AlgoDS
Поиск

Ищите по-русски или по-английски.

    Меню

    Паттерны задач: как выбрать подход

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

    Пять вопросов перед выбором паттерна

    1. Что ищем? Пару, непрерывный фрагмент, путь, количество способов или лучший вариант? Подмассив сохраняет непрерывность, подпоследовательность может пропускать элементы.
    2. Какие свойства гарантированы? Порядок, знак чисел, модель весов, возможность менять вход. Слово «массив» само по себе не выбирает алгоритм.
    3. Что делает перебор? Назовите кандидатов и повторную работу: поиск в префиксе, пересчёт диапазона или одинаковую остаточную подзадачу.
    4. Какое состояние достаточно? Границы, частоты, visited, минимум в куче или ответ DP. Запишите инвариант до реализации.
    5. Что опровергает идею? Постройте маленький контрпример и оцените время и память через Big O до усложнения кода.

    Техники сочетаются: префиксная сумма даёт значение диапазона, а хеш-таблица хранит частоты уже встреченных префиксов. Поэтому ниже ориентиры для проверки гипотез, а не правило «одно ключевое слово — один шаблон».

    Два указателя

    Признак задачи: Можно безопасно сдвигать одну из границ состояния.

    Когда подходит
    Данные упорядочены, а сравнение позволяет доказать, что одна граница больше не участвует в ответе. Сначала сформулируйте, какие кандидаты сохраняются после каждого сдвига.
    Когда не подходит
    На произвольном массиве увеличение левого значения не обязано увеличивать сумму. Сортировка тоже не всегда допустима: она меняет порядок и требует сохранить индексы, если ответу нужны исходные позиции.
    Проверьте на примере
    Для пары с заданной суммой в отсортированном массиве слишком малая сумма исключает текущий левый элемент. В несортированном массиве такое исключение неверно; рассмотрите множество или сортировку с учётом контракта.
    Стоимость
    Если каждый указатель движется только вперёд или внутрь диапазона, суммарное время O(n), память O(1).

    Скользящее окно

    Признак задачи: Ответ относится к непрерывному фрагменту с ремонтируемым инвариантом.

    Когда подходит
    Ищется непрерывный фрагмент, состояние обновляется при добавлении справа и удалении слева, а нарушение можно исправить движением левой границы без потери ответа.
    Когда не подходит
    Одного слова «подмассив» недостаточно. Для суммы с отрицательными числами стандартное сжатие окна по слишком большой сумме теряет монотонность. Проверяйте именно условие допустимости.
    Проверьте на примере
    В строке без повторов новый дубликат указывает, какую левую часть удалить. Для подсчёта подмассивов с точной суммой и произвольными знаками полезнее рассмотреть префиксные суммы вместе с хешированием.
    Стоимость
    O(n) движений границ. Для окна уникальности с хеш-таблицей ожидаемое время O(n), память O(u), где u — число разных просмотренных символов; обновление состояния должно быть дешёвым.

    Префиксная сумма

    Признак задачи: Нужны суммы или счётчики многих диапазонов.

    Когда подходит
    Много запросов суммы или количества на неизменяемых диапазонах. Одна подготовка позволяет получать ответ как разность двух префиксов, включая пустой префикс.
    Когда не подходит
    Частые изменения элементов делают обычные префиксы дорогими: приходится пересчитывать последующие значения. Минимум диапазона нельзя получить простой разностью минимумов префиксов.
    Проверьте на примере
    Для суммы на [l, r) вычислите prefix[r] − prefix[l]. Зафиксируйте полуинтервальные границы до кода и проверьте l = 0, пустой диапазон и r = n.
    Стоимость
    Построение O(n) времени и O(n) памяти; запрос суммы или счётчика полуинтервала после подготовки — O(1).

    Хеширование

    Признак задачи: Повторяется проверка наличия, частоты или соответствия.

    Когда подходит
    Повторяется вопрос «видели ли раньше?», нужен счётчик частот или соответствие ключа значению. Сохраняйте именно информацию, которая нужна следующим шагам, а не всю историю поиска.
    Когда не подходит
    Хеш-таблица не поддерживает упорядоченные соседства и сама по себе не даёт гарантированного O(1) в худшем случае. Для длинных ключей нужно учитывать стоимость хеширования и сравнения.
    Проверьте на примере
    Проверяя дубликаты, сначала спросите, есть ли значение в seen, и только затем вставьте его. Если вставить раньше, каждый элемент ошибочно станет собственным повтором.
    Стоимость
    Для ключей постоянного размера поиск и удаление ожидаемо O(1), вставка ожидаемо амортизированно O(1). Отдельная операция в худшем случае O(n) из-за коллизий или расширения; память O(n).

    Стек

    Признак задачи: Нужно обработать последнюю незавершённую сущность.

    Когда подходит
    Следующий шаг должен обработать последнюю незавершённую сущность: открытую скобку, вложенный контекст или отложенного кандидата. Это порядок LIFO.
    Когда не подходит
    Если первым должен обрабатываться самый ранний обнаруженный элемент, нужна очередь. Для ближайшего большего значения потребуется ещё и доказанный монотонный порядок кандидатов, а не просто стек.
    Проверьте на примере
    Закрывающая скобка должна соответствовать вершине стека. Проверяйте пустоту до чтения, тип пары при удалении и отсутствие незакрытых скобок в конце.
    Стоимость
    Чтение вершины и pop с конца — O(1); push в стек поверх динамического массива амортизированно O(1), отдельное расширение — O(n); память O(n).

    Куча

    Признак задачи: Нужно многократно получать текущий минимум или максимум.

    Когда подходит
    Нужно многократно извлекать текущий минимум или максимум, а кандидаты поступают или меняются между извлечениями. Для Top K можно удерживать лишь ограниченный набор лучших.
    Когда не подходит
    Если нужен полный порядок одного неизменного набора, сортировка может быть проще. Куча не ускоряет произвольный поиск и не делает любой соседний элемент массива следующим по величине.
    Проверьте на примере
    Минимум находится в корне, но брать второй элемент массива как второй минимум нельзя. После извлечения восстановите инвариант. В C++ priority_queue по умолчанию max-heap, обычные операции Python heapq используют min-heap.
    Стоимость
    В двоичной куче вершина O(1), просеивание O(log n), построение O(n), память O(n). Для кучи на растущем массиве вставка амортизированно O(log n), отдельное расширение может стоить O(n).

    BFS — поиск в ширину

    Признак задачи: Сущности соединены произвольными отношениями или переходами.

    Когда подходит
    Нужен путь с минимальным числом рёбер в невзвешенном графе или слоями распространяется состояние. Все источники multi-source BFS начинаются на расстоянии 0.
    Когда не подходит
    Обычная очередь BFS не учитывает разные веса рёбер. Для неотрицательных разных весов изучите Дейкстру; отрицательные веса требуют другого алгоритма и отдельного анализа.
    Проверьте на примере
    Помечайте вершину при добавлении в очередь: тогда несколько соседей не добавят её повторно. Первый слой — источники, каждый следующий добавляет одно ребро к расстоянию.
    Стоимость
    Для списков смежности полный обход O(V + E) времени и O(V) дополнительной памяти. Хранение самого графа O(V + E) считается отдельно.

    DFS — поиск в глубину

    Признак задачи: Сущности соединены произвольными отношениями или переходами.

    Когда подходит
    Нужно исследовать достижимость, компоненты или структуру переходов, продолжая одну ветвь до возврата. В несвязном графе внешний цикл запускает обход из каждой ещё не посещённой вершины.
    Когда не подходит
    Первый найденный DFS путь не обязательно кратчайший. Проверка циклов зависит от ориентированности графа; правило пропуска родителя нельзя бездумно переносить на ориентированный граф.
    Проверьте на примере
    Visited устанавливается до переходов, иначе цикл приведёт к повторным вызовам. На длинной цепочке глубина рекурсии растёт до V: в Python учитывайте предел рекурсии, при необходимости используйте явный стек.
    Стоимость
    Для списков смежности O(V + E) времени и O(V) дополнительной памяти с visited и стеком; память представления графа учитывается отдельно.

    Жадный выбор

    Признак задачи: Локальный выбор можно доказуемо включить в оптимальное решение.

    Когда подходит
    Локальный выбор можно доказуемо включить в оптимальное решение. Попробуйте обменный аргумент: заменить первый выбор оптимального решения своим так, чтобы ответ не ухудшился.
    Когда не подходит
    «Возьму самый большой» — гипотеза, а не доказательство. Для монет произвольных номиналов жадный выбор может быть неверным, хотя работает на некоторых наборах.
    Проверьте на примере
    Для монет 1, 3, 4 и суммы 6 выбор 4 даёт три монеты (4 + 1 + 1), а 3 + 3 — две. Если выбор нельзя доказать, вернитесь к полному перебору и ищите состояние DP.
    Стоимость
    Цена зависит от выбора кандидата; типичная схема с предварительной сортировкой занимает O(n log n) времени.

    Бэктрекинг

    Признак задачи: Нужно исследовать выборы, отменяя изменения состояния.

    Когда подходит
    Нужно построить варианты последовательностью выборов, ограничения отсекают часть ветвей, а изменения состояния можно отменить перед соседней ветвью.
    Когда не подходит
    При больших размерах полный перебор остаётся непригодным даже с несколькими отсечениями. Если важен лишь оптимальный ответ и повторяются одинаковые остаточные задачи, проверьте возможность мемоизации.
    Проверьте на примере
    Строя комбинацию, добавьте выбранный элемент, исследуйте продолжение и удалите его перед следующим выбором. Без отката состояние соседних ветвей смешается.
    Стоимость
    Грубая верхняя оценка числа узлов O(b^d) для b > 1 и глубины d; добавьте стоимость обработки узла и выдачи ответов. Стек и текущий путь обычно O(d), сохранённые ответы считаются отдельно.

    Динамическое программирование

    Признак задачи: Подзадачи перекрываются, а ответ определяется малым состоянием.

    Когда подходит
    Разные пути перебора приходят к одной остаточной задаче, а её ответ определяется компактным состоянием. Сформулируйте вопрос ячейки, базы, переходы и порядок зависимостей.
    Когда не подходит
    Если ключ пропускает важную часть истории, объединять подзадачи нельзя. Если состояний слишком много или они не повторяются, таблица не решит проблему сложности автоматически.
    Проверьте на примере
    Для лестницы с шагами 1 и 2 остаток r задаёт вопрос «сколько способов завершить путь?». База r = 0 даёт один пустой способ; одинаковые остатки нужно вычислять один раз.
    Стоимость
    Время обычно равно числу достижимых состояний, умноженному на число переходов; память — числу хранимых состояний.

    Как тренировать распознавание

    Сначала решите задачу с известной техникой. Затем закройте название и сформулируйте свойства задачи своими словами. Сравните две гипотезы, найдите контрпример к слабой и объясните инвариант сильной. Если вы узнали знакомый сюжет, это ещё не проверка нового условия.

    Используйте практику с разбором, переносом и самостоятельным режимом, а затем LeetCode 75, сопоставленный урокам. После решения записывайте, какой признак был решающим и на каком изменении условия алгоритм перестаёт работать.

    Для первого прохода следуйте порядку курса. Для подготовки к интервью откройте маршрут подготовки и повторения. Глубокий разбор выбора техники есть в уроке «Диагностика задачи без названия паттерна».