Шаблоны (паттерны) решения задач по Структурами данных и алгоритмам (Data Structures and Algorithms / DSA)
(продолжение предыдущего поста)

1. Array / String Inputs (Массивы / строки):

1. Отсортирован ли массив?
→ Использовать бинарный поиск, два указателя или префиксные суммы.
2. Задачи оптимизации (максимум/минимум/подмассив)?
→ Подумать о скользящем окне, динамическом программировании или жадных алгоритмах.
3. Поиск дубликатов, подсчёта или частот?
→ Использовать HashMap, HashSet или массив для подсчёта.
4. Нужны подстроки или подмассивы фиксированного размера?
→ Применить скользящее окно с двумя указателями.
5. Часто встречающиеся минимум/максимум в окне?
→ Использовать монотонную очередь, deque или кучу.
6. Генерация подмножеств, перестановок, комбинаций?
→ Использовать обратный ход (backtracking).
7. Сопоставление или разбор символов?
→ Использовать стек, особенно для сбалансированных скобок, инфиксной/постфиксной записи.

2. Graph Inputs (Графы):

1. Кратчайший путь в невзвешенном графе?
→ Использовать поиск в ширину (BFS).
2. Кратчайший путь в взвешенном графе?
→ Использовать алгоритм Дейкстры, Беллмана-Форда или A*.
3. Связные компоненты / обнаружение циклов?
→ Использовать DFS или Union-Find (DSU).
4. Топологическая сортировка?
→ Использовать алгоритм Кана или DFS с набором посещённых вершин.
5. Оптимизация, например, MST (минимальное остовное дерево)?
→ Использовать алгоритмы Крускала или Прима.

3. Linked List Inputs (Связанные списки):

1. Обнаружение циклов?
→ Использовать «медленный и быстрый указатели» (алгоритм Флойда).
2. Перевороты или частичные изменения?
→ Использовать жонглирование указателями: prev, curr, next.
3. Пересечение или средний узел?
→ Использовать два указателя.

4. Tree Inputs (Часто бинарные деревья):

1. Обходы?
→ Использовать inorder, preorder, postorder или обход по уровням (BFS).
2. Проверка сбалансированности или расчёт диаметра?
→ Использовать postorder + расчёт высоты.
3. Наименьший общий предок?
→ Использовать рекурсивный DFS или карту родителей + набор предков.

5. Dynamic Programming Use-Cases (Случаи применения динамического программирования):

1. Оптимальный выбор / перекрывающиеся подзадачи?
→ Использовать ДП с мемоизацией (сверху вниз) или табуляцией (снизу вверх).
2. Задачи типа «подмножество» или "knapsack"?
→ Использовать 1D/2D массивы ДП.
3. Сопоставление строк или редактирование?
→ Использовать матрицу ДП (например, расстояние редактирования, LCS).