Как решать LeetCode? Легко! Нужно просто…

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

На сегодняшний день алгоритмические задачи встречаются не только в FAANG. Многие компании и на отечественном рынке всё чаще вводят дополнительный алгоритмический этап на собеседовании – и знание алгоритмов становится отличным «плюсиком» не только при трудоустройстве, но и в решении повседневных задач. Взглянем подробнее на эти паттерны.

---

Прорешав более 1500 задач в LeetCode, я пришёл в такому выводу:

LeetCode - это не столько о том, сколько задач ты решил, сколько о том, сколько паттернов ты знаешь.

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

В этой статье мы разберём 15 видов паттернов, которые сделали мой опыт в LeetCode менее болезненным. Я подробно разберу каждый из них и оставлю ссылки на задачи в LeetCode, чтобы вы могли попрактиковаться.

1. Префиксные суммы (Prefix Sum)

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

Когда использовать: в ситуации, когда нужно выполнить несколько запросов сумм к подмассиву или вычислить совокупные суммы.

Пример задачи:

Дан массив nums. Вычислите сумму элементов в диапазоне [i, j].

Пример:

• Вход: nums = [1, 2, 3, 4, 5, 6], i = 1, j = 3

• Выход: 9

Объяснение:

• Создаём префиксный массив: P = [1, 3, 6, 10, 15, 21]

• Сумма элементов будет равна [i, j] = P[j] - P[i-1] (при i > 0)

Применимо к задачам:

• Range Sum Query - Immutable (LeetCode #303) ^[1]

• Contiguous Array (LeetCode #525) ^[2]

• Subarray Sum Equals K (LeetCode #560) ^[3]

Пример решения на Java: ссылка ^[4]

2. Два указателя (Two pointers)

Паттерн двух указателей использует два указателя для обхода массива или списка. Часто применяется для поиска пар элементов, удовлетворяющих определённому условию.

Когда использовать: при работе с отсортированными массивами или списками, где нужно найти пары, удовлетворяющие условию (например, сумма = target).

Пример задачи:

Найти два числа в отсортированном массиве, сумма которых равна заданному значению.

Пример:

• Вход: nums = [1, 2, 3, 4, 6], target = 6

• Выход: [1, 3] (индексы)

Объяснение:

• Инициализируем указатели: left = 0, right = len(nums) – 1

• Проверяем сумму элементов по двум указателям

• Если nums[left] + nums[right] == target → нашли решение

• Если сумма меньше — двигаем left вправо

• Если сумма больше — двигаем right влево

Применимо к задачам:

• Two Sum II - Input Array is Sorted (LeetCode #167) ^[5]

• 3Sum (LeetCode #15) ^[6]

• Container With Most Water (LeetCode #11) ^[7]

Пример решения на Java: ссылка ^[8]

3. Скользящее окно (Sliding Window)

Шаблон скользящего окна используется для поиска подмассива или подстроки, удовлетворяющей определённому условию. Он оптимизирует временную сложность за счёт поддержания «окна» фиксированного или переменного размера.

Когда использовать: при работе с непрерывными подмассивами или подстроками.

Пример задачи:

Найти максимальную сумму подмассива размера k.

Пример:

• Вход: nums = [2, 1, 5, 1, 3, 2], k = 3

• Выход: 9

Объяснение:

• Считаем сумму первых k элементов

• Затем «скользим» окно: вычитаем уходящий элемент, прибавляем входящий

• Отслеживаем максимальную сумму

Применимо к задачам:

• Maximum Average Subarray I (LeetCode #643) ^[9]

• Longest Substring Without Repeating Characters (LeetCode #3) ^[10]

• Minimum Window Substring (LeetCode #76) ^[11]

Пример решения на Java: ссылка ^[12]

4. Быстрый и медленный указатели (Fast & Slow Pointers)

Этот шаблон (известен как «черепаха и заяц») используется для обнаружения циклов в связных списках и других структурах.

Когда использовать: когда нужно определить наличие цикла, найти середину списка или решить задачи на цикличность.

Пример задачи:

Определить, содержит ли связный список цикличность.

Объяснение:

• Инициализируем два указателя: slow (1 шаг за итерацию), fast (2 шага)

• Если fast и slow встречаются — цикличность есть

• Если fast дошёл до конца — цикличности нет

Применимо к задачам:

• Linked List Cycle (LeetCode #141) ^[13]

• Happy Number (LeetCode #202) ^[14]

• Find the Duplicate Number (LeetCode #287) ^[15]

Пример решения на Java: ссылка ^[16]

5. Разворот связного списка на месте (In-place Reversal of LinkedList)

Этот шаблон позволяет разворачивать часть связного списка без дополнительного пространства.

Когда использовать: когда нужно развернуть подсписок или весь список «на месте».

Пример задачи:

Развернуть подсписок с позиции m по n.

Пример:

• Вход: head = [1, 2, 3, 4, 5], m = 2, n = 4

• Выход: [1, 4, 3, 2, 5]

Объяснение:

• Находим узлы до m и после n

• Разворачиваем участок между ними, корректируя указатели

Применимо к задачам:

• Reverse Linked List (LeetCode #206) ^[17]

• Reverse Linked List II (LeetCode #92) ^[18]

• Swap Nodes in Pairs (LeetCode #24) ^[19]

Пример решения на Java: ссылка ^[20]

6. Монотонный стек (Monotonic Stack)

Монотонный стек поддерживает элементы в стеке в строго возрастающем или убывающем порядке. Часто используется для поиска следующего большего/меньшего элемента.

Когда использовать: когда нужно найти ближайший больший/меньший элемент слева или справа.

Пример задачи:

Для каждого элемента массива найти следующий больший элемент. Если такого нет — вывести -1.

Пример:

• Вход: nums = [2, 1, 2, 4, 3]

• Выход: [4, 2, 4, -1, -1]

Объяснение:

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

• Перебираем массив и извлекаем элементы из стека для каждого элемента, пока не найдем больший элемент

• Если стек не пуст, устанавливаем результат для индекса наверху стека в текущий элемент

• Помещаем текущий элемент в стек

Применимо к задачам:

• Next Greater Element I (LeetCode #496) ^[21]

• Daily Temperatures (LeetCode #739) ^[22]

• Largest Rectangle in Histogram (LeetCode #84) ^[23]

Пример решения на Java: ссылка ^[24]

7. Топ K элементов (Top ‘K’ Elements)

Этот шаблон находит K наибольших или наименьших элементов с помощью куч (heap) или сортировки.

Когда использовать: при поиске медианы, топ-K элементов в потоке.

Пример задачи:

Найти K-й по величине элемент в неотсортированном массиве.

Пример:

• Вход: nums = [3, 2, 1, 5, 6, 4], k = 2

• Выход: 5

Объяснение:

• Используем минимальную кучу (min-heap) размера k, чтобы отслеживать k крупнейших элементов

• Перебираем массив, добавляя элементы в кучу

• Если размер кучи превышает k, удаляем из кучи наименьший элемент

• Корнем кучи будет k-й по величине элемент

Применимо к задачам:

• Kth Largest Element in an Array (LeetCode #215) ^[25]

• Top K Frequent Elements (LeetCode #347) ^[26]

• Find K Pairs with Smallest Sums (LeetCode #373) ^[27]

Пример решения на Java: ссылка ^[28]

8. Перекрывающиеся интервалы (Overlapping Intervals)

Шаблон для слияния или обработки интервалов, которые пересекаются.

Когда использовать: при работе с графиками, расписаниями, объединением диапазонов.

Пример задачи:

Слить все перекрывающиеся интервалы.

Пример:

• Вход: [[1,3], [2,6], [8,10], [15,18]]

• Выход: [[1,6], [8,10], [15,18]]

Объяснение:

• Сортируем интервалы по началу

• Создаем пустой список с именем merged для хранения объединенных интервалов

• Перебираем интервалы и проверяем, не перекрывается ли они с последним интервалом в объединенном списке

• Если они перекрываются, объединяем интервалы, обновив время окончания последнего объединенного интервала

• Если они не пересекаются, просто добавляем текущий интервал в объединенный список

Применимо к задачам:

• Merge Intervals (LeetCode #56) ^[29]

• Insert Interval (LeetCode #57) ^[30]

• Non-Overlapping Intervals (LeetCode #435) ^[31]

Пример решения на Java: ссылка ^[32]

9. Модифицированный бинарный поиск (Modified Binary Search)

Адаптация бинарного поиска для вращённых отсортированных массивов, нахождения границ и т.д.

Когда использовать: при работе с отсортированными или повёрнутыми массивами и поиске элементов.

Пример задачи:

Найти элемент в повёрнутом отсортированном массиве.

Пример:

• Вход: nums = [4,5,6,7,0,1,2], target = 0

• Выход: 4 (индекс)

Объяснение:

• Выполняем двоичный поиск с дополнительной проверкой, чтобы определить, какая половина массива отсортирована

• Затем проверяем, находится ли цель в пределах отсортированной половины

• Если да, ищем эту половину; в противном случае ищем вторую половину

Применимо к задачам:

• Search in Rotated Sorted Array (LeetCode #33) ^[33]

• Find Minimum in Rotated Sorted Array (LeetCode #153) ^[34]

• Search a 2D Matrix II (LeetCode #240) ^[35]

Пример решения на Java: ссылка ^[36]

10. Обход бинарного дерева (Binary Tree Traversal)

Обход всех узлов дерева в определённом порядке:

• PreOrder: корень → лево → право

• InOrder: лево → корень → право

• PostOrder: лево → право → корень

Когда использовать: почти во всех задачах на деревья.

Пример задачи:

Выполнить inorder-обход.

Пример:

• Вход: root = [1, null, 2, 3]

• Выход: [1, 3, 2]

Объяснение:

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

• Используем рекурсию или стек для обхода дерева в этом порядке.

Применимо к задачам:

• PreOrder → Binary Tree Paths (LeetCode #257) ^[37]

• InOrder → Kth Smallest Element in a BST (LeetCode #230) ^[38]

• PostOrder → Binary Tree Maximum Path Sum (LeetCode #124) ^[39]

Пример решения на Java: ссылка ^[32]

11. Поиск в глубину (DFS)

Погружаемся как можно глубже по одной ветке, прежде чем вернуться назад.

Когда использовать: для обхода всех путей, генерации комбинаций, рекурсивных задач на деревья/графы.

Пример задачи:

Найти все пути от корня до листьев.

Пример:

• Вход: root = [1,2,3,null,5]

• Выход: ["1->2->5", "1->3"]

Объяснение:

• Используем рекурсию или стек для прохождения каждого пути от корня к листьям.

• Записываем каждый путь по мере прохождения.

Применимо к задачам:

• Clone Graph (LeetCode #133) ^[40]

• Path Sum II (LeetCode #113) ^[41]

• Course Schedule II (LeetCode #210) ^[42]

Пример решения на Java: ссылка ^[43]

12. Поиск в ширину (BFS)

Узлы исследуются уровень за уровнем в дереве или графе.

Когда использовать: для поиска кратчайшего пути в невзвешенном графе, обхода по уровням.

Пример задачи:

Выполнить уровневый обход бинарного дерева.

Пример:

• Вход: root = [3,9,20,null,null,15,7]

• Выход: [[3], [9,20], [15,7]]

Объяснение:

• Используем очередь для отслеживания узлов на каждом уровне.

• Проходим каждый уровень и добавляем в очередь дочерние элементы текущих узлов.

Применимо к задачам:

• Binary Tree Level Order Traversal (LeetCode #102) ^[44]

• Rotting Oranges (LeetCode #994) ^[45]

• Word Ladder (LeetCode #127) ^[46]

Пример решения на Java: ссылка ^[47]

13. Обход матрицы (Matrix Traversal)

Обход элементов матрицы с помощью DFS, BFS и других техник.

Когда использовать: при работе с двумерной сеткой (grid) или матрицой, островами, заливкой и т.п.

Пример задачи:

Выполнить заливку (flood fill) — изменить цвет всех смежных клеток, начиная с заданной.

Пример:

• Вход: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2

• Выход: [[2,2,2],[2,2,0],[2,0,1]]

Объяснение:

• Используем DFS или BFS для перемещения по матрице, начиная с заданной ячейки.

• Изменяем цвет соединенных ячеек на новый цвет.

Применимо к задачам:

• Flood Fill (LeetCode #733) ^[48]

• Number of Islands (LeetCode #200) ^[49]

• Surrounded Regions (LeetCode #130) ^[50]

Пример решения на Java: ссылка ^[51]

14. Возврат (Backtracking)

Backtracking перебирает все возможные решения, откатываясь при неудаче.

Когда использовать: для задач на перестановки, комбинации, размещения, судоку и т.д.

Пример задачи:

Сгенерировать все перестановки списка.

Пример:

• Вход: nums = [1,2,3]

• Выход: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Объяснение:

• Используем рекурсию для создания перестановок.

• Для каждого элемента включаем его в текущую перестановку и рекурсивно сгенерируем оставшиеся перестановки.

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

Применимо к задачам:

• Permutations (LeetCode #46) ^[52]

• Subsets (LeetCode #78) ^[53]

• N-Queens (LeetCode #51) ^[54]

Пример решения на Java: ссылка ^[55]

15. Динамическое программирование (Dynamic Programming)

ДП разбивает задачу на подзадачи и решает их, избегая повторных вычислений.

Когда использовать: когда есть перекрывающиеся подзадачи и оптимальная подструктура.

Подтипы ДП:

• Числа Фибоначчи

• Рюкзак (0/1 Knapsack)

• Наибольшая общая подпоследовательность (LCS)

• Наибольшая возрастающая подпоследовательность (LIS)

• Сумма подмножества

• Умножение цепочки матриц

Пример задачи:

Найти n-е число Фибоначчи.

Пример:

• Вход: n = 5

• Выход: 5 (последовательность: 0, 1, 1, 2, 3, 5)

Объяснение:

• Используем восходящий подход для вычисления n-го числа Фибоначчи.

• Начинаем с первых двух чисел (0 и 1) и выполняем итерацию для вычисления следующих чисел, например (dp[i] = dp[i - 1] + dp[i - 2]).

Применимо к задачам:

• Climbing Stairs (LeetCode #70) ^[56]

• House Robber (LeetCode #198) ^[57]

• Coin Change (LeetCode #322) ^[58]

• Longest Common Subsequence (LCS) (LeetCode #1143) ^[59]

• Longest Increasing Subsequence (LIS) (LeetCode #322) ^[60]

• Partition Equal Subset Sum (LeetCode #416) ^[61]

Пример решения на Java: ссылка ^[62]

Все решения в нашем GitLab: ссылка ^[63]