← Назад к курсу
Как решать задачи на Python: общие принципы и несколько примеров
Для эффективного решения задач по программированию важно следовать структурированному подходу, а не сразу писать код. Есть три ключевых блока, как показано в таблице ниже.
| Шаг решения | Что включает? | Пример для задачи "Проверка на палиндром" |
|---|---|---|
| 1. Анализ задачи | Понимание условия, входных и выходных данных, краевых случаев. | Проверить, читается ли строка одинаково слева направо и справа налево, игнорируя регистр и знаки препинания. |
| 2. Разработка алгоритма | Создание последовательности шагов для преобразования ввода в вывод. | 1. Убрать лишние символы. 2. Привести к нижнему регистру. 3. Сравнить строку с её обратной версией. |
| 3. Реализация с комментариями | Чистый код, комментарии для пояснения сложной логики, а не очевидных вещей. | См. примеры в разделах задач ниже. |
Список из 10 непростых алгоритмических задач
Вот список задач, которые помогут развить алгоритмическое мышление. К некоторым из них я приведу реализацию с пояснениями, а для остальных дам ключевые идеи и направления для самостоятельной работы.
1. Задача о рюкзаке (Knapsack Problem)
Это классическая задача на динамическое программирование. Есть рюкзак вместимостью W и N предметов с весом weight[i] и ценностью value[i]. Нужно выбрать предметы с максимальной суммарной стоимостью, не превышая вместимость рюкзака.
2. Проверка зеркальности двоичного дерева
Для заданного двоичного дерева нужно проверить, является ли оно зеркальным отражением самого себя (симметричным относительно корня). Задача на рекурсию или обход деревьев.
3. Медиана в скользящем окне (Sliding Window Median)
Задача требует эффективно находить медиану для каждого окна фиксированного размера в потоке чисел. Решение обычно строится на использовании двух куч (мин-кучи и макс-кучи).
4. Построение очертания небоскрёбов (The Skyline Problem)
Сложная задача на обработку событий (sweep line) и работу с упорядоченными структурами данных (например, кучами) для нахождения общего силуэта множества зданий.
5. Удаление произвольного элемента из кучи (Heap with Removal)
Стандартная куча в Python (heapq) не поддерживает быстрое удаление произвольного элемента. Эта задача учит создавать надстройку над кучей для ленивого удаления.
6. Группировка анаграмм (Group Anagrams)
Для списка строк нужно сгруппировать слова, состоящие из одних и тех же букв (анаграммы). Ключевая идея — использование отсортированной строки или счётчика символов в качестве ключа в словаре.
7. Поиск k-го наибольшего элемента в потоке данных (Kth Largest Element in a Stream)
Нужно спроектировать структуру данных, которая в потоке чисел может быстро возвращать k-й по величине элемент. Оптимальное решение использует кучу минимального размера k.
8. Проверка сбалансированности двоичного дерева
Требуется определить, является ли двоичное дерево сбалансированным (разница высот левого и правого поддеревьев для любого узла не превышает 1). Решение — рекурсивный обход с возвратом высоты поддерева.
9. Реализация кэша с алгоритмом вытеснения LRU (Least Recently Used)
Задача на проектирование структуры данных, которая работает как кэш с ограниченной ёмкостью. При переполнении удаляется элемент, который использовался давнее всех. Реализуется с помощью хеш-таблицы (dict) и двусторонней очереди (deque или самодельного связного списка).
10. Задача о расстановке ферзей (N-Queens)
Классическая задача на поиск с возвратом (backtracking). Требуется разместить N ферзей на шахматной доске N×N так, чтобы они не били друг друга.
Реализация задач с комментариями
1. Задача о рюкзаке (0-1, динамическое программирование)
def knapsack(weights, values, capacity):
"""
Решает задачу о рюкзаке 0-1 методом динамического программирования.
Args:
weights: Список весов предметов.
values: Список стоимостей предметов.
capacity: Максимальная вместимость рюкзака.
Returns:
Максимальная стоимость, которую можно унести в рюкзаке.
"""
n = len(values)
# Создаем двумерный массив dp, где dp[i][w] будет хранить максимальную стоимость
# для первых i предметов и рюкзака вместимостью w.
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
# Построение таблицы dp снизу вверх
for i in range(1, n + 1):
for w in range(1, capacity + 1):
if weights[i-1] <= w:
# Если i-й предмет помещается, выбираем максимум из двух вариантов:
# 1. Не брать i-й предмет (оставляем стоимость как для i-1 предметов).
# 2. Взять i-й предмет: стоимость предмета + максимальная стоимость для оставшейся вместимости.
dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]])
else:
# Если предмет не помещается, пропускаем его.
dp[i][w] = dp[i-1][w]
return dp[n][capacity]
# Пример использования
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(f"Максимальная стоимость: {knapsack(weights, values, capacity)}")
# Вывод: Максимальная стоимость: 9 (предметы с весом 3 и 4)
2. Проверка зеркальности двоичного дерева
class TreeNode:
"""Узел бинарного дерева."""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_mirror(left: TreeNode, right: TreeNode) -> bool:
"""Вспомогательная рекурсивная функция для проверки симметрии двух поддеревьев."""
# Базовый случай: оба узла пустые
if not left and not right:
return True
# Если только один из узлов пустой, деревья не симметричны
if not left or not right:
return False
# Проверяем три условия:
# 1. Значения в узлах должны совпадать.
# 2. Левое поддерево левого узла должно быть зеркально правому поддереву правого узла.
# 3. Правое поддерево левого узла должно быть зеркально левому поддереву правого узла.
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
def is_symmetric(root: TreeNode) -> bool:
"""Проверяет, является ли дерево с корнем root зеркальным (симметричным)."""
if not root:
return True # Пустое дерево считается симметричным
return is_mirror(root.left, root.right)
# Пример использования: построим симметричное дерево [1,2,2,3,4,4,3]
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(3), TreeNode(4))
root.right = TreeNode(2, TreeNode(4), TreeNode(3))
print(f"Дерево симметрично? {is_symmetric(root)}") # Вывод: True
3. Реализация двух куч для поиска медианы в потоке (основа для задачи 3 и 5)
import heapq
class MedianFinder:
"""
Класс для эффективного поиска медианы в потоке чисел.
Использует две кучи: max_heap для меньшей половины чисел и min_heap для большей.
"""
def __init__(self):
# Max_heap моделируется с помощью отрицательных чисел, так как heapq в Python — min-heap.
self.max_heap = [] # для левой половины (меньшие числа)
self.min_heap = [] # для правой половины (большие числа)
def add_num(self, num: int) -> None:
"""Добавляет новое число в структуру, поддерживая баланс."""
# Решаем, в какую кучу положить число.
# По умолчанию отправляем в max_heap.
if not self.max_heap or num <= -self.max_heap[0]:
heapq.heappush(self.max_heap, -num)
else:
heapq.heappush(self.min_heap, num)
# **Балансировка куч**
# Размер max_heap не должен превышать размер min_heap более чем на 1, и наоборот.
if len(self.max_heap) > len(self.min_heap) + 1:
# Перемещаем корень max_heap в min_heap
heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
elif len(self.min_heap) > len(self.max_heap):
# Перемещаем корень min_heap в max_heap
heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
def find_median(self) -> float:
"""Возвращает медиану добавленных чисел."""
if len(self.max_heap) > len(self.min_heap):
# Нечетное количество элементов, медиана в корне max_heap
return -self.max_heap[0]
else:
# Четное количество, медиана - среднее арифметическое корней обеих куч
return (-self.max_heap[0] + self.min_heap[0]) / 2.0
# Пример использования
finder = MedianFinder()
for num in [1, 5, 3, 2, 4]:
finder.add_num(num)
print(f"После добавления {num}: текущая медиана = {finder.find_median()}")
# Вывод будет: 1, 3, 2, 2.5, 3
4. Построение очертания небоскрёбов (The Skyline Problem)
Алгоритм:
- Преобразуем каждое здание (L, R, H) в два события:
- (L, -H) - начало здания (отрицательная высота для сортировки)
- (R, H) - конец здания
- Сортируем события по координате X
- Используем max-heap для отслеживания текущих высот
- При встрече начала здания добавляем высоту в кучу
- При встрече конца здания помечаем высоту как "удаленную"
- Точка добавляется в результат, когда текущая максимальная высота изменяется
import heapq
from collections import defaultdict
def get_skyline(buildings):
"""
Находит очертания (skyline) для заданных зданий.
Args:
buildings: Список [L, R, H], где:
L - левая координата, R - правая координата, H - высота.
Returns:
Список ключевых точек skyline [x, height].
"""
if not buildings:
return []
# Шаг 1: Создаем события
events = []
for L, R, H in buildings:
# Отрицательная высота для начала здания обеспечивает правильный порядок сортировки
events.append((L, -H, R)) # Начало здания: (x, -height, right_x)
events.append((R, 0, 0)) # Конец здания: (x, 0, 0)
# Шаг 2: Сортируем события
events.sort()
# Шаг 3: Инициализируем структуры данных
result = [] # Результат: список ключевых точек
# Max-heap (отрицательные значения для эмуляции max-heap в Python min-heap)
# Элементы кучи: (-height, right_x)
heap = [(0, float('inf'))] # Начальный элемент: высота 0 до бесконечности
# Словарь для ленивого удаления
removed = defaultdict(int)
# Шаг 4: Обрабатываем события
for x, neg_h, R in events:
# Обработка начала здания
if neg_h < 0:
heapq.heappush(heap, (neg_h, R))
# Удаляем здания, которые закончились до текущей координаты x
while heap and removed[heap[0][0]] > 0:
h, _ = heapq.heappop(heap)
removed[h] -= 1
# Если это событие конца здания
if neg_h == 0:
# Находим все здания, которые заканчиваются в этой точке
while heap and heap[0][1] <= x:
heapq.heappop(heap)
# Получаем текущую максимальную высоту (минимальное отрицательное число)
current_height = -heap[0][0] if heap else 0
# Добавляем точку в результат, если высота изменилась
if not result or result[-1][1] != current_height:
# Если предыдущая точка имеет ту же координату x, обновляем её высоту
if result and result[-1][0] == x:
result[-1][1] = max(result[-1][1], current_height)
else:
result.append([x, current_height])
return result
# Пример использования
buildings = [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]
skyline = get_skyline(buildings)
print("Очертания небоскрёбов:")
for point in skyline:
print(f" {point}")
# Вывод: [[2,10], [3,15], [7,12], [12,0], [15,10], [20,8], [24,0]]
5. Куча с поддержкой удаления произвольных элементов
Алгоритм:
- Используем стандартную min-heap из heapq
- Для отслеживания удаленных элементов используем словарь
- При удалении помечаем элемент как удаленный в словаре
- При получении минимального элемента пропускаем помеченные как удаленные
- Периодически очищаем кучу от удаленных элементов
import heapq
from collections import defaultdict
class HeapWithRemoval:
"""
Min-heap с поддержкой удаления произвольных элементов.
Использует ленивое удаление (lazy deletion).
"""
def __init__(self):
self.heap = [] # Основная куча
self.removed = defaultdict(int) # Счетчик удаленных элементов
self.size = 0 # Текущий размер (без учета удаленных)
def push(self, value):
"""Добавляет элемент в кучу."""
heapq.heappush(self.heap, value)
self.size += 1
def remove(self, value):
"""
Помечает элемент для удаления.
Фактическое удаление произойдет при pop().
"""
if self.size == 0:
return False
self.removed[value] += 1
self.size -= 1
return True
def pop(self):
"""
Извлекает минимальный элемент, пропуская удаленные.
"""
while self.heap:
value = heapq.heappop(self.heap)
# Проверяем, не удален ли этот элемент
if self.removed.get(value, 0) > 0:
self.removed[value] -= 1
if self.removed[value] == 0:
del self.removed[value]
continue
self.size -= 1
return value
raise IndexError("pop from empty heap")
def peek(self):
"""
Возвращает минимальный элемент без извлечения.
"""
while self.heap:
value = self.heap[0]
if self.removed.get(value, 0) > 0:
# Удаляем помеченные элементы с вершины
heapq.heappop(self.heap)
self.removed[value] -= 1
if self.removed[value] == 0:
del self.removed[value]
continue
return value
raise IndexError("peek from empty heap")
def __len__(self):
"""Возвращает количество активных элементов в куче."""
return self.size
def cleanup(self):
"""Очищает кучу от всех удаленных элементов."""
while self.heap and self.removed.get(self.heap[0], 0) > 0:
value = heapq.heappop(self.heap)
self.removed[value] -= 1
if self.removed[value] == 0:
del self.removed[value]
# Пример использования
heap = HeapWithRemoval()
elements = [5, 3, 8, 1, 4, 7, 3]
print("Добавляем элементы:", elements)
for el in elements:
heap.push(el)
print(f"Размер кучи: {len(heap)}") # 7
print(f"Минимальный элемент: {heap.peek()}") # 1
print("\nУдаляем элементы 3 и 5")
heap.remove(3)
heap.remove(5)
print(f"Размер после удаления: {len(heap)}") # 5
print("\nИзвлекаем элементы по одному:")
while len(heap) > 0:
print(f" Извлечено: {heap.pop()}")
# Вывод: 1, 3, 4, 7, 8 (первый 3 удален, второй остался)
6. Группировка анаграмм
Алгоритм:
- Для каждой строки создаем ключ:
- Либо отсортированная версия строки
- Либо счетчик символов
- Используем словарь, где ключ — это признак анаграммы, значение — список строк
- Группируем строки по ключу
from collections import defaultdict
def group_anagrams(strs):
"""
Группирует анаграммы из списка строк.
Args:
strs: Список строк для группировки.
Returns:
Список списков сгруппированных анаграмм.
"""
# Вариант 1: Использование отсортированной строки в качестве ключа
def group_by_sorted(strs):
anagrams = defaultdict(list)
for s in strs:
# Сортируем символы строки и используем как ключ
sorted_key = ''.join(sorted(s))
anagrams[sorted_key].append(s)
return list(anagrams.values())
# Вариант 2: Использование счетчика символов в качестве ключа (более эффективно для длинных строк)
def group_by_counter(strs):
anagrams = defaultdict(list)
for s in strs:
# Создаем кортеж счетчика для 26 букв английского алфавита
count = [0] * 26
for char in s:
count[ord(char) - ord('a')] += 1
# Преобразуем список в кортеж для использования как ключ словаря
key = tuple(count)
anagrams[key].append(s)
return list(anagrams.values())
# Используем вариант с сортировкой (проще для понимания)
return group_by_sorted(strs)
def group_anagrams_optimized(strs):
"""
Оптимизированная версия с использованием кортежа счетчиков.
Эффективнее для строк с большим количеством символов.
"""
anagrams = defaultdict(list)
for s in strs:
# Создаем кортеж из 26 нулей для каждой буквы алфавита
count = [0] * 26
for char in s:
# Увеличиваем счетчик для соответствующей буквы
count[ord(char) - ord('a')] += 1
# Преобразуем в кортеж (хешируемый тип) для использования как ключ
key = tuple(count)
anagrams[key].append(s)
return list(anagrams.values())
# Пример использования
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print("Исходный список строк:", strs)
print("\nСгруппированные анаграммы:")
groups = group_anagrams(strs)
for i, group in enumerate(groups, 1):
print(f" Группа {i}: {group}")
# Вывод:
# Группа 1: ['eat', 'tea', 'ate']
# Группа 2: ['tan', 'nat']
# Группа 3: ['bat']
# Тестируем оптимизированную версию
print("\nОптимизированная версия:")
groups_opt = group_anagrams_optimized(strs)
for i, group in enumerate(groups_opt, 1):
print(f" Группа {i}: {group}")
7. K-й наибольший элемент в потоке данных
Алгоритм:
- Используем min-heap размера k для хранения k наибольших элементов
- При добавлении нового элемента:
- Если куча имеет размер < k, добавляем элемент
- Иначе, если элемент больше минимального в куче, заменяем его
- K-й наибольший элемент всегда на вершине min-heap
import heapq
class KthLargest:
"""
Находит k-й наибольший элемент в потоке данных.
"""
def __init__(self, k, nums):
"""
Инициализирует объект с целым числом k и потоком чисел nums.
Args:
k: Порядковый номер наибольшего элемента для поиска.
nums: Исходный поток чисел.
"""
self.k = k
self.heap = []
# Инициализируем кучу первыми k элементами
for num in nums:
self.add(num)
def add(self, val):
"""
Добавляет новый элемент в поток и возвращает k-й наибольший элемент.
Args:
val: Новое значение для добавления.
Returns:
Текущий k-й наибольший элемент.
"""
# Если в куче меньше k элементов, просто добавляем
if len(self.heap) < self.k:
heapq.heappush(self.heap, val)
# Иначе, если новый элемент больше минимального в куче, заменяем
elif val > self.heap[0]:
heapq.heappushpop(self.heap, val)
# Или можно так:
# heapq.heapreplace(self.heap, val)
# Возвращаем k-й наибольший (минимальный в min-heap размера k)
return self.heap[0]
def get_kth_largest(self):
"""
Возвращает текущий k-й наибольший элемент.
"""
if len(self.heap) < self.k:
return None
return self.heap[0]
# Пример использования
k = 3
arr = [4, 5, 8, 2]
kth_largest = KthLargest(k, arr)
print(f"Исходный массив: {arr}")
print(f"Ищем {k}-й наибольший элемент\n")
test_values = [3, 5, 10, 9, 4]
for val in test_values:
result = kth_largest.add(val)
print(f"После добавления {val}: {k}-й наибольший = {result}")
print(f" Состояние кучи: {sorted(kth_largest.heap)}")
# Вывод:
# После добавления 3: 3-й наибольший = 4
# После добавления 5: 3-й наибольший = 5
# После добавления 10: 3-й наибольший = 5
# После добавления 9: 3-й наибольший = 8
# После добавления 4: 3-й наибольший = 8
# Более сложный пример
print("\n" + "="*50)
print("Пример с отслеживанием стрима данных:")
class StreamingKthLargest:
"""
Более продвинутая версия для работы с потоком данных.
"""
def __init__(self, k):
self.k = k
self.heap = []
self.total_count = 0
def add_value(self, val):
"""
Добавляет значение из потока.
Returns:
Текущий k-й наибольший или None, если набрано меньше k элементов.
"""
self.total_count += 1
if len(self.heap) < self.k:
heapq.heappush(self.heap, val)
if len(self.heap) == self.k:
return self.heap[0]
return None
else:
if val > self.heap[0]:
heapq.heappushpop(self.heap, val)
return self.heap[0]
# Тестируем поток
stream = [1, 23, 12, 9, 30, 2, 50]
k = 3
processor = StreamingKthLargest(k)
print(f"Поток данных: {stream}")
print(f"Поиск {k}-го наибольшего в реальном времени:\n")
for i, val in enumerate(stream, 1):
result = processor.add_value(val)
print(f"Элемент {i}: {val}", end=" | ")
if result is None:
print(f"Набрано {len(processor.heap)}/{k} элементов")
else:
print(f"{k}-й наибольший = {result}")
print(f" Текущие {k} наибольших: {sorted(processor.heap)}")
8. Проверка сбалансированности двоичного дерева
Алгоритм:
- Рекурсивно вычисляем высоту каждого поддерева
- Проверяем разницу высот левого и правого поддеревьев
- Если для любого узла разница > 1, дерево не сбалансировано
- Возвращаем пару (сбалансировано?, высота)
class TreeNode:
"""Узел бинарного дерева."""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_balanced(root):
"""
Проверяет, является ли двоичное дерево сбалансированным.
Args:
root: Корень двоичного дерева.
Returns:
True, если дерево сбалансировано, иначе False.
"""
def check_balance(node):
"""
Рекурсивно проверяет баланс поддерева.
Returns:
(is_balanced, height)
"""
# Базовый случай: пустое поддерево
if not node:
return True, 0
# Рекурсивно проверяем левое и правое поддеревья
left_balanced, left_height = check_balance(node.left)
right_balanced, right_height = check_balance(node.right)
# Если хотя бы одно поддерево не сбалансировано, всё дерево не сбалансировано
if not left_balanced or not right_balanced:
return False, max(left_height, right_height) + 1
# Проверяем разницу высот
if abs(left_height - right_height) > 1:
return False, max(left_height, right_height) + 1
# Поддерево сбалансировано
return True, max(left_height, right_height) + 1
balanced, _ = check_balance(root)
return balanced
# Альтернативная реализация (более эффективная, с ранним выходом)
def is_balanced_optimized(root):
"""
Оптимизированная версия с ранним обнаружением несбалансированности.
"""
def get_height(node):
"""
Возвращает высоту поддерева или -1, если оно несбалансировано.
"""
if not node:
return 0
left_height = get_height(node.left)
# Ранний выход: если левое поддерево несбалансировано
if left_height == -1:
return -1
right_height = get_height(node.right)
# Ранний выход: если правое поддерево несбалансировано
if right_height == -1:
return -1
# Проверяем разницу высот
if abs(left_height - right_height) > 1:
return -1
# Возвращаем высоту поддерева
return max(left_height, right_height) + 1
return get_height(root) != -1
# Примеры построения деревьев для тестирования
def create_balanced_tree():
"""Создает сбалансированное дерево."""
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
return root
def create_unbalanced_tree():
"""Создает несбалансированное дерево."""
# 1
# / \
# 2 3
# / \
# 4 5
# /
# 6
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)
return root
# Тестирование
print("Тестирование сбалансированности деревьев:\n")
balanced_tree = create_balanced_tree()
print("Сбалансированное дерево:")
print(f" Базовая реализация: {is_balanced(balanced_tree)}")
print(f" Оптимизированная: {is_balanced_optimized(balanced_tree)}")
print("\n" + "-"*40)
unbalanced_tree = create_unbalanced_tree()
print("Несбалансированное дерево:")
print(f" Базовая реализация: {is_balanced(unbalanced_tree)}")
print(f" Оптимизированная: {is_balanced_optimized(unbalanced_tree)}")
# Дополнительный тест: пустое дерево
print("\n" + "-"*40)
print("Пустое дерево:")
print(f" Базовая реализация: {is_balanced(None)}")
print(f" Оптимизированная: {is_balanced_optimized(None)}")
9. Реализация LRU-кэша
Алгоритм:
- Используем хеш-таблицу (dict) для быстрого доступа по ключу
- Используем двусвязный список для отслеживания порядка использования
- При доступе к элементу перемещаем его в начало списка (самый новый)
- При добавлении нового элемента, если кэш полон, удаляем последний элемент (самый старый)
- Все операции выполняются за O(1)
class DLinkedNode:
"""Узел двусвязного списка для LRU кэша."""
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
"""
Реализация LRU (Least Recently Used) кэша.
Принцип работы:
- При доступе к элементу он становится "самым новым"
- При переполнении удаляется "самый старый" элемент
"""
def __init__(self, capacity):
"""
Инициализирует кэш заданной емкости.
Args:
capacity: Максимальное количество элементов в кэше.
"""
self.capacity = capacity
self.cache = {} # Хеш-таблица: key -> DLinkedNode
# Инициализируем двусвязный список с фиктивными head и tail
self.head = DLinkedNode() # Самый новый
self.tail = DLinkedNode() # Самый старый
# Связываем head и tail
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
def _add_node(self, node):
"""
Добавляет новый узел сразу после head (самый новый).
"""
# Связываем node с текущим первым элементом
node.prev = self.head
node.next = self.head.next
# Обновляем ссылки
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node):
"""
Удаляет узел из двусвязного списка.
"""
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
def _move_to_head(self, node):
"""
Перемещает существующий узел в начало списка (делает его самым новым).
"""
self._remove_node(node)
self._add_node(node)
def _pop_tail(self):
"""
Удаляет последний узел (самый старый) и возвращает его.
"""
tail_node = self.tail.prev
self._remove_node(tail_node)
return tail_node
def get(self, key):
"""
Получает значение по ключу.
Args:
key: Ключ для поиска.
Returns:
Значение или -1, если ключ не найден.
"""
if key not in self.cache:
return -1
# Получаем узел
node = self.cache[key]
# Обновляем порядок: перемещаем узел в начало (самый новый)
self._move_to_head(node)
return node.value
def put(self, key, value):
"""
Добавляет или обновляет значение по ключу.
Args:
key: Ключ для добавления/обновления.
value: Значение для установки.
"""
if key in self.cache:
# Ключ уже существует, обновляем значение и порядок
node = self.cache[key]
node.value = value
self._move_to_head(node)
else:
# Создаем новый узел
new_node = DLinkedNode(key, value)
# Добавляем в кэш и список
self.cache[key] = new_node
self._add_node(new_node)
self.size += 1
# Проверяем переполнение
if self.size > self.capacity:
# Удаляем самый старый элемент
tail_node = self._pop_tail()
del self.cache[tail_node.key]
self.size -= 1
def print_cache(self):
"""Выводит текущее состояние кэша."""
print(f"LRU Cache (capacity: {self.capacity}, size: {self.size}):")
# Выводим от самого нового к самому старому
node = self.head.next
elements = []
while node != self.tail:
elements.append(f"{node.key}:{node.value}")
node = node.next
if elements:
print(f" Новые -> Старые: {', '.join(elements)}")
else:
print(" Кэш пуст")
# Пример использования
print("Демонстрация работы LRU кэша:\n")
# Создаем кэш емкостью 3
cache = LRUCache(3)
cache.print_cache()
print("\n1. Добавляем элементы A:1, B:2, C:3")
cache.put('A', 1)
cache.put('B', 2)
cache.put('C', 3)
cache.print_cache()
print("\n2. Обращаемся к элементу B (теперь он самый новый)")
value = cache.get('B')
print(f" Полученное значение: {value}")
cache.print_cache()
print("\n3. Добавляем элемент D:4 (кэш переполнится, удалится самый старый A)")
cache.put('D', 4)
cache.print_cache()
print("\n4. Пытаемся получить удаленный элемент A")
value = cache.get('A')
print(f" Полученное значение: {value} (не найден)")
cache.print_cache()
print("\n5. Добавляем элемент E:5 (удалится самый старый C)")
cache.put('E', 5)
cache.print_cache()
print("\n6. Обращаемся к элементу B (теперь он самый новый)")
value = cache.get('B')
print(f" Полученное значение: {value}")
cache.print_cache()
print("\n7. Обновляем значение элемента D (теперь он самый новый)")
cache.put('D', 44)
cache.print_cache()
10. Задача о расстановке ферзей (N-Queens)
Алгоритм (поиск с возвратом):
- Используем рекурсию для размещения ферзей по строкам
- Для каждой позиции проверяем конфликты:
- Нет ферзя в том же столбце
- Нет ферзя на той же диагонали (как главной, так и побочной)
- Используем множества для отслеживания занятых столбцов и диагоналей
- При нахождении решения сохраняем его
def solve_n_queens(n):
"""
Решает задачу о расстановке N ферзей на доске N×N.
Args:
n: Размер доски и количество ферзей.
Returns:
Список всех возможных расстановок.
Каждая расстановка представлена списком строк,
где 'Q' - ферзь, '.' - пустая клетка.
"""
def is_safe(row, col, cols, diag1, diag2):
"""
Проверяет, безопасно ли разместить ферзя на позиции (row, col).
Args:
row: Номер строки.
col: Номер столбца.
cols: Множество занятых столбцов.
diag1: Множество занятых главных диагоналей (row - col).
diag2: Множество занятых побочных диагоналей (row + col).
Returns:
True, если размещение безопасно.
"""
# Проверяем столбец
if col in cols:
return False
# Проверяем главную диагональ (row - col = constant)
if (row - col) in diag1:
return False
# Проверяем побочную диагональ (row + col = constant)
if (row + col) in diag2:
return False
return True
def backtrack(row, board, cols, diag1, diag2, solutions):
"""
Рекурсивная функция для поиска решений.
Args:
row: Текущая строка для размещения ферзя.
board: Текущая доска (список строк).
cols: Множество занятых столбцов.
diag1: Множество занятых главных диагоналей.
diag2: Множество занятых побочных диагоналей.
solutions: Список для сохранения найденных решений.
"""
# Базовый случай: все ферзи размещены
if row == n:
# Сохраняем текущую доску как решение
solutions.append(["".join(row) for row in board])
return
# Пробуем разместить ферзя в каждом столбце текущей строки
for col in range(n):
if is_safe(row, col, cols, diag1, diag2):
# Размещаем ферзя
board[row][col] = 'Q'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
# Рекурсивно размещаем следующих ферзей
backtrack(row + 1, board, cols, diag1, diag2, solutions)
# Возвращаемся назад (backtrack)
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
# Инициализация
board = [['.' for _ in range(n)] for _ in range(n)]
solutions = []
# Множества для отслеживания занятых позиций
cols = set() # Занятые столбцы
diag1 = set() # Занятые главные диагонали (row - col)
diag2 = set() # Занятые побочные диагонали (row + col)
# Запускаем поиск с возвратом
backtrack(0, board, cols, diag1, diag2, solutions)
return solutions
def solve_n_queens_optimized(n):
"""
Оптимизированная версия с подсчетом количества решений.
Не хранит все доски, только считает количество решений.
"""
def backtrack(row, cols, diag1, diag2, count):
"""
Возвращает количество решений.
"""
if row == n:
return count + 1
for col in range(n):
if col not in cols and (row - col) not in diag1 and (row + col) not in diag2:
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
count = backtrack(row + 1, cols, diag1, diag2, count)
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
return count
cols = set()
diag1 = set()
diag2 = set()
return backtrack(0, cols, diag1, diag2, 0)
def print_solutions(solutions, max_to_print=2):
"""
Выводит решения в читаемом формате.
Args:
solutions: Список решений.
max_to_print: Максимальное количество решений для вывода.
"""
total = len(solutions)
print(f"Всего найдено решений: {total}")
if total == 0:
return
print(f"\nВывод первых {min(max_to_print, total)} решений:\n")
for i, solution in enumerate(solutions[:max_to_print], 1):
print(f"Решение {i}:")
for row in solution:
# Заменяем '.' на '◻' и 'Q' на '♕' для лучшей читаемости
row_display = row.replace('.', '◻').replace('Q', '♕')
print(f" {row_display}")
print()
# Примеры использования
print("="*60)
print("ЗАДАЧА О РАССТАНОВКЕ ФЕРЗЕЙ (N-Queens)")
print("="*60)
# Тестируем для N=4
print("\n1. Доска 4×4:")
solutions_4 = solve_n_queens(4)
print_solutions(solutions_4)
# Тестируем для N=8 (только количество решений)
print("\n2. Доска 8×8 (только количество решений):")
count_8 = solve_n_queens_optimized(8)
print(f" Всего решений для доски 8×8: {count_8}")
# Выводим первое решение для доски 8×8
print("\n3. Первое решение для доски 8×8:")
solutions_8 = solve_n_queens(8)
if solutions_8:
print(" Первые 4 строки первого решения:")
for i in range(4):
row_display = solutions_8[0][i].replace('.', '◻').replace('Q', '♕')
print(f" {row_display}")
print(" ...")
print(" (полное решение содержит 8 строк)")
# Демонстрация оптимизированного подсчета для разных N
print("\n" + "="*60)
print("Количество решений для разных размеров доски:")
print("="*60)
for n in range(1, 11):
count = solve_n_queens_optimized(n)
print(f" Доска {n}×{n}: {count} решение(ий)")
Эти реализации охватывают все 10 задач. Каждая содержит:
- Подробный алгоритм решения
- Реализацию с комментариями на русском языке
- Пример использования с выводом
- В некоторых случаях - оптимизированную версию
Как практиковаться дальше
Чтобы закрепить навыки, важно решать задачи на специализированных платформах. В таблице ниже приведены некоторые из них.
| Платформа | Особенности | Уровень сложности |
|---|---|---|
| LeetCode | Задачи для подготовки к собеседованиям, обширные коллекции. | От начального до продвинутого |
| HackerRank | Соревнования, спонсируемые IT-компаниями, хороши для резюме. | Разный |
| Codewars | Геймификация, задачи (ката) для оттачивания навыков. | От начального до продвинутого |
| CodinGame | Игровой процесс с помощью написания кода. | Разный |
| PyTutor | Русскоязычный ресурс с задачами по Python. | Начальный и средний |
Если вы хотите глубже разобраться в реализации конкретной задачи из списка (например, Skyline Problem или N-Queens), дайте знать — я могу подготовить подробный разбор с кодом.