Максим Байтович – Алгоритмическое мышление: От структур данных к паттернам решения задач (страница 1)

Алгоритмическое мышление: От структур данных к паттернам решения задач

Введение: Почему паттерны?

Представьте, что вы учитесь играть в шахматы. Можно заучить, как ходит каждая фигура — это синтаксис языка. Но чтобы выигрывать, нужно знать дебюты, связки, вилки и эндшпили. В программировании всё точно так же.

Большинство разработчиков застревают на алгоритмических собеседованиях или при решении сложных задач не потому, что они плохо знают Python или Java. Они застревают, потому что пытаются изобрести велосипед за тридцать минут, не зная, что задача уже решена десятки раз с помощью определённого паттерна.

Эта книга не учит синтаксису. Она учит узнавать врага в лицо. Мы берём сырую задачу и учимся препарировать её, задавая правильные вопросы.

Данные линейные или иерархические? Нужно перебрать все варианты или можно жадно выбрать лучший? Зависит ли текущий шаг от предыдущих? Ответив на эти вопросы, вы сужаете пространство поиска до двух-трёх паттернов, а дальше — дело техники.

Мы разобьём материал на три логических блока. Инструменты — идеальные формы хранения данных, фундамент, без которого невозможно говорить об алгоритмах. Методы — базовые операции вроде поиска и сортировки, кирпичики, из которых строятся решения. Паттерны — двадцать классических сценариев, покрывающих девяносто процентов задач на Leetcode, от скользящего окна до динамического программирования.

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

К концу книги у вас в голове сформируется дерево решений. Вы увидите задачу — и почти сразу поймёте, к какому паттерну она относится. Это и есть алгоритмическое мышление.

Часть I. Инструментарий: Данные в идеальной форме

Прежде чем применять паттерны, нужно понимать, с каким материалом мы работаем. Каждая структура данных — это не просто способ сложить байтики. Это философия доступа. Выбор правильной структуры часто решает задачу ещё до того, как вы написали первую строчку кода.

Глава 1. Массивы и строки: Линейный порядок

Массив — это непрерывный блок памяти, где каждый элемент сидит в своей ячейке, а ячейки пронумерованы по порядку. Если компьютерная память — это улица, то массив — дом с квартирами ноль, один, два, три.

Главная суперсила массива: зная адрес начала и номер элемента, вы попадаете в него мгновенно, за O(1). Это называется произвольный доступ. Вам не нужно проходить через первые пятьдесят квартир, чтобы попасть в пятьдесят первую.

Массивы бывают статическими и динамическими. Статический имеет фиксированный размер при создании — выделили память под сто элементов, и больше ни байтом. Динамический может расти: когда место заканчивается, он выделяет новый кусок памяти вдвое больше, копирует всё туда, и освобождает старый. Такое копирование случается всё реже по мере роста, и в среднем вставка в конец остаётся O(1). Это называется амортизированная сложность.

Базовые операции и их цена. Доступ по индексу — O(1), это суперсила. Поиск значения — O(N), если массив не отсортирован, приходится проверять каждый элемент. Вставка или удаление в конце — O(1). Вставка или удаление в начале или середине — O(N), потому что нужно сдвинуть всех соседей.

Строка — это, по сути, массив символов. Все операции над массивами применимы и к строкам, но с одной важной оговоркой: в большинстве языков строки иммутабельны. Операция s = s + "!" не меняет старую строку, а создаёт новую. Построение строки в цикле через конкатенацию даёт O(N²). Всегда используйте StringBuilder или его аналоги для аккумуляции.

Полезный инструмент при работе с массивами — префиксные суммы. Это массив, где каждый элемент хранит сумму всех предыдущих. Строится за O(N): pref[0] = arr[0], затем pref[i] = pref[i-1] + arr[i]. После этого любой запрос «сумма на отрезке от L до R» выполняется за O(1): pref[R] - pref[L-1]. Это не просто трюк, это паттерн мышления — предподсчёт для мгновенных ответов.

Пример. Дан массив цен на акции за несколько дней. Нужно отвечать на множество запросов: «какова средняя цена с дня L по день R?» Предподсчитываем префиксные суммы, и каждый запрос — это одна операция вычитания и деления.

Ещё один инструмент — скользящее окно, но это уже полноценный паттерн, и мы разберём его в отдельной главе.

Сигналы, что нужно использовать массив: данные однотипны и их количество известно или меняется редко, нужен частый доступ по индексу, порядок элементов важен, задача про последовательность или соседей или окно. Сигналы, что массив неудобен: частые вставки или удаления в середину — смотрите на связный список; постоянный поиск «есть ли элемент?» — смотрите на хеш-таблицу; нужен доступ к самому большому или самому маленькому — смотрите на кучу.

Глава 2. Связные списки: Гибкость через указатели

Связный список — это цепочка узлов, разбросанных по памяти. Каждый узел хранит данные и ссылку на следующего соседа. В двусвязном списке — ещё и на предыдущего. Нет сплошного куска памяти. Нет произвольного доступа.

Представьте поезд. Вы можете легко отцепить вагон в середине и вставить новый, просто перецепив сцепки. Но чтобы попасть из локомотива в десятый вагон, вам придётся пройти через все девять предыдущих. Телепорта нет. В этом и заключается философия связного списка: гибкость вставки и удаления ценой потери мгновенного доступа.

Типы списков. Односвязный: каждый узел знает только про следующий, движение только вперёд. Двусвязный: каждый узел знает про следующий и предыдущий, можно двигаться в обе стороны. Кольцевой: последний узел ссылается на первый, нет естественного конца.

Базовые операции и их цена. Доступ по индексу — O(N), это ахиллесова пята. Поиск значения — тоже O(N). Вставка или удаление в начало — O(1), это суперсила. Вставка или удаление в середине — O(1), если узел уже у вас в руках, но поиск этого узла стоит O(N). Вставка или удаление в конце — O(1), если есть хвостовой указатель, иначе O(N).

Главный дзен всех операций над списками — перенаправление указателей. Не нужно двигать данные, только менять адреса в полях next и prev. Удаление узла B из цепочки A стрелка B стрелка C: A.next = C. В двусвязном ещё C.prev = A. Узел B отсоединён. Вставка узла X между A и B: X.next = B, затем A.next = X. Критический порядок действий: если сначала сделать A.next = X, вы потеряете ссылку на B. Поэтому всегда сначала сохраняем хвост, потом рвём связь.

Полезная техника — фиктивный узел, или Dummy Node. Голова списка — особый случай: у неё нет предыдущего узла. Чтобы не писать для неё отдельную логику, создают фиктивный узел перед головой. В конце просто возвращают dummy.next. Это как пришить временный локомотив, чтобы все вагоны обрабатывались одинаково.

Пример. Дано: односвязный список 1 -> 2 -> 3 -> 4 -> 5. Нужно развернуть его. Решение: проходим по списку, на каждом шаге запоминаем следующий узел, перенаправляем текущий на предыдущий, сдвигаем указатели. После цикла бывшая голова стала хвостом, бывший хвост — головой. Результат: 5 -> 4 -> 3 -> 2 -> 1.

Другой пример. Нужно удалить N-й узел с конца списка за один проход. Заводим два указателя, оба на голову. Первый сдвигаем на N шагов вперёд. Затем оба двигаем шаг за шагом, пока первый не дойдёт до конца. Второй окажется ровно на N-м узле с конца. Удаляем его, перецепив ссылку.

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

Глава 3. Стек и очередь: Дисциплина доступа

Стек и очередь — это не столько структуры данных, сколько дисциплины доступа. Они определяют не то, как данные хранятся, а то, в каком порядке они извлекаются. Реализовать их можно и на массиве, и на связном списке.