--- title: "Паттерны алгоритмов: все 52 и какой нужен задаче" url: https://algopath.pro/ru/patterns language: ru summary: "Почти любая задача с собеседования - это одна из немногих форм в новой обёртке. Каждая страница ниже называет форму, слова в условии, которые на неё указывают, и соседа, с которым её путают." --- # Паттерны алгоритмов: все 52 и какой нужен задаче ## Массивы - [Преобразование массива на месте (In-place array transform)](https://algopath.pro/ru/patterns/in-place-array) - O(n) Индекс записи идёт следом за индексом чтения по одному буферу. Назад копируется только нужное, второй массив не создаётся. ## Хеширование - [Хеш-множество / словарь (Hash set / map)](https://algopath.pro/ru/patterns/hash-set-map) - O(n) Хеш превращает поиск в один шаг. Множество отвечает, встречалось ли значение, словарь отвечает, сколько раз оно встречалось. ## Два указателя - [Два указателя (с концов) (Two pointers (opposite ends))](https://algopath.pro/ru/patterns/two-pointers-opposite) - O(n) Два индекса стартуют по краям отсортированного массива и идут навстречу. Каждый шаг двигает ту сторону, что мешает ответу. - [Два указателя (в одну сторону) (Two pointers (same direction))](https://algopath.pro/ru/patterns/two-pointers-same-direction) - O(n) Указатель чтения бежит вперёд, а указатель записи идёт следом. Запись сдвигается только там, где значение стоит сохранить. ## Скользящее окно - [Скользящее окно (фиксированный размер) (Sliding window (fixed size))](https://algopath.pro/ru/patterns/sliding-window-fixed) - O(n) Окно ровно из k элементов катится по шагу за раз. Добавьте входящее значение, уберите выходящее, остальное не пересчитывайте. - [Скользящее окно (переменное) (Sliding window (variable))](https://algopath.pro/ru/patterns/sliding-window-variable) - O(n) Растите окно справа, а как только условие сломалось, сужайте его слева. Ни один из концов никогда не идёт назад по массиву. ## Префиксные суммы - [Префиксные суммы (Prefix sums)](https://algopath.pro/ru/patterns/prefix-sums) - O(n) build / O(1) query Храните накопленную сумму всего, что стоит до данного индекса. Тогда сумма на отрезке это одно вычитание, а не целый цикл. - [Массив разностей (Difference array)](https://algopath.pro/ru/patterns/difference-array) - O(n) Записывайте не значение, а изменение в каждой точке. Обновление отрезка стоит двух записей, а один проход в конце всё собирает. ## Поиск - [Линейный поиск (Linear search)](https://algopath.pro/ru/patterns/linear-search) - O(n) Идите по коллекции с одного конца и остановитесь на первом подходящем элементе. Ни порядка, ни структуры, ни подготовки. - [Бинарный поиск (массив) (Binary search (array))](https://algopath.pro/ru/patterns/binary-search-array) - O(log n) Посмотрите на середину отсортированного отрезка и выбросьте половину, где ответа быть не может. Повторяйте до одного элемента. - [Бинарный поиск во вращённом массиве (Binary search on a rotated array)](https://algopath.pro/ru/patterns/binary-search-rotated) - O(log n) Отсортированный массив, разрезанный и переставленный, на каждом шаге хранит одну отсортированную половину. Найдите её и выберите сторону. - [Бинарный поиск по ответу (Binary search on the answer)](https://algopath.pro/ru/patterns/binary-search-on-answer) - O(n log(range)) Искать здесь надо не в данных, а в диапазоне возможных ответов. Проверка да или нет говорит, какую половину можно выбросить. ## Сортировка - [Элементарные сортировки (выбором, пузырьком, вставками) (Elementary sorts (selection, bubble, insertion))](https://algopath.pro/ru/patterns/elementary-sort) - O(n^2) Сортировки выбором, пузырьком и вставками сравнивают соседей и меняют их местами. Все три стоят O(n в квадрате) на перемешанных данных. - [Быстрая сортировка (merge / quick) (Fast sort (merge / quick))](https://algopath.pro/ru/patterns/fast-sort) - O(n log n) Разрежьте массив надвое, отсортируйте каждую часть и соберите обратно. Merge режет по позиции, а quick режет по значению. - [Сортировка без сравнений (подсчётом / поразрядная) (Non-comparison sort (counting / radix))](https://algopath.pro/ru/patterns/non-comparison-sort) - O(n) Сортировки подсчётом и поразрядная не сравнивают значения между собой. Они читают сам ключ и обгоняют n log n на узком диапазоне. - [Сортировка с пользовательским компаратором (Sort with a custom comparator)](https://algopath.pro/ru/patterns/sort-comparators) - O(n log n) Компаратор отвечает ровно на один вопрос: какой из двух элементов идёт раньше. Всё остальное берёт на себя сама сортировка. ## Интервалы - [Интервалы: слияние и вставка (Intervals: merge & insert)](https://algopath.pro/ru/patterns/intervals-merge) - O(n log n) Отсортируйте интервалы по началу и пройдите их один раз. Соседи сливаются, если следующее начало не позже текущего конца. - [Линия развёртки (подсчёт событий) (Sweep line (event counting))](https://algopath.pro/ru/patterns/sweep-line) - O(n log n) Превратите каждый интервал в событие начала и событие конца. Отсортируйте события по координате и пройдите со счётчиком. ## Связные списки - [Разворот связного списка (Linked list reversal)](https://algopath.pro/ru/patterns/linked-list-reversal) - O(n) Пройдите список один раз и в каждом узле разверните ссылку на предыдущий узел. Трёх локальных переменных для этого хватит. - [Быстрый и медленный указатели (Fast & slow pointers)](https://algopath.pro/ru/patterns/fast-slow-pointers) - O(n) Один указатель делает по одному шагу за раз, а другой сразу по два. Именно разрыв между ними выдаёт циклы и середину списка. - [Слияние и перестройка связного списка (Linked list merge & reorder)](https://algopath.pro/ru/patterns/linked-list-merge) - O(n + m) Стройте ответ на фиктивном узле и берите головы из обоих списков. Фиктивный узел убирает разбор случая пустого результата. ## Стеки и очереди - [Стек (LIFO) (Stack (LIFO))](https://algopath.pro/ru/patterns/stack) - O(n) Стек всегда отдаёт самый свежий положенный элемент первым. Поэтому он подходит всему, что закрывается в обратном порядке. - [Монотонный стек (Monotonic stack)](https://algopath.pro/ru/patterns/monotonic-stack) - O(n) Держите значения в стеке возрастающими снизу вверх. Снимайте всё, что проигрывает новому, и каждое снятие находит ответ. - [Монотонная дек-очередь (максимум/минимум окна) (Monotonic deque (sliding window max/min))](https://algopath.pro/ru/patterns/monotonic-deque) - O(n) Дек, упорядоченный так, что спереди всегда лежит максимум окна. Проигравшие значения уходят сзади, а устаревшие спереди. ## Рекурсия - [Рекурсия (Recursion)](https://algopath.pro/ru/patterns/recursion) - O(n) Функция вызывает саму себя на уменьшенной версии задачи. Базовый случай её останавливает, а вызовы разворачиваются назад. - [Рекурсия с мемоизацией (Recursion with memoization)](https://algopath.pro/ru/patterns/memoization) - O(states) Рекурсия, которая записывает каждый посчитанный ответ. Когда тот же аргумент приходит снова, отдаётся сохранённое значение. ## Перебор с возвратом - [Бэктрекинг (Backtracking)](https://algopath.pro/ru/patterns/backtracking) - O(2^n)/O(n!) Сделайте выбор, спуститесь вниз, а потом отмените выбор. Именно отмена позволяет одному массиву держать все варианты подряд. ## Деревья - [Обход дерева (Tree traversal)](https://algopath.pro/ru/patterns/tree-traversal) - O(n) Обойдите каждый узел дерева ровно один раз. Именно то, в каком месте вы посещаете узел, и решает, что в итоге вычислит обход. - [Двоичное дерево поиска (Binary search tree)](https://algopath.pro/ru/patterns/bst) - O(log n) avg Дерево поиска держит все меньшие значения слева, а большие справа. Каждый поиск отбрасывает целиком одну сторону дерева. - [Наименьший общий предок (Lowest common ancestor)](https://algopath.pro/ru/patterns/tree-lca) - O(n) Наименьший общий предок это самый глубокий узел, под которым лежат обе цели. Найти его хватает одного обратного обхода дерева. - [Сериализация / десериализация дерева (Tree serialize / deserialize)](https://algopath.pro/ru/patterns/tree-serialize) - O(n) Запишите дерево в одну плоскую строку и восстановите его точно таким же. Работает это за счёт меток отсутствующих потомков. ## Кучи и топ-k - [Бинарная куча / очередь с приоритетом (Binary heap / priority queue)](https://algopath.pro/ru/patterns/binary-heap) - O(log n) per op Куча держит наверху наименьшее значение, а больше ничего не упорядочивает вообще. Вставка и снятие стоят по log n каждая. ## Графы - [Обход графа BFS / DFS (Graph BFS / DFS)](https://algopath.pro/ru/patterns/graph-bfs-dfs) - O(V+E) Обходите граф от стартовой вершины, помечая всё уже увиденное. Очередь даёт кратчайший путь в рёбрах, а стек уходит вглубь. - [Компоненты связности (Connected components)](https://algopath.pro/ru/patterns/graph-components) - O(V+E) Начинайте новый обход в каждой ещё не увиденной вершине. Каждый реально начатый обход означает ещё одну связную группу графа. - [Топологическая сортировка (алгоритм Кана) (Topological sort (Kahn's algorithm))](https://algopath.pro/ru/patterns/topological-sort) - O(V+E) Расставьте задачи так, чтобы каждая шла после всех, от которых она зависит. Каждый раз берите вершину, которая никому не должна. - [Система непересекающихся множеств (Union-find (disjoint set))](https://algopath.pro/ru/patterns/union-find) - near O(1) per op Каждый элемент указывает на родителя, а подъём наверх приводит к корню, который называет группу. Элементы вместе, если корни совпали. - [Алгоритм Дейкстры (Dijkstra's algorithm)](https://algopath.pro/ru/patterns/dijkstra) - O(E log V) Закрывайте ближайшую незакрытую вершину и ослабляйте все её рёбра. Куча держит эту вершину всегда в одном чтении от вас. - [Эйлеров путь (алгоритм Хирхольцера) (Eulerian path (Hierholzer's algorithm))](https://algopath.pro/ru/patterns/eulerian-path) - O(E) Пройдите граф, использовав каждое ребро ровно один раз. Кладите вершину в стек, когда она застряла, а ответ читайте с конца. - [Проверка двудольности (раскраска в два цвета) (Bipartite check (two-coloring))](https://algopath.pro/ru/patterns/bipartite) - O(V+E) Покрасьте любую вершину, а потом покрасьте каждого её соседа в другой цвет. Конфликт доказывает, что граф не двудольный. ## Жадные алгоритмы - [Жадный алгоритм (обменный аргумент) (Greedy (exchange argument))](https://algopath.pro/ru/patterns/greedy) - O(n log n) Берите лучший на вид вариант прямо сейчас и никогда к нему не возвращайтесь. Работает это, только если есть доказательство. ## Динамическое программирование - [Динамическое программирование (1-D) (Dynamic programming (1-D))](https://algopath.pro/ru/patterns/dynamic-programming) - O(states) Ответьте на маленькую версию задачи, сохраните ответ и стройте из него следующий. Каждое состояние считается только один раз. - [DP над подпоследовательностями (LIS / LCS / расстояние редактирования) (DP on subsequences (LIS / LCS / edit distance))](https://algopath.pro/ru/patterns/dp-subsequence) - O(n^2)/O(nm) Состояние здесь это пара позиций, по одной в каждой последовательности. Каждая ячейка спрашивает, совпали ли эти элементы. - [DP на интервалах (DP on intervals)](https://algopath.pro/ru/patterns/dp-interval) - O(n^3) Состояние здесь это отрезок, а переход выбирает последний ход внутри него. Короткие отрезки всегда заполняются раньше длинных. - [DP на деревьях (DP on trees)](https://algopath.pro/ru/patterns/dp-on-trees) - O(n) Ответ каждого узла собирается из ответов его собственных потомков. Один обратный обход по дереву считает их все за проход. ## Строки и динамическое программирование - [DP на строках (word break) (DP on strings (word break))](https://algopath.pro/ru/patterns/dp-strings) - O(n^2) Режьте строку в каждой позиции и спрашивайте, годится ли получившийся кусок. Таблица достижимых позиций убирает повторы. ## Строки - [Trie (префиксное дерево) (Trie (prefix tree))](https://algopath.pro/ru/patterns/trie) - O(len) per op Слова с общим префиксом делят между собой один и тот же путь от корня. Поиск стоит ровно столько, какова длина этого слова. ## Битовые операции - [Битовые манипуляции (Bit manipulation)](https://algopath.pro/ru/patterns/bit-manipulation) - O(1)/O(n) Считайте целое число длинным рядом переключателей. Маски, сдвиги и XOR читают или переключают каждый из них прямо на месте. ## Математика и теория чисел - [Математика и теория чисел (НОД, решето, модульная арифметика) (Math and number theory (GCD, sieve, modular))](https://algopath.pro/ru/patterns/math-number-theory) - varies Теория чисел заменяет перебор всех значений обычной арифметикой. НОД, модульные правила и решето убирают полный перебор. ## Матрицы - [Обход матрицы (спираль / диагонали) (Matrix traversal (spiral / diagonal))](https://algopath.pro/ru/patterns/matrix-traversal) - O(mn) Обходите сетку в том порядке, которого обычные циклы не дают. Следующую клетку выбирают границы или правило направления. - [Поиск в матрице (отсортированная сетка) (Matrix search (sorted grid))](https://algopath.pro/ru/patterns/matrix-search) - O(m+n) В сетке, отсортированной в обе стороны, из угла есть только одно направление. Сравнение отбрасывает целый ряд или столбец. - [Поиск слова в матрице (DFS/backtracking по сетке) (Matrix word search (grid DFS/backtracking))](https://algopath.pro/ru/patterns/matrix-word-search) - O(mn*4^L) Ищите в сетке, шагая в соседа и потом возвращаясь обратно. Клетка помечена ровно столько времени, сколько вы внутри неё. ## Продвинутые темы - [Дерево Фенвика / дерево отрезков (Fenwick tree / segment tree)](https://algopath.pro/ru/patterns/fenwick-segment-tree) - O(log n) per op Дерево над отрезками отвечает на запрос и принимает изменение, и то и другое за log n. Префиксные суммы второго не умеют.