Уровень над алгоритмами: по формулировке условия понять, какой приём здесь работает. «Отсортированный массив», «подряд идущие элементы», «ближайший больший справа» — каждая такая фраза указывает на конкретное семейство решений.
Ключевые тезисы
- Решение начинается не с кода, а с классификации: сигнал в условии → семейство приёмов → конкретный вариант.
- Ограничения на размер входа называют требуемую сложность: n ≤ 20 — перебор подмножеств, n ≤ 10⁵ — O(n log n), n ≤ 10¹⁸ — логарифм или формула.
- Почти каждый приём отвечает на один вопрос: что наивный перебор считает второй раз.
Какую задачу решает
На алгоритмической секции проваливаются не потому, что не знают, как устроен . Проваливаются потому, что не видят, что перед ними бинарный поиск. Знание приёмов и умение их узнавать — разные навыки, и второй почти никогда не тренируют отдельно.
Между тем распознавание устроено довольно механически. Условия задач пишут людям и похожими словами: «подряд идущие», «ближайший больший», «минимальное значение, при котором», «сколькими способами». За каждой такой формулировкой стоит небольшое семейство приёмов, и первая гипотеза о решении строится за полминуты, а не за десять.
Второй источник подсказок — ограничения. Размер входа в условии стоит не для красоты: он прямо называет допустимую сложность, а значит и класс решений. И третий, самый общий приём: написать честный перебор и спросить, что он считает второй раз. Повторное сложение отрезка снимается префиксными суммами, повторный поиск — хеш-таблицей, повторное решение подзадачи — динамикой. Почти вся глава — ответы на этот один вопрос.
«Дан массив до 10⁵ целых чисел, возможно отрицательных. Найдите количество подотрезков с суммой ровно k». Разбор по шагам. Ищем количество, а не сам отрезок. Ограничение 10⁵ исключает квадрат: нужен один проход или логарифм. Слово «подотрезок» — сигнал на , но рядом стоит «возможно отрицательных», а это прямой запрет: окно требует монотонности суммы. Остаются префиксные суммы, и формулировка «сумма равна k» переписывается как «префиксная сумма в левой границе равна текущей минус k» — то есть узнавание уже встреченного значения, а это . Решение названо целиком до написания первой строки кода, и всё, что для этого потребовалось, — три сигнала из условия.
Подробный разбор
Условия задач пишут люди, и пишут их похожими словами. Ниже — прямое соответствие между формулировкой и приёмом. Таблица не заменяет понимания, но задаёт первую гипотезу, а дальше остаётся проверить применимость.
| Сигнал в условии | Паттерн |
|---|---|
| Отсортированный массив, найти элемент или позицию | бинарный поиск |
| «Минимальное значение, при котором получается», ответ проверяется быстро | бинарный поиск по ответу |
| Подряд идущие элементы плюс ограничение | скользящее окно |
| Пара с заданной суммой в отсортированном массиве | встречные указатели |
| Цикл, середина списка, k-й с конца | быстрый и медленный указатель |
| Много запросов суммы на отрезках | префиксные суммы |
| «Сколько подотрезков с суммой k» | префикс плюс хеш-таблица |
| «Встречалось ли раньше», «сколько раз встречается» | хеш-таблица |
| Сгруппировать похожие (анаграммы, дубликаты) | хеш-таблица по канонической форме |
| Правильные скобки, вложенность, откат к последнему | стек |
| «Ближайший больший справа» | монотонный стек |
| Максимум внутри | дек |
| по числу шагов, «минимум переходов» | обход в ширину |
| Связность, компоненты, все пути, перебор с возвратом | обход в глубину |
| Зависимости, порядок выполнения, «сначала это, потом то» | топологическая сортировка |
| Пути с весами | Дейкстра и её родня |
| «Сколькими способами», «максимальная выгода при выборе» | динамика |
| Максимум непересекающихся, минимум ресурсов | жадность |
| k-й по величине, топ-k | порядковые статистики или куча |
Сигналы не взаимоисключающие, и это нормально: у задачи бывает два решения — например, через и через префиксы. Важно назвать хотя бы одно семейство за первые полминуты, а не перебирать приёмы вслепую.
Ограничение на пишут не для красоты: оно отсекает целые классы решений. Ориентир — порядка простых операций в секунду; отсюда таблица, которую стоит держать в голове целиком.
| Размер входа | Допустимая сложность | Что обычно имеется в виду |
|---|---|---|
| перебор перестановок | ||
| перебор подмножеств, динамика по маскам | ||
| динамика на парах, Флойд — Уоршелл | ||
| двумерная динамика, перебор пар | ||
| , , , дерево | ||
| один проход: , префиксы, | ||
| поиск по ответу, математика, быстрое возведение в степень |
Таблица читается в обе стороны. Если придуманное решение на порядок медленнее допустимого, значит выбран не тот паттерн — и оптимизировать его бессмысленно, нужно возвращаться к постановке. Если решение заметно быстрее необходимого, вы, возможно, пишете лишнее.
Отдельный сигнал — маленькое при пугающей формулировке. почти всегда означает перебор по подмножествам: полиномиального решения у задачи может не существовать, и искать его — потерянное время.
- Переформулировать условие одной фразой: что ищем — число, отрезок, порядок, путь, подмножество.
- Посмотреть на ограничения и назвать целевую сложность.
- Проговорить честный перебор и его сложность: это и опорная точка, и запасной ответ.
- Найти, что перебор пересчитывает зря.
- Назвать паттерн и проверить условия его применимости: отсортированность, монотонность, знак значений.
- Разобрать один маленький пример руками — до написания кода.
Четвёртый шаг — содержание всей главы. Почти каждый приём отвечает на вопрос «что здесь считается второй раз» и убирает ровно этот повтор.
| Что перебор делает повторно | Приём |
|---|---|
| Складывает один и тот же отрезок | префиксные суммы |
| Ищет элемент линейным проходом | хеш-таблица |
| Решает одну и ту же подзадачу | динамика или мемоизация |
| Проверяет все пары на отсортированных данных | два указателя |
| Для каждого элемента ищет ближайший подходящий | монотонный стек |
| Перебирает значения ответа подряд | бинарный поиск по ответу |
| Каждый раз заново ищет минимум | куча |
Шестой шаг выглядит необязательным и экономит больше всего времени. Пример на четырёх элементах, разобранный руками, ловит перепутанные границы и забытый случай пустого входа до того, как они станут падающим тестом.
- Подпоследовательность — не подотрезок. Слово «подряд» решает, это или динамика; без него окно неприменимо в принципе.
- «Отсортированный» бывает приманкой. Если по данным всё равно нужен полный проход, порядок ничего не даёт.
- Сумма и отрицательные числа. требует неотрицательности, префиксные суммы — нет.
- Кратчайший путь с весами — не обход в ширину. считает шаги, а не стоимость; с весами нужен .
- «Максимум» или «минимум» ещё не означает жадность. Сначала аргумент обмена, потом код.
- Хеш-таблица не хранит порядок. Если в ответе нужен порядок или диапазон, нужна не она, а дерево или .
Последняя проверка перед кодом — назвать граничные случаи: пустой вход, один элемент, все элементы одинаковые, все отрицательные, дубликаты, переполнение целого типа. На секции алгоритмов ошибаются на них чаще, чем на выборе алгоритма.
Если распознать паттерн не удалось за несколько минут, работает запасной ход: написать честный перебор и вслух назвать его сложность. Рабочее медленное решение — это результат, от которого можно отталкиваться; пустой экран результатом не является.
Где применяется
- Алгоритмическая секцияНазвать семейство решения в первые минуты, а не перебирать приёмы вслепую.
- Ревью кодаУвидеть в чужом цикле скрытый квадрат и знать, чем он снимается.
- Оптимизация Понять, что именно пересчитывается зря, до того как переписывать.
- ПодготовкаРазбор задач по паттернам, а не по номерам: сто задач превращаются в десять схем.
Плюсы, минусы и альтернативы
Брать, если
- Задача новая, а времени на перебор всех приёмов нет.
- Решение придумалось, но не укладывается в ограничения — значит выбран не тот паттерн.
Не брать, если
- Задача прикладная и упирается не в алгоритм, а в устройство данных или в железо.
- Паттерн опознан, но условия применимости не проверены — тогда это не распознавание, а угадывание.
Чем заменяют
Видеолекции
Тайм-кода именно на эту тему в записях нет. Но глава «Алгоритмы и структуры данных» разобрана в курсе целиком — с той оговоркой, что место в записи придётся искать самому.
Связанные темы
Алгоритмическое мышление
Time and Space Complexity85%
Асимптотическая сложность · Алгоритмы и структуры данныхСпособ сравнить алгоритмы, не запуская их: как растёт время работы с ростом входа. Отбрасывает константы и оставляет то, что решает на больших данных.
Recursion and Divide and Conquer85%
Рекурсия и разделяй-и-властвуй · Алгоритмы и структуры данныхЗадача сводится к таким же задачам меньшего размера. Основа сортировки слиянием, быстрой сортировки, обхода деревьев и почти всей динамики.
Dynamic Programming85%
Динамическое программирование · Алгоритмы и структуры данныхПеребор, в котором каждое подсостояние считается ровно один раз. Превращает экспоненциальный перебор в полиномиальный, если подзадачи перекрываются.
Greedy Algorithms85%
Жадные алгоритмы · Алгоритмы и структуры данныхНа каждом шаге берём локально лучший вариант и не пересматриваем решение. Работает не всегда — но когда работает, проще и быстрее динамики.
Binary Search85%
Бинарный поиск · Алгоритмы и структуры данныхПоловинное деление на отсортированных данных: за логарифм шагов вместо линейного перебора. Приём шире поиска — им ищут ответ в любой монотонной задаче.
Всё, что названо в описании, разобрано здесь же или в соседней теме — переходы под каждым определением.
Сигнал условия
Фраза в постановке, за которой стоит конкретное семейство приёмов.
Разбор ниже: Словарь сигналовОграничения как требование
Размер входа называет допустимую сложность: n ≤ 20 — перебор масок, n ≤ 10⁵ — логарифм.
Разбор ниже: Ограничения называют сложностьОпорный перебор
Честное медленное решение: точка отсчёта, запасной ответ и источник идеи.
Разбор ниже: Порядок разбора задачиПовторный счёт
Что перебор считает второй раз — то и убирает приём.
Разбор ниже: Порядок разбора задачиЛожный сигнал
«Отсортированный», «максимум», «кратчайший» — слова, которые ведут не туда.
Разбор ниже: Ложные сигналыТема встречается в тесте по направлениям — ошибки приведут обратно на эту страницу.
Глава «Алгоритмы и структуры данных» последний раз правилась . Нашли ошибку — напишите.