Алгоритмы и структуры данных

Поиск в 2D-матрице

Проблема: Дана двумерная целочисленная матрица (matrix) размера m x n и число (target), которое надо найти в матрице. Каждая строка матрицы сортируется в порядке неубывания. Первое целое число каждой строки больше последнего целого числа предыдущей строки. Необходимо реализовать алгоритм, который возвращает true, если число найдено в матрице, или false в противном случае.

Пример:
Input: matrix = [[1,2,4,8],[10,11,12,13],[14,20,30,40]], target = 10
Output: true

Самый большой прямоугольник в гистограмме

Проблема: Дан массив целых чисел heights, где heights[i] представляет высоту столбца. Ширина каждого столбца равна 1.

Необходимо реализовать алгоритм, который возвращает площадь наибольшего прямоугольника, который может быть сформирован среди столбцов.

function largestRectangleArea(heights) {
    heights.append(0) 
    stack = empty stack
    max_area = 0

    for i from 0 to length(heights) - 1 {
        while stack is not empty and 
        heights[i] < heights[stack.top()] {
            height = heights[stack.pop()]
            width = if stack is empty ? i : i - stack.top() - 1
            max_area = max(max_area, height * width)
        }
        stack.push(i)
    }
    return max_area
}

🚀 Приглашаем на бесплатный вебинар по C++! 🚀

Дата: 19 ноября 2024 года
Время: 20:00
Тема: Как протестировать C++ код и оценить степень собственной лени

На вебинаре поговорим о том, зачем разработчикам писать юнит-тесты, и какую пользу они несут. Посмотрим популярные фреймворки тестирования, такие как GTest и Boost, разберем несколько практических примеров. Затем попробуем оценить, достаточно ли тестов мы написали для своего кода.

На занятии:
1. Научимся подключать фреймворки тестирования к своему проекту при помощи CMake.
2. Напишем готовые к запуску тесты.
3. Поговорим о том, как измерить покрытие тестами кода, какие инструменты для этого существуют.

В результате:
1. Придем к тому, что вместе с кодом стоит сразу писать и юнит-тесты к нему.
2. В будущем с легкостью интегрируем любой фреймворк тестирования в свой проект.
3. Научимся не только писать тесты, но и мерить их покрытие.

👉🏻О курсе "Специализация C++ Developer" на Otus:
Длительность курса: 10 месяцев.
Формат: Онлайн.

Программа курса:
· Введение в язык C++: основы синтаксиса, структура программ, базовые конструкции.
· Классы и структуры: ООП, наследование, полиморфизм, шаблоны.
· Основы unit-тестирования: подключение фреймворков, написание тестов, измерение покрытия.
· Стандартная библиотека и полезные алгоритмы: контейнеры, ввод-вывод, алгоритмы.

📌Скидка 15%: действует до 17 ноября!

Не упустите шанс стать профессионалом в C++! Присоединяйтесь к вебинару и узнайте больше о курсе.
🔗 Регистрация на вебинар

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576, www.otus.ru

Температура воздуха

Проблема: Дан массив целых чисел, где температура[i] представляет собой дневную температуру в i-й день.

Необходимо реализовать алгоритм, который возвращает результат массива, где result[i] — это количество дней после i-го дня до появления более высокой температуры в будущий день. Если в будущем не будет дня, когда в i-й день будет более высокая температура, вместо этого установите result[i] в ​​0.

Пример 1:
Input: temperatures = [30,38,30,36,35,40,28]
Output: [1,4,1,2,1,0,0]

Пример 2:
Input: temperatures = [22,21,20]
Output: [0,0,0]

Обратная польская запись

Проблема: Дан массив строковых токенов, который представляет допустимое арифметическое выражение в обратной польской нотации. В результате возвращает целое число, представляющее оценку выражения.

Операнды могут быть целыми числами или результатами других операций. К операторам относятся «+», «-», «*» и «/». Предположим, что деление целых чисел всегда сокращается до нуля.

Пример:
Input: tokens = ["1","2","+","3","*","4","-"]
Output: 5
Объяснение: ((1 + 2) * 3) - 4 = 5

Проверка скобок

Проблема: Дана строка s, состоящая из следующих символов: '(', ')', '{', '}', '[' и ']'. Входная строка s действительна тогда и только тогда, когда:
- Каждая открытая скобка закрывается закрывающей скобкой одного и того же типа.
- Открытые скобки закрываются в правильном порядке.
- Каждой закрывающей скобке соответствует открытая скобка того же типа.

В результате надо вывести true, если s — допустимая строка, и false в противном случае.

Пример 1:
Input: s = "([{}])"
Output: true

Пример 2:
Input: s = "[(])"
Output: false

Покупка и продажа крипты

Проблема: Дан целочисленный массив цен, где prices[i] — цена AlgoCoin на i-й день. Можно выбрать один день для покупки одного AlgoCoin и выбрать другой день в будущем для его продажи.

В результате надо вывести максимальную прибыль, которую можно получить. Кроме того, есть возможность отказаться от совершения каких-либо транзакций, и в этом случае прибыль будет равна 0.

Пример 1:
Input: prices = [10,1,5,6,7,1]
Output: 6
Пояснение: купить за prices[1] и продать по prices[4]. В итоге, прибыль = 7 – 1 = 6.

Пример 2:
Input: prices = [10,8,7,5,2]
Output: 0
Пояснение: Невозможно совершить прибыльные сделки, поэтому максимальная прибыль равна 0.

Улавливание дождевой воды

Проблема: Дан массив высот неотрицательных целых чисел, которые представляют карту высот. Каждое значение heights[i] представляет высоту полосы, ширина которой равна 1.

В результате должно вернуться максимальная площадь воды, которая может задерживаться между решетками.

Контейнер для воды

Проблема: Дан целочисленный массив heights, где heights[i] представляет высоту i-ой колонки.

Можно выбрать любые две колонки, чтобы сформировать контейнер. В результате должно вернуться максимальное количество воды, которое может хранить контейнер.

function maxArea(heights) {
    left = 0
    right = length(heights) - 1
    max_area = 0

    while left < right {
        height = min(heights[left], heights[right])
        width = right - left
        current_area = height * width
        max_area = max(max_area, current_area)

        if heights[left] < heights[right] { 
            left += 1 
        }
        else { right -= 1 }
    }
    return max_area
}

👨‍💻 Потренируйтесь проходить собеседования с разработчиками из Яндекса, VK, Ozon, Тинькофф и других ведущих компаний, а также получите подробный отзыв о том, на какую зарплату и грейд вы можете расчитывать, или над чем вам еще стоит поработать.

Потренироваться проходить собеседования

Сумма трёх целых чисел

Проблема: Дан целочисленный массив nums. Необходимо реализовать алгоритм, который вернет все тройки [nums[i], nums[j], nums[k]], где nums[i] + nums[j] + nums[k] == 0, и индексы i, j и k различны.

Вывод не должен содержать повторяющихся троек. Можно вернуть результат и тройки в любом порядке.

Пример 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Объяснение:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.

Пример 2:
Input: nums = [0,0,0]
Output: [[0,0,0]]

⁉️ Хотите усовершенствовать навыки программирования, прокачать алгоритмическое мышление и претендовать на более интересные вакансии?

Добро пожаловать на курс «Алгоритмы и структуры данных»!

- сможете повысить производительность программ и улучшить качество кода
- приобретёте опыт реализации классических алгоритмов
- поймёте, как создавать собственные алгоритмы для решения бизнес-задач

👨‍💻🛠👨🏻‍💻 Курс для бэкенд- и фронтенд-разработчиков, а также для начинающих программистов (на любом языке программирования).

Обучайтесь у экспертов из ведущих компаний, решайте задачи из практики и подтвердите повышение квалификации
в выпускном проекте.

🗓Курс стартует 30 октября
➡️ Чтобы начать обучение, пройдите вступительный тест

🔴 Записаться на курс «Алгоритмы и структуры данных»: https://otus.pw/nTy5/

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Самая длинная последовательность

Проблема: Дан массив целых чисел nums. Необходимо реализовать алгоритм, который вернет длину самой длинной последовательности элементов.

Самая длинная последовательность — это последовательность элементов, в которой каждый элемент ровно на 1 больше предыдущего элемента.

Пример 1:
Input: nums = [2,20,4,10,3,4,5]
Output: 4

Пример 2:
Input: nums = [0,3,2,5,4,6,1,1]
Output: 7

Хотите узнать, как реализовать идеальную хэш-таблицу, которая работает за О(L) время?

Ждем вас на открытом вебинаре 21 октября в 20:00 мск, где мы разберем:

- как создать алгоритм ассоциативного массива на основе идеальной хэш-таблицы;
- как исключить коллизии с помощью двухступенчатой хэш-таблицы;
- как выполнить визуальное тестирование с англо-русским словарем на 2.000 слов.

👨‍💻🛠👨🏻‍💻 Урок для Junior-разработчиков на любых языках программирования.

🚀 Спикер Евгений Волосатов — программист баз данных и преподаватель с огромным и разнообразным опытом, автор статей и учебных программ по C#, Java, PHP.

🆓 Встречаемся в преддверии старта курса «Алгоритмы и структуры данных». Все участники вебинара получат специальную цену на обучение!

🔴 Регистрируйтесь прямо сейчас, чтобы не пропустить мероприятие: https://otus.pw/8X3Xe/

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Произведения всех элементов массива, кроме текущего

Проблема: Дан целочисленный массив nums. Необходимо реализовать алгоритм, который вернет массив, где iый элемент является произведением всех элементов nums, кроме nums[i] (каждое произведение гарантированно умещается в 32-битное целое число).

Для решения задачи без использования операции деления и за O(n) времени, можно использовать метод предварительного вычисления произведений. Идея заключается в том, чтобы использовать два прохода по массиву: один для вычисления произведений слева от текущего элемента и другой для вычисления произведений справа от текущего элемента.

Пример:
Input: nums = [-1,0,1,2,3]
Output: [0,-6,0,0,0]

"K" элементов в списке

Проблема: Дан целочисленный массив nums и целое число k. Необходимо реализовать алгоритм, который вернет k наиболее часто встречающихся элементов массива. Можно вернуть вывод в любом порядке.

Пример 1:
Input: nums = [1,2,2,3,3,3], k = 2
Output: [2,3]

Пример 2:
Input: nums = [7,7], k = 1
Output: [7]

Хотите узнать, как превратить массив в пирамиду и ускорить сортировку данных?

Ждем вас на бесплатном вебинаре 14 октября в 20:00 мск, где мы разберем:

- как реализовать алгоритм сортировки выбором с линейной сложностью;
- как превратить массив в пирамиду (кучу) для быстрого доступа к максимальному элементу;
- как создать алгоритм пирамидальной сортировки с квазилинейной сложностью — О(N log N);
- визуальные примеры работы алгоритма на конкретных числах.

🚀 Спикер Евгений Волосатов — программист баз данных и преподаватель с огромным и разнообразным опытом, автор статей и учебных программ по C#, Java, PHP.

Встречаемся в преддверии старта курса «Алгоритмы и структуры данных». Все участники вебинара получат специальную цену на обучение!

Регистрируйтесь прямо сейчас, чтобы не пропустить мероприятие: https://otus.pw/JPJs/

Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576

Группы анаграмм

Проблема: Дан массив строк strs. Необходимо реализовать алгоритм, который сгруппирует все анаграммы в подгруппы. Можно вернуть вывод в любом порядке.

Анаграмма — это строка, содержащая те же символы, что и другая строка, но порядок символов может быть другим.

Пример 1:
Input: strs = ["act","pots","tops","cat","stop","hat"]
Output: [["hat"],["act", "cat"],["stop", "pots", "tops"]]

Пример 2:
Input: strs = ["x"]
Output: [["x"]]

Два целых числа

Проблема: Дан массив целых чисел nums и целочисленный target. Необходимо реализовать алгоритм, который вернет индексы i и j такие, что nums[i] + nums[j] == target и i != j. Можно предположить, что каждый input имеет ровно одну пару индексов i и j, удовлетворяющих условию. Сначала верните ответ с меньшим индексом.

Пример 1:
Input: nums = [3,4,5,6], target = 7
Output: [0,1]


Пример 2:
Input: nums = [-3,4,3,90], target=0
Output: [0,2]

Анаграмма

Проблема: Даны две строки s и t. Необходимо реализовать алгоритм, который возвращает true, если эти две строки являются анаграммами друг друга, в противном случае верните false.

Анаграмма — это строка, содержащая те же символы, что и другая строка, но порядок символов может быть другим.

Пример 1:
Input: s = "racecar", t = "carrace"
Output: true

Пример 2:
Input: s = "jar", t = "jam"
Output: false

Повторяющееся целое число

Проблема: Дан целочисленный массив array. Необходимо реализовать алгоритм, который возвращает true, если какое-либо значение встречается в массиве более одного раза, в противном случае возвращается false.

Пример 1:
Input: nums = [1, 2, 3, 3]
Output: true

Пример 2:
Input: nums = [1, 2, 3, 4]
Output: false

Вычисление лексикографически следующей битовой перестановки

Дано число v, представляющее собой текущее расположение битов, и необходимо вычислить следующую лексикографическую перестановку битов с заданным количеством единиц.

Например, если задано 3 бита и текущее расположение битов:
00010011,
то следующими будут:
00010101,
00010110,
00011001,
00011010,
00011100,
00100011 и так далее.

*Функция __builtin_ctz(v) компилятора GNU C для процессоров x86 возвращает количество замыкающих нулей. Для компиляторов Microsoft для x86 используется intrinsic _BitScanForward. Обе функции генерируют инструкцию bsf, но могут быть доступны эквиваленты для других архитектур. Если их нет, можно использовать один из методов подсчета подряд идущих нулевых битов.

Подсчет количества байтов между m и n

Макрос countbetween предназначен для подсчета количества байтов в слове x, которые находятся в диапазоне m < значение < n. Он использует макрос hasbetween, чтобы сначала найти все байты, которые удовлетворяют этому условию, а затем подсчитывает их количество.

Точное определение нахождения байта со значением между m и n

Этот макрос использует побитовые и арифметические операции для проверки, содержит ли слово x байт со значением между m и n. hasbetween дает точный результат, но использует больше операций для достижения этого по сравнению с макросом likelyhasbetween.

Определение, содержит ли слово байт со значением между m и n

Когда m < n, следующая техника позволяет проверить, содержит ли слово x байт со значением, таким образом, что m < значение < n. Эта техника использует 7 арифметических/логических операций, если n и m являются константами.

Однако, иногда может давать ложные срабатывания (false positives), т.е. оно может сообщить, что значение находится в диапазоне, когда это не так.

Подсчет количества байтов, больше заданного значения

Для подсчета количества байтов в x, значение которых больше n, можно использовать макрос countmore, который использует 6 операций.

Определение наличия байта, больше заданного значения, в 32-битном слове

Для проверки, содержит ли слово x байт со значением, превышающим n, можно использовать макрос hasmore. Он использует всего 3 арифметических/логических операции, если n является константой.

Предполагается, что x ≥ 0 и 0 ≤ n ≤ 127.

Подсчет количества байтов, меньше заданного значения

Макрос countless предназначен для подсчета количества байтов в 32-битном слове, значение которых меньше заданного числа n. Этот макрос выполняет задачу с использованием 7 арифметических и логических операций. Он позволяет эффективно обрабатывать данные, минимизируя количество операций и, следовательно, увеличивая производительность.

Определение наличия байта, меньше заданного значения, в 32-битном слове

Этот метод проверяет, содержит ли 32-битное слово байт с значением, которое меньше заданного числа n, используя всего 4 операции. Он эффективен и быстро выполняет задачу путем вычитания маскированного значения, инвертирования исходного слова и маскирования старших битов.

Определение наличия байта с определенным значением в 32-битном слове

Иногда возникает необходимость проверить, содержит ли любое 8-битное значение в 32-битном слове определенное значение. Для этого можно использовать операцию XOR, чтобы проверить совпадение каждого байта с искомым значением, и затем определить, содержит ли результат нулевой байт.

Определение наличия нулевого байта в 32-битном слове

Определение наличия нулевого байта является важной задачей при работе с данными и строками. Эффективные методы для выполнения этой проверки могут значительно улучшить производительность программ. Один из таких методов использует побитовые операции для минимизации числа операций и повышения скорости.

Оптимизированный метод определения наличия нулевого байта в 32-битном слове

Определение наличия нулевого байта в 32-битном слове — важная задача, которая часто встречается при обработке строк и других данных.

Преимущества метода
- Эффективность: Метод использует всего 4 операции, что делает его чрезвычайно быстрым.
- Компактность: Код прост и легко интегрируется в любые программы.
- Надежность: Метод точно определяет наличие нулевого байта, минимизируя количество ложных срабатываний.