Общие принципы решения задачи TOP-150 LeetCode по группам
В этом уроке список задач с TOP-150 LeetCode сгруппирован по типам, для каждого типа указаны общие принципы и стратегии решения.
1. Два указателя (Two Pointers)
Задачи: 1, 2, 3, 4, 5, 11, 15, 26, 27, 28, 42, 46, 75, 86, 125, 132
Суть: Использование двух индексов для прохода по массиву/строке за один проход O(n).
Принципы:
- Встречные указатели: начало и конец, сходятся к центру (Palindrome, Two Sum II)
- Быстрый/медленный: один указатель идет быстрее (удаление дубликатов)
- Скользящее окно: оба указателя движутся в одну сторону (Minimum Size Subarray Sum)
Шаблон:
left, right = 0, len(arr)-1
while left < right:
if condition:
left += 1
else:
right -= 1
2. Скользящее окно (Sliding Window)
Задачи: 30, 31, 33, 76, 145, 146
Суть: Поддержание подмассива/подстроки с заданным свойством.
Типы:
- Фиксированное окно: K размер (Maximum Average Subarray)
- Динамическое окно: расширяется/сужается (без повторяющихся символов)
Шаблон:
left = 0
for right in range(len(arr)):
# Добавляем arr[right] в окно
while условие_нарушено:
# Удаляем arr[left] из окна
left += 1
# Обновляем результат
3. Динамическое программирование (DP)
Задачи: 13, 42, 53, 70, 97, 112, 113, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150
Суть: Разбиение на подзадачи, мемоизация результатов.
Подходы:
- 1D DP: Fibonacci, House Robber
- 2D DP: Edit Distance, LCS
- DP на подотрезках: Palindromic Substrings
- DP с битовыми масками: (в этом списке нет)
Общий принцип:
- Определить состояние dp[i]
- Найти переход между состояниями
- Определить базовые случаи
- Порядок вычисления (обычно снизу вверх)
Пример (1D):
dp = [0]*n
dp[0], dp[1] = base_cases
for i in range(2, n):
dp[i] = max(dp[i-1], dp[i-2] + arr[i])
4. Поиск и сортировка (Search & Sort)
Задачи: 5, 33, 34, 81, 88, 114, 115, 116, 117, 118, 119, 120, 121
Суть: Бинарный поиск, QuickSelect, свойства отсортированных массивов.
Бинарный поиск:
def binary_search(arr, target):
left, right = 0, len(arr)-1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Особые случаи:
- Пиковый элемент: arr[mid] сравниваем с соседями
- Повернутый массив: определяем, какая часть отсортирована
- Медиана двух массивов: разделение на левые/правые части
5. Хэш-таблицы и множества (Hash Maps & Sets)
Задачи: 12, 39, 40, 41, 42, 43, 44, 45, 46, 47, 128, 129
Суть: Использование словарей для O(1) доступа к данным.
Типичные применения:
- Подсчет частот: Counter из collections
- Проверка существования: set для уникальных значений
- Хранение индексов: для задач поиска пар
- Кэширование результатов: мемоизация
Шаблон:
from collections import Counter, defaultdict
# Частоты элементов
counter = Counter(arr)
# Группировка по ключу
groups = defaultdict(list)
for item in items:
key = transform(item)
groups[key].append(item)
6. Стек и очередь (Stack & Queue)
Задачи: 20, 21, 23, 52, 53, 54, 55, 56, 84, 85, 94, 124
Суть: LIFO/FIFO структуры для обработки данных в определенном порядке.
Применения:
- Стек: парные структуры (скобки), обратная польская запись
- Очередь: BFS обход графа, sliding window maximum
- Монотонный стек: ближайший больший/меньший элемент
Пример монотонного стека:
stack = []
for i in range(len(arr)):
while stack and arr[stack[-1]] < arr[i]:
idx = stack.pop()
# Обработка arr[idx]
stack.append(i)
7. Связные списки (Linked Lists)
Задачи: 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 75, 109, 111
Суть: Работа с указателями, развороты, слияния.
Техники:
- Разворот: итеративный и рекурсивный
- Слияние: Merge Two Sorted Lists
- Кольца: Floyd's Cycle Detection
- Dummy head: упрощение обработки краевых случаев
Шаблон разворота:
def reverse(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
8. Деревья (Trees)
Задачи: 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 108, 110
Суть: Рекурсивные обходы, свойства BST, построение деревьев.
Обходы:
# DFS рекурсивно
def dfs(node):
if not node:
return
# Pre-order: здесь
dfs(node.left)
# In-order: здесь (для BST)
dfs(node.right)
# Post-order: здесь
# BFS с очередью
from collections import deque
queue = deque([root])
while queue:
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
# Обработка
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
Особенности:
- BST: inorder дает отсортированный массив
- Построение: из inorder+preorder/postorder
- LCA: рекурсивный поиск с возвратом узлов
9. Графы (Graphs)
Задачи: 89, 90, 91, 92, 93, 94, 95, 96, 97
Суть: BFS/DFS обход, топологическая сортировка, компоненты связности.
Алгоритмы:
# BFS
def bfs(start):
queue = deque([start])
visited = set([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# DFS
def dfs(node, visited):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor, visited)
# Topological Sort (Kahn's)
def topological_sort(n, edges):
indegree = [0]*n
graph = defaultdict(list)
# Построение графа
queue = deque([i for i in range(n) if indegree[i]==0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return result if len(result)==n else []
10. Бектрекинг (Backtracking)
Задачи: 17, 51, 101, 102, 103, 104, 105, 106, 107
Суть: Рекурсивный перебор с откатом.
Шаблон:
def backtrack(path, choices):
if условие_остановки:
результат.append(path.copy())
return
for choice in choices:
if недопустимый_выбор:
continue
path.append(choice)
backtrack(path, новые_choices)
path.pop() # откат
Оптимизации:
- Отсечение: проверка перед углублением
- Мемоизация: кэширование результатов
- Симметрия: пропуск эквивалентных вариантов
11. Префиксное дерево (Trie)
Задачи: 98, 99, 100
Суть: Эффективный поиск строк с общим префиксом.
Структура:
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end
12. Жадные алгоритмы (Greedy)
Задачи: 6, 9, 10, 14, 45, 51, 122, 123
Суть: Локально оптимальный выбор ведет к глобальному оптимуму.
Области применения:
- Интервалы: сортировка по окончанию
- Задачи с прыжками: максимальный достижимый индекс
- Расписания: earliest finish time first
Пример (Jump Game):
def canJump(nums):
max_reach = 0
for i in range(len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])
return True
13. Побитовые операции (Bit Manipulation)
Задачи: 125, 126, 127, 128, 129, 130, 131
Суть: Использование битов для экономии памяти.
Основные операции:
x & 1 # младший бит x >> 1 # сдвиг вправо x << 1 # сдвиг влево x & (x-1) # сброс младшего единичного бита x & -x # получение младшего единичного бита x ^ x = 0 # XOR свойства
Паттерны:
- Single Number: XOR всех элементов
- Подсчет единиц: Brian Kernighan's algorithm
- Степени двойки: x & (x-1) == 0
14. Математические задачи (Math)
Задачи: 7, 8, 48, 131, 132, 133, 134, 135, 136
Суть: Формулы, свойства чисел, геометрия.
Типичные темы:
- Геометрия: Max Points on a Line (тангенсы)
- Числа: палиндромы, факториалы
- Интервалы: пересечения, объединения
- Степенная функция: быстрое возведение в степень
Быстрое возведение:
def pow(x, n):
if n == 0:
return 1
if n < 0:
return 1/pow(x, -n)
half = pow(x, n//2)
if n % 2 == 0:
return half * half
else:
return half * half * x
15. Матрицы (Matrix)
Задачи: 35, 36, 37, 38, 48, 73, 90, 115, 150
Суть: Обходы, повороты, преобразования.
Техники:
- Спиральный обход: 4 границы (top, bottom, left, right)
- Поворот: transpose + reverse
- Обход BFS/DFS: для островов и регионов
Шаблон спирали:
def spiral_order(matrix):
result = []
top, bottom = 0, len(matrix)-1
left, right = 0, len(matrix[0])-1
while top <= bottom and left <= right:
# Вправо
for j in range(left, right+1):
result.append(matrix[top][j])
top += 1
# Вниз
for i in range(top, bottom+1):
result.append(matrix[i][right])
right -= 1
if top <= bottom:
# Влево
for j in range(right, left-1, -1):
result.append(matrix[bottom][j])
bottom -= 1
if left <= right:
# Вверх
for i in range(bottom, top-1, -1):
result.append(matrix[i][left])
left += 1
return result
16. Строки (Strings)
Задачи: 17, 18, 19, 20, 21, 22, 23, 24, 25, 39, 40, 41, 43, 97, 106, 107, 145
Суть: Работа с подстроками, паттернами, преобразованиями.
Важные техники:
- KMP: для поиска подстрок (использует префикс-функцию)
- Z-функция: альтернатива KMP
- Палиндромы: расширение от центра
- Преобразования: группы, замены, сравнения
KMP префикс-функция:
def prefix_function(s):
pi = [0]*len(s)
for i in range(1, len(s)):
j = pi[i-1]
while j > 0 and s[i] != s[j]:
j = pi[j-1]
if s[i] == s[j]:
j += 1
pi[i] = j
return pi
Общие рекомендации:
- Сначала анализируйте ограничения - от них зависит подход
- Пишите псевдокод перед кодом
- Тестируйте краевые случаи: пустые структуры, один элемент
- Сложность: всегда оценивайте time/space complexity
- Практикуйте паттерны - многие задачи вариации известных
- Используйте встроенные структуры: Counter, defaultdict, deque, heapq
- Рекурсия vs Итерация: знайте когда что применять
- Оптимизация: иногда O(n²) достаточно, иногда нужно O(n)
Каждый блок требует практики. Начните с базовых задач в каждом блоке, затем переходите к сложным комбинациям.