Longest valid Parentheses - LeetCode with me 31

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

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Search in rotated sorted array - LeetCode with me 32

Search in rotated sorted array очень похоже на "сон для усталых взрослых людей", так как задачка не сложная - обычный бинарный поиск с дополнительной проверкой на излом массива.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Find First and Last Position of Element in Sorted Array - LeetCode with me 33

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

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Find Insert Position - LeetCode with me 34

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

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Valid Sudoku - LeetCode with me 35

Проверяем судоку на валидность. Есть решать задачку в лоб, ровно так, как написано в условии, то добиться высоких результатов, ожидаемо, не получится. Подход без использования вспомогательных структур данных позволяет получить 100% результат и именно его будем реализовывать.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Soduku Solver - LeetCode with me 36

В прошлый раз проверяли судоку на валидность, в этот раз будем решать с использованием алгоритма backtracking.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Count and Say - LeetCode with me 37

Несложная задачка с очень сложным описанием - реализуем алгоритм RLE (run-length encoding) или кодирование длин серий. Разберемся с условием и реализуем.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Combination Sum - LeetCode with me 38

Очередная задачка на backtracking - выбрать из массива элементы, которые в сумме дают заданное число. Если представить, что ищем сумму двух элементов, которые вместе дают target, то нужно зафиксировать один элемент, допустим, А, то нужно найти второй, который равен (target - A). С тремя элементами так же - зафиксируем один элемент (А) и будем искать теперь два других, которые в сумме дают (target - A). Для суммы неограниченной длинны делаем несколько итераций, где каждый раз уменьшаем target на значение зафиксированного элемента.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Combination Sum II - LeetCode with me 39

Очень похоже на задачку, которую мы решали в прошлый раз, на Combination Sum. Основная сложность этой задачи состоит в том, что теперь исходные данные могут содержать дубликаты, а в результатах дубликатов быть не должно. Можем использовать структуры данных вроде множеств, который позволяют от дубликатов избавиться, либо отсортируем входные данные и будем пропускать дубликаты.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

First Missing Positive - LeetCode with me 40

Задачка уровня Hard на поиск первого положительного пропуска в массиве. Рассмотрим два решения - очевидное и оптимальное, используем циклическую сортировку.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Trapping Rain Water - LeetCode with me 41

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

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Multiply Strings - LeetCode with me 42

Следующая задачка уже среднего уровня сложности на длинную арифметику - нужно умножить два числа представленные в виде строк. Применим метод, известный каждому еще со школы - умножение столбиком.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Wildcard Matching - LeetCode with me 43

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

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Jump Game II - LeetCode with me 44

Задача на динамическое программирование. Иногда кажется, что самые быстрые алгоритмы на LeetCode это далеко не самые правильные или подходящие, поэтому рассмотрим сначала хороший алгоритм, а потом быстрый.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Permutations - LeetCode with me 45

Сегодня рассмотрим две задачи на генерацию перестановок. Обе решаются сходным образом - с использованием алгоритма backtracking.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Rotate Image - LeetCode with me 46

Задача на поворот двухмерного изображения. Берем и поворачиваем.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Group Anagrams - LeetCode with me 47

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

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Pow x ^ n - LeetCode with me 48

Реализуем функцию возведения в степень без использования стандартной библиотеки. Для повышения производительности воспользуемся знаниями из школьного курса алгебры.

Это последнее, семидесятое видео в 2024 году. За весь год мои видео посмотрели более 61 тысячи раз, что составляет более 8 тысяч часов. А еще на канал на YouTube подписалось больше 1100 новых зрителей. Довольно неплохой рост, на мой взгляд!

Спасибо всем, кто был со мной в 2024 году, увидимся в новом, 2025 году!

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

N-Queens - LeetCode with me 49

Первая задача в новом 2025 году. Начнем с уровня Hard и расставим ферзей по шахматной доске. Ничего сложного, обычный backtracking.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode

Maximum Subarray - LeetCode with me 50

Ищем подмассив произвольной длинный с максимальной суммой. Задача решается с использованием скользящего окна или алгоритма Кадано. Также разберем рекурсивный подход, основанный на идее divide and conquer.

Ссылки: Ссылка на задачу | Patreon (если вы не в России) | Boosty (если вы в России) | #LeetCode