Александр Чепайкин
Senior Developer в крупном финтехе. С 2012 года в IT, участвовал в разработке мобильных приложений, игр и сложных распределенных систем. Несколько лет работал удаленно в крупных стартапах Кремниевой долины.
Эта статья содержит список и краткое описание алгоритмов и оценки сложности алгоритмов.
Я не преследую цель дать всю исчерпывающую информацию в одной статье. Одна статья не заменит полноценного обучения так что читайте книги например Грокаем алгоритмы (Адитья Бхаргава).
Если вы нанимаете, и готовы рассмотреть хорошего Junior+/Middle Python Backend, напишите мне в Telegram. Я учу людей программировать, а не просто проходить собеседования. Даже если прямо сейчас у вас нет вакансии, в будущем у вас появится потребность в хорошем Junior+, который готов к самостоятельной работе и может быстро расти до уровня Middle. Посмотрите как я обучаю, если у вас есть сомнения.
ВАЖНО: Нет смысла решеать задачи, не зная основные структуры данных, и как правильно оценивать сложность алгоритмов. Поэтому сначала изучаем внимательно то, что описано в статье + структуры данных из этой статьи.
Используйте содержание и кнопку НАВЕРХ для удобства навигации по статье. Ваш голос за статью - лучшая благодарность автору и мотивация для меня.
Содержание
Популярные подходы к решению алгоритмических задач
Задачи для подготовки к алгоритмическому собеседованию в Яндекс
Как проходят алгоритмические собеседования
Алгоритмическая секция – обязательный этап собеседования для разработчиков в такие компании как Яндекс, где проверяют умение писать чистый код и находить оптимальные решения.
Как проходит алгоритмическая секция?
Длительность – 1 час, из которых 30–40 минут отводится на решение задач.
ВАЖНО: Перед тем как писать код, сначала вам нужно будет объяснить, как будете решать, и какая сложность по времени и по памяти у вашего решения. Тут важно задавать вопросы по возможным входным данным, ограничениях и пограничных случаях.
Первая задача – простая, решается одним-двумя проходами по массиву (например, поиск наибольшего неубывающего подотрезка). Главное – объяснить алгоритм, оценить сложность и написать чистый код.
Вторая задача – сложнее, требует знания структур данных (деревья, хэш-таблицы и т.д.). Частая проблема – нехватка времени.
Иногда дают третью задачу – сложную, но её можно решить без кода, только обсуждая подход.
Пока кандидат пишет решение, собеседующий следит и задаёт вопросы, а в конце даёт пару минут на перепроверку.
Как подготовиться?
Изучить основные структуры данных.
Изучите популярные алгоритмы. Не ограничивайтесь этой статьей. Тут я описал далеко не все что может встретиться на собеседовании. Эту статью можно рассматривать как отправную точку в изучении.
Учитесь тестировать код без запуска – в секции нельзя запускать код, ошибки надо находить «в уме». Весь код нужно будет написать в Yandex Code без возможности запуска и важно тренироваться писать код именно там.
Решайте задачи на LeetCode – это поможет развить навык работы с алгоритмами, но решайте задание не на сайте leetcode а в Yandex Code. Уже готовое решение копируете в leetcode для проверки, если есть ошибки - считайте это провалом.
Сначала думаем - потом пишем. Не торопитесь. Всегда сначала в голове продумываете решение и его алгоритмическую сложность, а потом начинаете писать код. Частая ошибка это сразу начать писать код и пытаться походу написания прийти к решению. Из-за этого кандидаты иногда пишут странные вещи, которые они бы не написали, если бы сначала продумали решение вплоть до результата работы программы. Даже если вы написали, а потом поняли, что это не то что нужно и удалили этот код, собеседующий это запомнит, что может привести к провалу собеседования.
Как вести себя на собеседовании?
Задавайте вопросы – уточняйте входные данные и ограничения.
Учитывайте крайние случаи – пустые массивы, отрицательные числа, большие входные данные.
Оптимально распределяйте время – на первую задачу около 30 минут.
Не бойтесь ошибаться – главное, уметь их исправлять.
Алгоритмическая сложность
Big O нотация
Big O нотация — это способ измерения скорости работы алгоритма. Она показывает, как быстро растёт время выполнения или потребление памяти в зависимости от размера входных данных.
Основные классы сложности
Нотация | Название | Пример |
|---|---|---|
O(1) | Константное время | Доступ к элементу массива arr[0] |
O(log N) | Логарифмическое | Бинарный поиск в отсортированном массиве |
O(N) | Линейное время | Перебор массива for i in arr: |
O(N log N) | Квазилинейное | Быстрая сортировка (QuickSort) |
O(N²) | Квадратичное | Два вложенных цикла for i in arr: for j in arr: |
O(2ⁿ) | Экспоненциальное | Перебор всех подмножеств множества |
O(N!) | Факториальное | Генерация всех перестановок |
Примеры расчёта времени и памяти вместе
Алгоритм | Время | Память |
|---|---|---|
Доступ к элементу массива | O(1) | O(1) |
Линейный поиск | O(N) | O(1) |
Двоичный (бинарный) поиск | O(log N) | O(1) |
Копирование массива | O(N) | O(N) |
Быстрая сортировка (QuickSort) | O(N log N) | O(log N) |
Динамическое программирование (таблица) | O(N²) | O(N²) |
Генерация всех перестановок | O(N!) | O(N!) |
Как считать сложность?
Игнорируем константы
O(2N) → O(N)
O(5N + 10) → O(N)
Берём самое быстро растущее слагаемое
O(N + N²) → O(N²)
O(N log N + N) → O(N log N)
Вложенные циклы → умножаем
for i in range(N): # O(N) for j in range(N): # O(N) print(i, j) # O(1)Общая сложность: O(N * N) = O(N²)
Последовательные операции → складываем
for i in range(N): # O(N) print(i) # O(1) for j in range(N): # O(N) print(j) # O(1)Общая сложность: O(N) + O(N) = O(2N) = O(N) (игнорируем константу)
Сложность по времени и по памяти
Сложность по времени - это зависимость времени выполнения программы от размера входных данных.
Допустим у нас есть функция которая принимает строку, тогда в случае линейной временной сложности, время ее выполнения будет расти линейно относительно размера переданной строке.
Длина строки 10 - время выполнения 1мс
Длина строки 50 - время выполнения 5мс
Длина строки 100 - время выполнения 10мс
Длина строки 120 - время выполнения 12мс
Конечно это условное время выполнения для простоты понимания.
Взависимости от выбранного подхода мы получим результат за разное время.
Пример переворота строки с линейной сложностью по времени O(N) и по памяти O(N)
from collections import deque
def reverse(string):
result = deque([]) # O(1)
for char in string: # O(N) итераций
result.appendleft(char) # O(1) для каждой итерации
return ''.join(result) # O(N)Временная сложность:
Создание deque([]): O(1)
Итерация по строке (N итераций): O(N)
Каждое appendleft() — O(1) → в сумме O(N)
''.join(result), так как deque конвертируется в строку: O(N)
Итоговая временная сложность:
O(1) + O(N) + O(N) = O(N)
Сложность по памяти или пространственная сложность:
deque хранит N символов → O(N)
''.join(result) создаёт новую строку длины N → O(N)
Итоговая сложность по памяти:
O(N) + O(N) = O(N)
O(1) - константная
Время выполнения или потребляемая память не зависит от размера входных данных.
Примеры:
Получение элемента массива по индексу
Добавления или удаление элемента в конце динамического массива (list в Python)
Получение значения по ключу из Хеш-таблицы (set и dict в Python)
Для примера давайте перевернем список за O(1) по памяти и O(N) по времени
def reverse(numbers):
left = 0
right = len(numbers) - 1
while left <= right:
numbers[left], numbers[right] = numbers[right], numbers[left]
left += 1
right -= 1Временная сложность:
Инициализация left и right — O(1)
Цикл while left <= right
Количество итераций примерно N/2 (мы обрабатываем по 2 элемента за раз).
Каждое присваивание numbers[left], numbers[right] = numbers[right], numbers[left] выполняется за O(1).
Итераций всего O(N/2) = O(N).
Итоговая временная сложность: O(N)
Пространственная сложность:
Используется переменные left и right — O(1).
Модификация списка происходит in-place (на месте), без создания новых структур данных.
Итоговая пространственная сложность: O(1) (константная память).
O(N) - линейная
Рассмотрим пример переворота списка за O(N) по памяти и O(N) по времени
def reverse(numbers):
result = deque([]) # O(1)
for num in numbers: # O(N) итераций
result.appendleft(num) # O(1) для каждой итерации
return list(result) # O(N)Временная сложность:
Создание deque([]) — O(1).
Цикл for num in numbers выполняется N раз.
appendleft(num) в deque работает за O(1) (в отличие от списка, где вставка в начало — O(N)).
Всего O(N) * O(1) = O(N).
list(result)
deque конвертируется в список путём копирования всех N элементов.
Работает за O(N).
Итоговая временная сложность:
O(1) + O(N) + O(N) = O(N)
Пространственная сложность:
result (deque) хранит N элементов → O(N).
Возвращаемый список list(result) требует ещё O(N) памяти.
Итоговая пространственная сложность:
O(N) + O(N) = O(N)
O(N^2) - квадратичная
Пример переворота строки с квадратичной сложностью по времени O(N2) и линейной по памяти O(N)
def reverse(string):
result = '' # O(1)
for char in string: # O(N) итераций
result = char + result # O(N) на каждую конкатенацию
return resultВременная сложность:
Создание пустой строки: result = '' — O(1)
Итерация по string (N символов) — O(N)
Операция result = char + result на каждой итерации
В Python строки неизменяемы, поэтому char + result создаёт новую строку на каждой итерации.
При конкатенации char + result, новая строка должна скопировать все N уже накопленных символов → O(N) на каждую операцию.
Так как for выполняется N раз, общая сложность O(1 + 2 + 3 + ... + N) = O(N²) (арифметическая прогрессия).
Итоговая временная сложность: O(N²)
Из-за того, что строки неизменяемы, операция result = char + result требует копирования всей строки на каждом шаге, что даёт квадратичную сложность.
Сложность по памяти или пространственная сложность:
Исходная строка string занимает O(N)
result хранит новую строку длины N, что даёт O(N)
Дополнительная память для временных строк (так как создаётся новая строка на каждой итерации) → в худшем случае O(N²) временно, но если не учитывать промежуточные строки, остаётся O(N).
O(log N) - логарифмическая
Логарифмическая сложность означает, что время выполнения алгоритма увеличивается очень медленно при росте входных данных. Если размер входных данных N увеличится в 2 раза, количество операций возрастёт только на 1 дополнительный шаг.
Представь, что у тебя есть книга с 1000 страниц, и ты ищешь конкретную страницу. Вместо того чтобы листать страницу за страницей (O(N)), ты можешь каждый раз делить книгу пополам:
Открываешь середину книги.
Если нужная страница слева — идёшь в левую половину, иначе в правую.
Повторяешь, пока не найдёшь страницу.
При таком методе количество шагов не превышает log₂(N). Например:
Для 1000 страниц потребуется ~10 шагов.
Для 1 000 000 страниц — ~20 шагов!
Классический пример — бинарный поиск в отсортированном массиве:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2 # Берём середину
if arr[mid] == target:
return mid # Нашли элемент
elif arr[mid] < target:
left = mid + 1 # Ищем в правой половине
else:
right = mid - 1 # Ищем в левой половине
return -1 # Элемент не найден
# Пример использования:
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(binary_search(arr, 9)) # Выведет 4 (индекс числа 9)Почему O(log N)?
Каждый шаг уменьшает диапазон поиска в 2 раза, поэтому общее число итераций — не больше log₂(N).
Итог: O(log N) встречается в задачах, где данные разделяются пополам на каждом шаге, например, в бинарном поиске.
O(N log N) - квазилинейная
Квазилинейная сложность означает, что время выполнения алгоритма растёт чуть быстрее, чем линейно, но всё же гораздо медленнее, чем квадратично (O(N²)).
Если N увеличивается в 10 раз, время работы увеличивается примерно в 10 × log(N) раз (то есть не в 100, как при O(N²), а меньше).
Представь, что ты хочешь отсортировать список из N чисел:
Если ты просто пробежишься по списку (O(N)) — это займёт N шагов.
Если на каждом шаге ты будешь разделять данные и выполнять несколько действий (O(log N)) — это даст N log N.
Допустим, ты раскладываешь колоду из N карт по номиналу:
Разделяешь колоду пополам, сортируешь каждую часть.
Потом объединяешь их обратно в один отсортированный список.
Повторяешь, пока всё не будет отсортировано.
Так работает, например, быстрая сортировка (QuickSort) и сортировка слиянием (MergeSort).
Классический пример — быстрая сортировка (QuickSort):
def quicksort(arr):
if len(arr) <= 1:
return arr # Базовый случай: если 1 или 0 элементов, возвращаем как есть
pivot = arr[len(arr) // 2] # Выбираем опорный элемент (pivot)
left = [x for x in arr if x < pivot] # Все элементы меньше pivot
middle = [x for x in arr if x == pivot] # Элементы, равные pivot
right = [x for x in arr if x > pivot] # Все элементы больше pivot
return quicksort(left) + middle + quicksort(right) # Рекурсивно сортируем и объединяем
# Пример использования:
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5]
print(quicksort(arr)) # Выведет: [1, 1, 2, 3, 4, 5, 5, 6, 9]Почему O(N log N)?
Каждый вызов делит массив на 2 части → log N уровней рекурсии.
На каждом уровне происходит обход всех N элементов.
Итого: O(N) * O(log N) = O(N log N).
O(N³) - кубическая
Кубическая сложность означает, что время работы растёт очень быстро при увеличении входных данных N.
Если N увеличится в 2 раза, время работы увеличится в 2³ = 8 раз.
Если N увеличится в 10 раз, время работы увеличится в 10³ = 1000 раз!
Пример из жизни:
Допустим, у тебя есть N студентов, и тебе нужно проверить:
Как каждый студент взаимодействует с каждым другим (O(N²)).
Для каждой пары проверить ещё одно условие (O(N)).
В итоге получаем O(N³).
Такое встречается, например, в переборе всех троек чисел в массиве и работе с матрицами.
Классический пример — умножение двух квадратных матриц размером N×N:
def matrix_multiply(A, B):
N = len(A) # Размер матрицы (предполагаем, что A и B — квадратные)
# O(N²) по памяти: создаём результат N×N
result = [[0] * N for _ in range(N)]
# O(N³) по времени: три вложенных цикла
for i in range(N): # Перебираем строки матрицы A
for j in range(N): # Перебираем столбцы матрицы B
for k in range(N): # Считаем скалярное произведение строки и столбца
result[i][j] += A[i][k] * B[k][j]
return result
# Пример использования:
A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
print(matrix_multiply(A, B))
# Выведет: [[19, 22], [43, 50]]Временная сложность: O(N³)
Внешний цикл (i) выполняется N раз.
Средний цикл (j) выполняется N раз.
Внутренний цикл (k) выполняется N раз.
Итог: O(N) × O(N) × O(N) = O(N³).
Пространственная сложность: O(N²)
Мы создаём новую матрицу N×N для хранения результата, что занимает O(N²) памяти.
Дополнительных больших структур не создаём, поэтому память = O(N²).
Итог
O(N³) по времени — три вложенных цикла перебирают все возможные комбинации.
O(N²) по памяти — мы создаём новую N×N матрицу для хранения результата.
Такие алгоритмы встречаются в работе с матрицами, переборе троек элементов и некоторых графовых алгоритмах.
O(N!) - факториальная
Факториальная сложность означает, что время выполнения растёт катастрофически быстро при увеличении N.
Если N увеличится всего на 1, время работы увеличивается в N раз!
Пример:
N = 3 → 3! = 3 × 2 × 1 = 6 операций.
N = 5 → 5! = 5 × 4 × 3 × 2 × 1 = 120 операций.
N = 10 → 10! = 3 628 800 операций.
Допустим, ты хочешь перебрать все возможные способы рассадить N человек за N стульев.
Первого человека можно посадить на N мест.
Второго человека — на (N - 1) оставшееся место.
Третьего — на (N - 2) и так далее…
В итоге получаем N! (N факториал) комбинаций.
Такая сложность встречается в переборе всех перестановок (пермутаций) и брутфорсных решениях.
Классический пример — генерация всех перестановок массива:
def permutations(arr):
if len(arr) == 0:
return [[]] # Базовый случай: единственная перестановка пустого массива — пустой массив
result = [] # O(N!) по памяти — храним все перестановки
for i in range(len(arr)):
rest = arr[:i] + arr[i+1:] # Убираем текущий элемент из массива (O(N))
for perm in permutations(rest): # Рекурсивно получаем все перестановки оставшихся элементов
result.append([arr[i]] + perm) # Добавляем текущий элемент к каждой из них
return result
# Пример использования:
arr = [1, 2, 3]
print(permutations(arr))
# Выведет: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]Временная сложность: O(N!)
Каждый вызов функции создает N рекурсивных веток.
В каждой ветке остаётся (N - 1)! вызовов.
Итог: O(N × (N - 1) × (N - 2) × ... × 1) = O(N!).
Пространственная сложность: O(N!)
В result хранится N! перестановок, каждая из которых имеет длину N.
Глубина рекурсии также N.
Итог: O(N!) памяти.
Итог
O(N!) по времени — крайне неэффективно для больших N.
O(N!) по памяти — храним все возможные перестановки.
Такие алгоритмы встречаются в переборе всех возможных комбинаций и брутфорсных решениях, например, в решении задач коммивояжёра и раскраски графов.
O(2^N) - экспоненциальная
Экспоненциальная сложность означает, что количество операций удваивается с каждым новым элементом N.
Если N увеличивается на 1, время выполнения увеличивается в 2 раза!
Пример:
N = 1 → 2¹ = 2 операции.
N = 5 → 2⁵ = 32 операций.
N = 10 → 2¹⁰ = 1024 операций.
N = 30 → 2³⁰ = 1 073 741 824 операций (больше 1 миллиарда!).
Допустим, ты хочешь перебрать все возможные подмножества из N предметов.
У каждого предмета есть 2 варианта: он либо включён в подмножество, либо нет.
Если предметов N, то всего возможных комбинаций 2^N.
Например, для {A, B, C} возможные подмножества:
{}, {A}, {B}, {C}, {A, B}, {A, C}, {B, C}, {A, B, C} (всего 2³ = 8).
Такая сложность встречается в переборе всех подмножеств (power set) и решениях с рекурсией и бэктреком.
Классический пример — генерация всех подмножеств (power set):
def generate_subsets(arr, index=0, current_subset=None):
if current_subset is None:
current_subset = []
if index == len(arr): # Базовый случай: дошли до конца массива
print(current_subset) # Выводим текущее подмножество
return
# Не включаем текущий элемент в подмножество
generate_subsets(arr, index + 1, current_subset)
# Включаем текущий элемент в подмножество
generate_subsets(arr, index + 1, current_subset + [arr[index]])
# Пример использования:
arr = [1, 2, 3]
generate_subsets(arr)
# Выведет:
# []
# [3]
# [2]
# [2, 3]
# [1]
# [1, 3]
# [1, 2]
# [1, 2, 3]Временная сложность: O(2^N)
В каждом шаге рекурсии есть 2 варианта: взять элемент или не взять.
Это создаёт 2 ветки для каждого элемента.
Итог: O(2^N) вызовов.
Пространственная сложность: O(2^N)
Мы храним все 2^N подмножеств, что занимает O(2^N) памяти.
Глубина рекурсии O(N), но основное потребление памяти идёт на хранение всех решений.
Итог
O(2^N) по времени — экспоненциальный рост при увеличении N.
O(2^N) по памяти — если храним все возможные подмножества.
Встречается в переборе всех подмножеств, бэктреккинге, рекурсивных задачах.
При больших N (например, N > 30) такие алгоритмы становятся практически неиспользуемыми из-за взрывного роста вычислений.
Цикломатическая сложность (Cyclomatic Complexity)
Цикломатическая сложность — это метрика, которая показывает, насколько сложен код в плане ветвлений и возможных путей выполнения.
Чем больше условий (if, while, for, case), тем выше цикломатическая сложность, а значит, код сложнее поддерживать и тестировать.
Представь, что ты едешь по дороге. Если дорога прямая, то всё просто — один маршрут. Но если на каждом километре развилка (if), то возможных путей становится много, и чем их больше, тем сложнее найти оптимальный.
Как определить цикломатическую сложность?
Формула:
M=E−N+2PM = E - N + 2PM=E−N+2P
Где:
M — цикломатическая сложность.
E — количество рёбер (переходов между операциями).
N — количество узлов (инструкций в коде).
P — количество отдельных компонентов (обычно 1 для обычной программы).
Простой код (M = 1, минимальная сложность)
def sum_numbers(a, b):
return a + bE = 1, N = 1, P = 1 → M = 1
Нет условий или циклов, всего один возможный путь выполнения.
Средняя сложность (M = 3)
def check_number(n):
if n > 0:
print("Положительное")
elif n < 0:
print("Отрицательное")
else:
print("Ноль")E = 4, N = 3, P = 1 → M = 3
Есть 2 условия (if и elif), создающие 3 возможных пути выполнения.
Как улучшить?
Можно заменить if-elif-else на dict для лучшей читаемости:
def check_number(n):
messages = {n > 0: "Положительное", n < 0: "Отрицательное"}
print(messages.get(True, "Ноль"))Теперь M = 2, код стал проще.
Высокая сложность (M = 5)
def process_numbers(a, b):
if a > 0:
if b > 0:
print("Оба положительные")
else:
print("a положительное, b нет")
else:
if b > 0:
print("b положительное, a нет")
else:
print("Оба отрицательные или ноль")E = 6, N = 4, P = 1 → M = 5
4 if → 5 возможных путей выполнения.
Как улучшить? Можно упростить вложенность:
def process_numbers(a, b):
if a > 0 and b > 0:
print("Оба положительные")
elif a > 0:
print("a положительное, b нет")
elif b > 0:
print("b положительное, a нет")
else:
print("Оба отрицательные или ноль")Теперь M = 4, код проще читать.
Очень сложный код (M = 9)
def complex_logic(x, y, z):
if x > 0:
if y > 0:
if z > 0:
print("Все положительные")
else:
print("x и y положительные, z нет")
else:
if z > 0:
print("x и z положительные, y нет")
else:
print("Только x положительное")
else:
if y > 0:
if z > 0:
print("y и z положительные, x нет")
else:
print("Только y положительное")
else:
if z > 0:
print("Только z положительное")
else:
print("Все нули или отрицательные")E = 10, N = 7, P = 1 → M = 9
8 if-ов → 9 возможных путей выполнения.
Как улучшить? Используем таблицу условий вместо вложенных if:
def complex_logic(x, y, z):
states = {(True, True, True): "Все положительные",
(True, True, False): "x и y положительные, z нет",
(True, False, True): "x и z положительные, y нет",
(True, False, False): "Только x положительное",
(False, True, True): "y и z положительные, x нет",
(False, True, False): "Только y положительное",
(False, False, True): "Только z положительное",
(False, False, False): "Все нули или отрицательные"}
print(states[(x > 0, y > 0, z > 0)])Теперь M = 2, код читается легче!
Общие способы уменьшения цикломатической сложности
1. Убирайте вложенные if
Чем глубже if, тем сложнее код.
Лучше использовать логические операторы (and, or) или ранний выход (return).
2. Используйте dict вместо if-elif-else
dict позволяет убрать длинные каскады if-elif-else.
3. Разбивайте сложные функции на простые
Функция должна делать только одну вещь.
4. Используйте полиморфизм (если код на ООП)
Вместо if в ООП-коде лучше использовать наследование и перегрузку методов.
Итог
Цикломатическая сложность показывает, сколько путей выполнения в коде.
Чем больше if, for, while — тем сложнее код.
Оптимизация: убираем вложенные if, используем dict, логические операторы и ранний выход.
Хороший код = меньше путей выполнения = проще читать и тестировать.
Популярные подходы к решению алгоритмических задач
Два указателя (Two Pointers)
Два указателя — это техника, которая помогает обрабатывать массив за один проход или уменьшить количество ненужных проверок.
Мы используем два индекса (указателя), которые двигаются по массиву разными способами:
Один медленный, другой быстрый
Один с начала, другой с конца
Два указателя по разным массивам
Медленный и быстрый указатели (Fast & Slow)
Когда один указатель движется медленно, а другой — быстро. Используется для поиска цикла в списках, анализа последовательностей и т.д..
Пример: Найти цикл в связном списке (алгоритм Флойда)
Что значит "цикл" в списке? Если в списке есть цикл, то указатель может бесконечно бегать по кругу, не доходя до None.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def has_cycle(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next # Медленный двигается на 1 шаг
fast = fast.next.next # Быстрый двигается на 2 шага
if slow == fast:
return True # Если указатели встретились — цикл есть!
return False # Если fast дошел до конца — цикла нет
# Пример списка с циклом: 1 -> 2 -> 3 -> 4 -> 2 (цикл)
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2 # Цикл
print(has_cycle(node1)) # TrueПочему это работает?
Если цикла нет, fast дойдет до None, и мы вернем False.
Если цикл есть, fast и slow рано или поздно встретятся.
Сложность: O(N), потому что мы пробегаем список один раз.
Два указателя с концов
Когда один указатель с начала, другой с конца, и они сходятся в середине.
Где это ипользуется?
Поиск пар чисел, дающих нужную сумму.
Переворот массива in-place.
Пример: Найти два числа, сумма которых равна target (в отсортированном массиве)
def two_sum(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return (arr[left], arr[right])
elif current_sum < target:
left += 1 # Увеличиваем сумму
else:
right -= 1 # Уменьшаем сумму
return None
print(two_sum([1, 2, 3, 4, 6], 6)) # (2, 4)
print(two_sum([1, 3, 5, 8, 12], 10)) # (2, 8)Вместо O(N²) за счет вложенного цикла → O(N), потому что проходим список всего один раз.
Два указателя по разным массивам
Когда у нас два отсортированных массива, и мы хотим их обработать быстрее, чем за O(N*M).
Где это используется?
Слияние двух отсортированных массивов.
Поиск пересечений двух массивов.
Пример: Найти общие элементы двух отсортированных массивов
def common_elements(arr1, arr2):
i, j = 0, 0
result = []
while i < len(arr1) and j < len(arr2):
if arr1[i] == arr2[j]: # Одинаковые элементы
result.append(arr1[i])
i += 1
j += 1
elif arr1[i] < arr2[j]: # Двигаем указатель на меньшем числе
i += 1
else:
j += 1
return result
print(common_elements([1, 3, 4, 6], [2, 3, 6, 8])) # [3, 6]Обычный перебор был бы O(N*M), а тут всего O(N + M).
Скользящее окно (Sliding Window)
Представь, что у тебя есть массив чисел, и тебе надо найти максимальную сумму подмассива фиксированной длины или самую длинную подстроку, удовлетворяющую условиям.
Перебирать все возможные подмассивы (O(N²)).
Использовать "скользящее окно" и проходить по массиву всего один раз (O(N)).
Как это работает?
Представь, что у тебя есть "окно" (например, подмассив длины k).
Ты сначала заполняешь это окно, суммируя k элементов.
Затем "скользишь" по массиву, убирая старый элемент (который вышел за границу окна) и добавляя новый элемент (который входит в окно).
Пример 1: Найти максимальную сумму k подряд идущих элементов в массиве
Дан массив чисел и k. Найти подмассив длины k с максимальной суммой.
def max_sum_subarray(arr, k):
max_sum = float('-inf')
current_sum = sum(arr[:k]) # Начальная сумма первых k элементов
max_sum = current_sum
for i in range(len(arr) - k):
current_sum = current_sum - arr[i] + arr[i + k] # Сдвигаем окно
max_sum = max(max_sum, current_sum)
return max_sum
print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3)) # 9 (5+1+3)
print(max_sum_subarray([4, 2, 1, 7, 8, 1, 2, 8, 1, 0], 3)) # 16 (7+8+1)Почему это круто?
Без скользящего окна: Надо проверять все подмассивы (O(N²)).
Со скользящим окном: Мы просто убираем старый элемент и добавляем новый (O(N)).
Пример 2: Найти длину самой длинной подстроки с уникальными символами
Даная строка. Найти самую длинную подстроку, в которой нет повторяющихся символов.
def longest_unique_substring(s):
char_set = set() # Храним уникальные символы
left = 0 # Левый указатель окна
max_length = 0
for right in range(len(s)):
while s[right] in char_set: # Если символ уже в окне — сдвигаем левый указатель
char_set.remove(s[left])
left += 1
char_set.add(s[right]) # Добавляем новый символ в окно
max_length = max(max_length, right - left + 1) # Считаем длину окна
return max_length
print(longest_unique_substring("abcabcbb")) # 3 (abc)
print(longest_unique_substring("bbbbb")) # 1 (b)
print(longest_unique_substring("pwwkew")) # 3 (wke)Как это работает?
Окно сдвигается вправо по строке.
Если символ повторяется, сдвигаем левую границу окна, пока повтор не исчезнет.
Итоговая сложность O(N), потому что каждый символ обрабатывается максимум 2 раза (когда заходит в окно и когда выходит).
Пример 3: Минимальная длина подмассива с суммой >= target
Найти самый короткий подмассив, сумма которого ≥ target.
def min_subarray_len(target, arr):
left = 0
current_sum = 0
min_length = float('inf')
for right in range(len(arr)):
current_sum += arr[right] # Добавляем новый элемент в окно
while current_sum >= target: # Если сумма >= target, сдвигаем левую границу
min_length = min(min_length, right - left + 1)
current_sum -= arr[left]
left += 1
return min_length if min_length != float('inf') else 0
print(min_subarray_len(7, [2, 3, 1, 2, 4, 3])) # 2 ([4, 3])
print(min_subarray_len(15, [1, 2, 3, 4, 5])) # 5 ([1,2,3,4,5])Почему это круто?
Без скользящего окна: Надо проверять все возможные подмассивы (O(N²)).
Со скользящим окном: Мы не перезапускаем поиск сначала, а просто сдвигаем левую границу (O(N)).
Обход в глубину (DFS — Depth First Search)
Обход в глубину (DFS) — это способ обхода графа или дерева, при котором мы идем как можно глубже по одной ветке, прежде чем вернуться назад и попробовать другую.
Представь, что ты заблудился в лабиринте, но у тебя есть правило:
Всегда иди вперед, пока не упрешься в тупик.
Если уперся — откатывайся назад и пробуй другую дорогу.
Где применяется?
Обход графов и деревьев (например, в поисковых алгоритмах).
Поиск пути в лабиринтах.
Проверка связности графа (есть ли путь между узлами).
Поиск компоненты связности.
Генерация лабиринтов.
Пример 1: DFS для дерева (рекурсия)
Обход дерева в глубину (прямой, обратный, симметричный обходы)
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def dfs_inorder(node): # Симметричный (LNR)
if node:
dfs_inorder(node.left)
print(node.value, end=" ")
dfs_inorder(node.right)
def dfs_preorder(node): # Прямой (NLR)
if node:
print(node.value, end=" ")
dfs_preorder(node.left)
dfs_preorder(node.right)
def dfs_postorder(node): # Обратный (LRN)
if node:
dfs_postorder(node.left)
dfs_postorder(node.right)
print(node.value, end=" ")
# Создадим дерево
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
print("DFS (симметричный обход):")
dfs_inorder(root) # 4 2 5 1 6 3 7
print("\nDFS (прямой обход):")
dfs_preorder(root) # 1 2 4 5 3 6 7
print("\nDFS (обратный обход):")
dfs_postorder(root) # 4 5 2 6 7 3 1Как это работает?
Мы рекурсивно идем вниз по левому поддереву.
Когда левых детей нет — обрабатываем текущий узел.
Потом идем в правое поддерево.
Возвращаемся назад и повторяем, пока не обойдем все.
Пример 2: DFS для графа (итеративный вариант со стеком)
Тоже самое, но без рекурсии (безопаснее для больших графов)
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop() # Достаем последний элемент (LIFO)
if node not in visited:
print(node, end=" ")
visited.add(node)
stack.extend(graph[node][::-1]) # Добавляем соседей в стек (в обратном порядке)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print("DFS итеративно:")
dfs_iterative(graph, 'A') # A C F E B D (порядок может отличаться)Почему итеративный DFS иногда лучше?
В глубоких деревьях и графах рекурсия может привести к переполнению стека.
Здесь мы используем явный стек, поэтому управляем процессом вручную.
Обход в ширину (BFS — Breadth First Search)
BFS (Breadth-First Search) — это алгоритм поиска, который сначала исследует все ближайшие узлы, а потом переходит на следующий уровень.
Представь, что ты ищешь друга в толпе. Вместо того, чтобы сразу бежать вглубь, ты сначала проверяешь всех людей рядом, потом идешь чуть дальше и так далее.
Пример 1: BFS для графа
Обходим все вершины, начиная с указанной
from collections import deque
def bfs(graph, start):
queue = deque([start]) # Очередь для обхода
result = [] # Список посещенных вершин
while queue:
node = queue.popleft() # Берем первый элемент из очереди
if node not in result:
result.append(node)
queue.extend(graph[node]) # Добавляем всех соседей в очередь
return result
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print("BFS обход:", bfs(graph, 'A'))
# Возможный вывод: ['A', 'B', 'C', 'D', 'E', 'F']Как это работает?
Начинаем с вершины A и кладем ее в очередь.
Берем A, добавляем её соседей (B, C).
Берем B, добавляем её соседей (D, E).
Берем C, добавляем F.
Продолжаем, пока не обойдем весь граф.
Пример 2: BFS для поиска пути в лабиринте
Ищем кратчайший путь из левого верхнего угла в правый нижний
def bfs_maze(maze, start):
rows, cols = len(maze), len(maze[0])
queue = deque([(start[0], start[1], [(start[0], start[1])])]) # (x, y, путь)
while queue:
x, y, path = queue.popleft()
# Если дошли до выхода
if (x, y) == (rows - 1, cols - 1):
return path
# Возможные направления движения
for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == '.':
maze[nx][ny] = '#' # Отмечаем клетку как посещенную
queue.append((nx, ny, path + [(nx, ny)]))
return None # Если путь не найден
maze = [
['.', '.', '.', '#', '.', '.'],
['#', '#', '.', '#', '.', '#'],
['.', '.', '.', '.', '.', '.'],
['#', '.', '#', '#', '#', '.'],
['.', '.', '.', '#', '.', '.'],
['#', '#', '.', '.', '.', '.']
]
path = bfs_maze(maze, (0, 0))
print("Кратчайший путь:", path)Как это работает?
BFS находит кратчайший путь, потому что проверяет все соседние клетки по уровням.
Каждая клетка добавляется в очередь только один раз, что делает алгоритм эффективным.
Разделяй и властвуй (Divide and Conquer)
Разделяй и властвуй (Divide and Conquer) — это подход к решению задач, который заключается в разбиении большой задачи на несколько меньших, которые решаются отдельно, а потом результаты этих меньших задач объединяются в решение исходной задачи.
Представь, что у тебя есть огромная гора работы, и ты решаешь ее разобрать на маленькие части. Каждую часть ты решаешь по отдельности, а затем все собрал и получил решение.
Как это работает?
Разделение: Разбиваем исходную задачу на несколько меньших, идентичных, но более простых подзадач.
Решение: Каждую из этих подзадач решаем независимо.
Объединение: Объединяем решения подзадач в итоговое решение задачи.
Пример 1: Сортировка слиянием (Merge Sort)
def merge_sort(arr):
if len(arr) <= 1:
return arr
# Разделяем массив на две части
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# Объединяем отсортированные части
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
# Слияние двух отсортированных списков
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Добавляем оставшиеся элементы
result.extend(left[i:])
result.extend(right[j:])
return result
arr = [38, 27, 43, 3, 9, 82, 10]
print("Отсортированный массив:", merge_sort(arr))Как это работает?
Мы разбиваем массив на две части до тех пор, пока не получим массивы из одного элемента.
Каждый из этих маленьких массивов уже отсортирован (по сути, из одного элемента).
Сливаем их в два отсортированных массива, повторяя этот процесс на каждом уровне.
Пример 2: Быстрая сортировка (Quick Sort)
Алгоритм сортировки массива, который выбирает опорный элемент и сортирует элементы вокруг него.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # Выбираем опорный элемент
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
arr = [38, 27, 43, 3, 9, 82, 10]
print("Отсортированный массив:", quick_sort(arr))Как это работает?
Разделение: Мы выбираем опорный элемент, а затем делим массив на три части: меньшие, равные и большие опорному элементу.
Решение: Рекурсивно применяем сортировку к подмассивам.
Объединение: Объединяем отсортированные части, что дает нам итоговый отсортированный массив.
Пример 3: Поиск максимального элемента в массиве
def find_max(arr):
if len(arr) == 1:
return arr[0]
mid = len(arr) // 2
left_max = find_max(arr[:mid])
right_max = find_max(arr[mid:])
return max(left_max, right_max)
arr = [2, 5, 1, 8, 3, 7]
print("Максимальный элемент:", find_max(arr))Как это работает?
Разбиваем массив на две части.
Находим максимальные элементы в обеих частях.
Возвращаем наибольшее из двух найденных максимумов.
Динамическое программирование (Dynamic Programming)
Динамическое программирование (DP) — это метод оптимизации, который используется для решения задач, состоящих из повторяющихся подзадач, где результаты этих подзадач можно сохранить и переиспользовать для ускорения вычислений.
Представь, что ты решаешь задачу и уже потратил много времени на решение одной из ее частей. В следующий раз, когда эта часть появится, ты просто возьмешь уже готовый результат, а не будешь решать ее заново. Это и есть суть динамического программирования.
Как работает динамическое программирование?
Разбиение задачи: Разбиваем задачу на несколько подзадач.
Решение подзадач: Каждую подзадачу решаем отдельно.
Сохранение результатов: Результаты подзадач сохраняем в таблице или массиве.
Использование ранее сохраненных результатов: Для последующих подзадач используем уже вычисленные значения, что позволяет избежать повторных вычислений.
Различие между динамическим программированием и методом "разделяй и властвуй"
Динамическое программирование и метод "разделяй и властвуй" — оба являются стратегиями для решения сложных задач, но они имеют принципиальные различия в подходе к решению и характере задач, для которых они применимы.
Подход к решению задачи:
Динамическое программирование (DP):
Основной принцип — разбиение задачи на подзадачи и сохранение результатов этих подзадач для предотвращения их многократного вычисления.
Используется, когда задача содержит повторяющиеся подзадачи. Мы решаем подзадачи один раз и сохраняем результаты, чтобы использовать их в дальнейшем.
Решение зависит от ранее найденных решений подзадач.
Разделяй и властвуй (Divide and Conquer):
Основной принцип — разделение задачи на подзадачи, которые решаются независимо друг от друга, а затем объединение результатов.
Здесь подзадачи не пересекаются и не имеют общих решений, которые нужно сохранять.
Задача делится на несколько частей, каждая из которых решается независимо, а затем результаты комбинируются для получения ответа.
Тип задач:
Динамическое программирование подходит для задач, где:
Есть повторяющиеся подзадачи.
Необходимо оптимизировать какое-то значение (например, максимизировать прибыль или минимизировать стоимость).
Примеры: задачи о рюкзаке, задачи на нахождение наибольшей общей подпоследовательности, числовые последовательности (например, Фибоначчи).
Метод "разделяй и властвуй" используется для задач, где:
Подзадачи независимы друг от друга, и их решение не зависит от решения других подзадач.
Примеры: сортировка (например, быстрая сортировка, сортировка слиянием), нахождение минимального/максимального элемента в массиве.
Хранение промежуточных результатов:
Динамическое программирование требует сохранения результатов подзадач, чтобы избежать их многократного вычисления. Это может быть сделано с помощью таблицы или массива.
Метод "разделяй и властвуй" обычно не требует сохранения промежуточных результатов, так как подзадачи решаются независимо друг от друга.
Пример 1: Числа Фибоначчи
Задача: Нужно вычислить n-е число Фибоначчи. Числа Фибоначчи строятся по правилу:
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) для n > 1
Решение без динамического программирования (Рекурсия)
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(10)) # Вывод: 55Время: O(2^n), потому что на каждом уровне рекурсии происходит два вызова для n-1 и n-2, что приводит к экспоненциальному числу вызовов.
Память: O(n), потому что для рекурсии требуется хранить стек вызовов.
Решение с динамическим программированием
def fibonacci_dp(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fibonacci_dp(10)) # Вывод: 55Время: O(n), потому что мы проходим массив один раз, чтобы вычислить каждый элемент.
Память: O(n), потому что мы храним все промежуточные результаты в массиве.
Мы заполняем массив dp, начиная с первого элемента и используя результаты предыдущих элементов для вычисления следующего. Это позволяет избежать многократных вычислений для одинаковых значений.
Пример 2: Задача о рюкзаке (0/1 Knapsack)
У нас есть рюкзак, в который мы можем положить предметы. Каждый предмет имеет вес и стоимость. Нужно выбрать такие предметы, чтобы максимизировать стоимость, но не превысить максимальный вес рюкзака.
Решение с динамическим программированием
def knapsack(weights, values, W):
n = len(weights)
dp = [[0] * (W + 1) for _ in range(n + 1)] # Массив для хранения результатов
for i in range(1, n + 1):
for w in range(1, W + 1):
if weights[i - 1] <= w: # Если текущий предмет можно взять в рюкзак
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 5
print(knapsack(weights, values, W)) # Вывод: 7Время: O(n * W), где n — количество предметов, а W — максимальный вес рюкзака. Мы заполняем таблицу размером n x W.
Память: O(n * W), потому что мы храним результаты для всех возможных комбинаций предметов и весов.
Мы создаем таблицу dp, где каждый элемент dp[i][w] представляет максимальную стоимость, которую можно достичь с первыми i предметами при весе рюкзака w. Для каждого предмета решаем, стоит ли его добавить в рюкзак или оставить.
Пример 3: Поиск наибольшей общей подпоследовательности (LCS)
Задача: Найти наибольшую общую подпоследовательность двух строк.
Решение с динамическим программированием
def lcs(X, Y):
m = len(X)
n = len(Y)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
X = "ABCBDAB"
Y = "BDCAB"
print(lcs(X, Y)) # Вывод: 4Время: O(m * n), где m и n — длины строк. Мы заполняем таблицу размером m x n.
Память: O(m * n), так как мы храним результаты для всех возможных пар подстрок.
Мы создаем таблицу dp, где каждый элемент dp[i][j] хранит длину наибольшей общей подпоследовательности для первых i символов строки X и первых j символов строки Y.
Жадный алгоритм (Greedy Algorithm)
Жадный алгоритм — это метод решения задач, при котором на каждом шаге выбирается локально оптимальное решение, с надеждой, что это приведет к глобально оптимальному результату. Идея заключается в том, чтобы на каждом шаге делать тот выбор, который кажется наилучшим в текущий момент, не задумываясь о будущем.
Жадные алгоритмы часто используются для оптимизационных задач, где нужно найти наилучшее решение при ограниченных ресурсах, например, минимизировать стоимость, максимизировать прибыль или выполнить задачи с ограничениями.
Основные правила работы жадного алгоритма:
Локальная оптимизация: на каждом шаге выбирается решение, которое оптимально на текущем шаге.
Решение задачи пошагово: на каждом шаге принимается одно решение, и это решение не изменяется.
Не всегда дает глобальный оптимум: в некоторых задачах жадный алгоритм не может найти наилучшее решение, но во многих случаях он работает достаточно хорошо и эффективно.
Задача о монетах (Change Making Problem)
Дано множество монет с разными номиналами (например, 1, 5, 10, 25). Нужно из набора монет составить заданную сумму, используя минимальное количество монет.
Алгоритм:
На каждом шаге выбираем монету наибольшего номинала, которая меньше или равна оставшейся сумме.
Уменьшаем оставшуюся сумму на номинал выбранной монеты и повторяем шаг.
Пример: Для суммы 30 и монет [1, 5, 10, 25] жадный алгоритм выберет монету 25 (оставшаяся сумма 5), затем монету 5 (оставшаяся сумма 0). Результат: 2 монеты.
def make_change(amount, coins):
coins.sort(reverse=True) # Сортируем монеты по убыванию
result = []
for coin in coins:
while amount >= coin:
amount -= coin
result.append(coin)
return result
amount = 30
coins = [1, 5, 10, 25]
print(make_change(amount, coins)) # [25, 5]Время: O(n), где n — количество монет (после сортировки). В худшем случае можно пройти по всем монетам.
Память: O(k), где k — количество монет, используемых для получения суммы.
Задача о рюкзаке с жадным методом (Fractional Knapsack Problem)
Есть рюкзак с ограниченной вместимостью и набор предметов, каждый из которых имеет массу и стоимость. Нужно выбрать предметы, чтобы максимизировать стоимость в рюкзаке. В отличие от классической задачи о рюкзаке, здесь можно брать части предметов (то есть, предмет можно разделить).
Алгоритм:
Рассчитываем "ценность" каждого предмета, деля его стоимость на массу.
Сортируем предметы по этой ценности (по убыванию).
Заполняем рюкзак, начиная с предметов с наибольшей ценностью.
Пример: Предметы: масса [10, 20, 30], стоимость [60, 100, 120], вместимость рюкзака — 50.
Жадный алгоритм сначала выберет предмет с наибольшей ценностью (120/30 = 4), затем второй (100/20 = 5), и после этого возьмет часть третьего предмета.
def fractional_knapsack(capacity, weights, values):
n = len(weights)
ratio = [(values[i] / weights[i], weights[i], values[i]) for i in range(n)]
ratio.sort(reverse=True, key=lambda x: x[0])
total_value = 0
for r, w, v in ratio:
if capacity >= w:
total_value += v
capacity -= w
else:
total_value += v * (capacity / w)
break
return total_value
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(fractional_knapsack(capacity, weights, values)) # 240.0Время: O(n log n), где n — количество предметов (время на сортировку).
Память: O(n), где n — количество предметов (для хранения информации о каждом предмете).
Задача о наименьшем пути (Shortest Path in a Graph)
Найти кратчайший путь от одной вершины графа до другой, используя жадный алгоритм.
Алгоритм:
Начинаем с начальной вершины.
Из всех соседей выбираем наименьший по весу путь.
Повторяем процесс для каждого следующего соседа.
Пример: Для графа с вершинами и рёбрами, жадный алгоритм может быть использован для поиска пути, например, с использованием алгоритма Дейкстры (если веса рёбер неотрицательны).
import heapq
def dijkstra(graph, start):
pq = [(0, start)] # (distance, node)
distances = {node: float('inf') for node in graph}
distances[start] = 0
while pq:
current_distance, current_node = heapq.heappop(pq)
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('A', 1), ('C', 2), ('D', 5)],
'C': [('A', 4), ('B', 2), ('D', 1)],
'D': [('B', 5), ('C', 1)]
}
print(dijkstra(graph, 'A')) # {'A': 0, 'B': 1, 'C': 3, 'D': 4}Время: O((V + E) log V), где V — количество вершин, E — количество рёбер (для алгоритма Дейкстры с приоритетной очередью).
Память: O(V), где V — количество вершин (для хранения расстояний).
Поиск с возвратом (Backtracking)
Поиск с возвратом — это метод решения задач, при котором решение строится поэтапно, и если на каком-то этапе возникает неудачное решение, алгоритм «возвращается» назад и пробует другой вариант. Это своего рода улучшение метода полного перебора, где мы не продолжаем искать решения по ветке, если понимаем, что дальнейшее продвижение не приведет к успешному результату.
Этот подход часто используется для задач, где нужно исследовать все возможные варианты или решения, такие как задачи на перестановки, комбинации, размещения, игры или разделение задач на более мелкие подзадачи.
Основные правила работы поиска с возвратом:
Поиск всех решений: мы можем исследовать все возможные варианты решений, пытаясь разные пути.
Возврат (Backtrack): если текущий путь не приводит к правильному решению, мы возвращаемся на шаг назад и пробуем другой вариант.
Рекурсия: часто используется рекурсивный подход, чтобы легко возвращаться на предыдущие шаги.
Задача о расставлении ферзей (N-Queens Problem)
Разместить N ферзей на шахматной доске размером N x N так, чтобы ни один ферзь не угрожал другому. Ферзи могут угрожать друг другу по горизонтали, вертикали и диагоналям.
Алгоритм:
Размещаем ферзя в первом ряду, затем продолжаем размещать ферзей на следующих рядах.
Если на текущем шаге не удается разместить ферзя, возвращаемся на предыдущий шаг и пробуем другой вариант.
Если все ферзи размещены корректно, выводим решение.
def is_safe(board, row, col, n):
for i in range(row):
if board[i] == col or abs(board[i] - col) == row - i:
return False
return True
def solve_nqueens(board, row, n):
if row == n:
return [board[:]] # Найдено решение, возвращаем доску
solutions = []
for col in range(n):
if is_safe(board, row, col, n):
board[row] = col # Размещаем ферзя
solutions += solve_nqueens(board, row + 1, n) # Рекурсивный вызов
board[row] = -1 # Отменяем размещение
return solutions
def n_queens(n):
board = [-1] * n # Инициализация доски
return solve_nqueens(board, 0, n)
print(n_queens(4))Время: O(N!), так как в худшем случае мы проверяем все возможные перестановки размещения ферзей на доске.
Память: O(N), так как нам нужно хранить положение ферзей в каждой строке (для доски N x N), а также хранить решения в памяти.
Задача о разбиении множества (Subset Sum Problem)
Есть множество чисел, нужно найти, существует ли подмножество этих чисел, сумма которых равна заданному числу (например, 10).
Алгоритм:
Проверяем, можно ли сформировать сумму из текущего подмножества.
Если сумма равна целевому числу, возвращаем True.
Если сумма больше, отменяем текущий выбор и пробуем следующее число.
Рекурсивно пытаемся добавить элементы множества к текущей сумме.
def is_subset_sum(numbers, target, index):
if target == 0:
return True
if index == len(numbers) or target < 0:
return False
# Включаем текущий элемент
if is_subset_sum(numbers, target - numbers[index], index + 1):
return True
# Не включаем текущий элемент
return is_subset_sum(numbers, target, index + 1)
def subset_sum(numbers, target):
return is_subset_sum(numbers, target, 0)
numbers = [3, 34, 4, 12, 5, 2]
target = 9
print(subset_sum(numbers, target)) # True (3 + 4 + 2 = 9)Время: O(2^N), так как на каждом шаге есть два варианта: включить или не включить элемент в подмножество.
Память: O(N), так как на каждом шаге рекурсии хранится состояние.
Задача о перестановках (Permutations)
Найти все возможные перестановки для данного списка чисел.
Алгоритм:
Итерируем по всем элементам списка и на каждом шаге фиксируем один элемент.
Рекурсивно генерируем все возможные перестановки оставшихся элементов.
Когда элементы заканчиваются, выводим текущую перестановку.
def permute(nums):
def backtrack(start):
if start == len(nums):
result.append(nums[:])
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start] # Меняем местами
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start] # Возврат
result = []
backtrack(0)
return result
print(permute([1, 2, 3]))Время: O(N!), так как для N элементов существует N! перестановок.
Память: O(N), так как мы храним результат и текущие элементы в процессе перестановки.
Задачи для подготовки к алгоритмическому собеседованию в Яндекс
Конечно на собеседовании вам скрее всего дадут другие задачи, но подходы к решению будут схожи.
Тренироваться решать алгоритмы вам нужно так, как описано в этой статье в главе - Как проходят алгоритмические собеседования. Если не получается, значит пробуйте сначала решать более простые задачи.
Сборники задач:
https://leetcode.com/problem-list/m424e3ds/
https://leetcode.com/problem-list/m17t1ade/
https://leetcode.com/problem-list/m424e3ds/
linked lists:
https://leetcode.com/problems/merge-k-sorted-lists/ https://leetcode.com/problems/linked-list-cycle/ https://leetcode.com/problems/add-two-numbers/ https://leetcode.com/problems/reverse-linked-list/
binary search:
https://leetcode.com/problems/binary-search/ https://leetcode.com/problems/guess-number-higher-or-lower/ https://leetcode.com/problems/search-a-2d-matrix/ https://leetcode.com/problems/search-in-rotated-sorted-array/ https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
hash table:
https://leetcode.com/problems/single-number/ (решить за O(1) по памяти)
https://leetcode.com/problems/two-sum/
https://leetcode.com/problems/group-anagrams/
https://leetcode.com/problems/valid-anagram/
https://leetcode.com/problems/find-all-anagrams-in-a-string/
queue/stack:
https://leetcode.com/problems/valid-parentheses/
dfs/bfs:
https://leetcode.com/problems/number-of-islands/ https://leetcode.com/problems/remove-invalid-parentheses/
sort:
https://leetcode.com/problems/merge-intervals/
heap/hash:
https://leetcode.com/problems/top-k-frequent-words/ https://leetcode.com/problems/top-k-frequent-elements/
two pointers:
https://leetcode.com/problems/container-with-most-water/ https://leetcode.com/problems/partition-labels/
sliding window:
https://leetcode.com/problems/sliding-window-median/ https://leetcode.com/problems/sliding-window-maximum/ https://leetcode.com/problems/longest-repeating-character-replacement/
tree:
https://leetcode.com/problems/same-tree/ https://leetcode.com/problems/symmetric-tree/ https://leetcode.com/problems/balanced-binary-tree/ https://leetcode.com/problems/path-sum-ii/
greedy problems:
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ https://leetcode.com/tag/prefix-sum/
