Учебная платформа AST-STUDY

← Назад к курсу

Структурированный набор "строительных блоков" (patterns) и тактик для алгоритмов на Python

В этом уроке содержится структурированный набор "строительных блоков" (patterns) и тактик как ключ к успеху на алгоритмических собеседованиях. Вот подробный список, сфокусированный на Python.

I. Основные мыслительные паттерны и тактики

1. Разбиение задачи на подзадачи (Decomposition)

  • Разбить строку по словам/предложениям: text.split(), re.split(r'[.!?]', text)
  • Разбить число на цифры: digits = [int(d) for d in str(n)]
  • Разбить интервал (например, для бинарного поиска): while left <= right: mid = (left + right) // 2
  • Разделяй и властвуй (Merge Sort, Quick Sort): Рекурсивно разбивай на половины.

2. Изменение порядка (Reversal)

  • Развернуть строку/массив: 
    s = s[::-1]  # Самый питонячий способ
reversed_s = ''.join(reversed(s))  # Итератор
arr.reverse()  # На месте для списка
  • Развернуть связанный список: Классическая задача с тремя указателями (prev, curr, next).
  • Использовать стек (LIFO) для обратного порядка: stack.append(); stack.pop().

3. Быстрые формулы (из математики/комбинаторики)

  • Сумма арифметической прогрессии 1..n: total = n * (n + 1) // 2
  • Количество пар из n элементов (рукопожатий): pairs = n * (n - 1) // 2
  • Сумма квадратов: 1^2 + 2^2 + ... + n^2 = n * (n + 1) * (2*n + 1) // 6
  • Проверка на чётность: if n & 1: ... (нечетное)
  • Последняя цифра: last_digit = n % 10
  • Целочисленное деление и остаток: div, mod = divmod(a, b)
  • Максимум/минимум без if: max_val = a if a > b else b или max(a, b)

4. Работа с индексами и "два указателя" (Two Pointers)

  • Встречные указатели (для палиндромов, суммы в отсортированном массиве): 
    left, right = 0, len(arr) - 1
while left < right:
    # логика
    left += 1
    right -= 1
  • Быстрый и медленный указатель (Floyd's Algorithm): 
    slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# slow в середине
  • Скользящее окно (фиксированное или переменное): 
    l = 0
for r in range(len(s)):
    # добавить s[r] в окно
    while условие_нарушено: # для переменного окна
        # убрать s[l] из окна
        l += 1
    # обновить ответ

5. Префиксные суммы и накопление

  • Быстрый ответ на сумму подмассива arr[i:j]: 
    prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
    prefix[i+1] = prefix[i] + arr[i]
sum_i_j = prefix[j] - prefix[i]  # O(1)!
  • Накопление для поиска максимума/минимума: "Какая максимальная прибыль к этому дню?"

6. Хэш-таблицы (словари) — "швейцарский нож"

  • Подсчёт частот: freq = {}; for x in items: freq[x] = freq.get(x, 0) + 1
  • Поиск пары/дубликата за O(1): if target - num in seen:
  • Группировка по ключу: from collections import defaultdict; groups = defaultdict(list)
  • Кэширование (мемоизация): @lru_cache(None) для рекурсии.

7. Множества (Sets)

  • Проверка на наличие за O(1): if x in seen_set:
  • Удаление дубликатов: unique = list(set(items)) (порядок теряется, можно dict.fromkeys).
  • Операции над множествами: union, intersection, difference.

8. Очереди и кучи (Priority Queues)

  • Очередь (FIFO) для BFS: from collections import deque; q = deque(); q.append(); q.popleft()
  • Очередь с приоритетом (куча, мини-куча по умолчанию): 
    import heapq
heap = []
heapq.heappush(heap, value)
min_val = heapq.heappop(heap)
# Для макси-кучи инвертируйте значения: heapq.heappush(heap, -value)

9. Сортировка и поиск

  • Сортировка — часто первый шаг: arr.sort() (in-place) или sorted_arr = sorted(arr)
  • Свои ключи сортировки: arr.sort(key=lambda x: (x[1], -x[0]))
  • Бинарный поиск по ответу (не по массиву): "Найти минимальное значение, удовлетворяющее условию".

10. Рекурсия и Backtracking

  • Шаблон backtracking: 
    def backtrack(path, choices):
    if условие_успеха:
        результат.append(path[:])  # КОПИЯ!
        return
    for choice in choices:
        if choice is valid:
            path.append(choice)
            backtrack(path, new_choices)
            path.pop()  # откат!

II. Полезные "хитрости" на Python

  • enumerate: for i, val in enumerate(arr):
  • zip: for a, b in zip(list1, list2):
  • any/all: if any(x > 0 for x in list):
  • Срезы (slicing): arr[2:5], arr[::2], arr[::-1]
  • Генераторы списков/словарей/множеств: [x*2 for x in range(10) if x%2==0]
  • math и itertools — твои друзья: 
    import math
math.gcd(a, b), math.ceil(x), math.floor(x), math.isqrt(n) # (Python 3.8+)

    import itertools
# permutations, combinations, accumulate, groupby

III. План атаки на задачу

  1. Уточнить условие: Задай вопросы. Крайние случаи? Входные размеры?
  2. Придумать наивное решение (Brute Force): Сначала работающее, потом оптимизируй.
  3. Искать паттерн/строительный блок: Какая структура данных или алгоритм здесь спрятаны? (Часто в условии есть подсказки: "отсортировано", "O(1) времени", "без дубликатов").
  4. Оценить сложность: Время (O(n^2) -> плохо), Память (O(n) -> обычно ок).
  5. Написать код: Чисто, с понятными переменными. Комментируй ключевые моменты.
  6. Протестировать на примерах: Сначала на данных из условия, потом на краях (n=0, n=1, пустой ввод, огромные числа, отрицательные).

IV. Для повторения перед собеседованием

Составь для себя "Чек-лист тем" и прогони по 1-2 ключевые задачи на каждый блок:

  1. Массивы/строки: Two Pointers, Sliding Window, Prefix Sum.
  2. Хэш-таблицы: Поиск пары, группировка.
  3. Связные списки: Разворот, Floyd's Algorithm.
  4. ️Деревья: Обходы (DFS, BFS), рекурсия.
  5. Графы: Поиск в ширину/глубину, топологическая сортировка.
  6. Динамическое программирование: Fibonacci, рюкзак, наибольшая подпоследовательность.
  7. Сортировка и поиск: Binary Search, Kth Largest.
  8. Кучи: K-way merge, K самых частых элементов.

Главный совет: Не пытайся заучить 1000 задач. Пойми 100 паттернов. На собеседовании сведи новую задачу к известному паттерну, используя эти строительные блоки. Удачи