← Назад к курсу
Погружение в алгоритмы на Python от простого к сложному: 8 групп по 3 задачи в каждой
В этом материале представлена расширенная подборка: по 3 простые и наглядные задачи на каждую из 8 ключевых тем. Все задачи расположены в порядке возрастания сложности внутри каждой темы.
Часть 1: Строки, Простые списки, Числа, Матрицы
1. СТРОКИ
Задача 1.1: Подсчёт гласных букв
Задача: Посчитать количество гласных букв в строке (латиница или кириллица).
def count_vowels(s: str) -> int:
"""
Подсчёт гласных букв в строке (регистр не учитывается).
"""
vowels = "aeiouаеёиоуыэюя"
count = 0
for char in s.lower(): # Приводим к нижнему регистру
if char in vowels:
count += 1
return count
# Пример
print(count_vowels("Hello World!")) # 3 (e, o, o)
print(count_vowels("Привет мир")) # 3 (и, е, и)
Задача 1.2: Проверка анаграммы
Задача: Проверить, являются ли две строки анаграммами (состоят из одних и тех же букв).
def is_anagram(s1: str, s2: str) -> bool:
"""
Проверяет, являются ли строки анаграммами.
"""
# Убираем пробелы и приводим к одному регистру
s1 = s1.replace(" ", "").lower()
s2 = s2.replace(" ", "").lower()
# Сравниваем отсортированные символы
return sorted(s1) == sorted(s2)
# Пример
print(is_anagram("listen", "silent")) # True
print(is_anagram("hello", "world")) # False
Задача 1.3: Самый частый символ
Задача: Найти символ, который встречается в строке чаще всего.
def most_frequent_char(s: str) -> str:
"""
Находит самый частый символ в строке.
"""
char_count = {}
# Подсчитываем каждый символ
for char in s:
if char != " ": # Пробелы игнорируем
char_count[char] = char_count.get(char, 0) + 1
# Ищем символ с максимальным количеством
if not char_count:
return ""
return max(char_count, key=char_count.get)
# Пример
print(most_frequent_char("программирование")) # 'р' (встречается 3 раза)
print(most_frequent_char("hello world")) # 'l' (3 раза)
2. ПРОСТЫЕ СПИСКИ (МАССИВЫ)
Задача 2.1: Поиск минимального и максимального элементов
Задача: Найти минимальный и максимальный элементы в списке за один проход.
def find_min_max(arr: list) -> tuple:
"""
Находит минимальный и максимальный элементы в списке.
Возвращает кортеж (min, max).
"""
if not arr:
return None, None
min_val = max_val = arr[0]
for num in arr[1:]: # Начинаем со второго элемента
if num < min_val:
min_val = num
elif num > max_val:
max_val = num
return min_val, max_val
# Пример
arr = [3, 5, 1, 8, 2, 7]
min_val, max_val = find_min_max(arr)
print(f"Min: {min_val}, Max: {max_val}") # Min: 1, Max: 8
Задача 2.2: Перевернуть список
Задача: Создать новый список с элементами в обратном порядке.
def reverse_list(arr: list) -> list:
"""
Возвращает новый список с элементами в обратном порядке.
"""
# Способ 1: Срез
return arr[::-1]
# Способ 2: Через цикл
# reversed_arr = []
# for i in range(len(arr)-1, -1, -1):
# reversed_arr.append(arr[i])
# return reversed_arr
# Пример
arr = [1, 2, 3, 4, 5]
print(reverse_list(arr)) # [5, 4, 3, 2, 1]
Задача 2.3: Удалить дубликаты из отсортированного списка
Задача: Удалить повторяющиеся элементы из отсортированного списка (in-place).
def remove_duplicates_sorted(arr: list) -> int:
"""
Удаляет дубликаты из отсортированного списка.
Возвращает новую длину списка.
"""
if not arr:
return 0
# Указатель на место для уникального элемента
unique_index = 0
for i in range(1, len(arr)):
if arr[i] != arr[unique_index]:
unique_index += 1
arr[unique_index] = arr[i]
# Обрезаем список до уникальных элементов
del arr[unique_index+1:]
return unique_index + 1
# Пример
arr = [1, 1, 2, 2, 2, 3, 4, 4, 5]
new_length = remove_duplicates_sorted(arr)
print(f"Новая длина: {new_length}, список: {arr}")
# Новая длина: 5, список: [1, 2, 3, 4, 5]
3. ЧИСЛА
Задача 3.1: Чётное или нечётное
Задача: Определить, является ли число чётным.
def is_even(n: int) -> bool:
"""
Проверяет, является ли число чётным.
"""
return n % 2 == 0
# Пример
print(is_even(10)) # True
print(is_even(7)) # False
Задача 3.2: Сумма цифр числа
Задача: Найти сумму цифр заданного числа.
def sum_of_digits(n: int) -> int:
"""
Вычисляет сумму цифр числа.
"""
n = abs(n) # Работаем с положительными числами
total = 0
while n > 0:
total += n % 10 # Берём последнюю цифру
n //= 10 # Убираем последнюю цифру
return total
# Пример
print(sum_of_digits(12345)) # 1+2+3+4+5 = 15
print(sum_of_digits(987)) # 9+8+7 = 24
Задача 3.3: Числа Фибоначчи (первые N чисел)
Задача: Вывести первые N чисел последовательности Фибоначчи.
def fibonacci(n: int) -> list:
"""
Генерирует первые N чисел Фибоначчи.
"""
if n <= 0:
return []
elif n == 1:
return [0]
fib = [0, 1]
for i in range(2, n):
fib.append(fib[i-1] + fib[i-2])
return fib[:n] # Возвращаем ровно N чисел
# Пример
print(fibonacci(10)) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
4. МАТРИЦЫ
Задача 4.1: Сумма всех элементов матрицы
Задача: Найти сумму всех элементов в матрице (списке списков).
def matrix_sum(matrix: list[list]) -> int:
"""
Вычисляет сумму всех элементов матрицы.
"""
total = 0
for row in matrix:
for element in row:
total += element
return total
# Пример
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print(f"Сумма всех элементов: {matrix_sum(matrix)}") # 45
Задача 4.2: Транспонирование матрицы
Задача: Найти транспонированную матрицу (строки становятся столбцами).
def transpose_matrix(matrix: list[list]) -> list[list]:
"""
Возвращает транспонированную матрицу.
"""
# Определяем размеры исходной матрицы
rows = len(matrix)
cols = len(matrix[0])
# Создаём новую матрицу с перевёрнутыми размерами
transposed = [[0] * rows for _ in range(cols)]
for i in range(rows):
for j in range(cols):
transposed[j][i] = matrix[i][j]
return transposed
# Пример
matrix = [
[1, 2, 3],
[4, 5, 6]
]
print("Транспонированная матрица:")
for row in transpose_matrix(matrix):
print(row)
# [1, 4]
# [2, 5]
# [3, 6]
Задача 4.3: Сумма элементов главной диагонали
Задача: Найти сумму элементов на главной диагонали квадратной матрицы.
def diagonal_sum(matrix: list[list]) -> int:
"""
Вычисляет сумму элементов главной диагонали.
Матрица должна быть квадратной.
"""
total = 0
n = len(matrix) # Размер квадратной матрицы
for i in range(n):
total += matrix[i][i] # Элементы с одинаковыми индексами
return total
# Пример
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
print(f"Сумма главной диагонали: {diagonal_sum(matrix)}") # 1+5+9 = 15
Часть 2: Связанные списки, Деревья, Кучи, Графы
5. СВЯЗАННЫЕ СПИСКИ
Задача 5.1: Подсчёт длины списка
Задача: Найти количество узлов в односвязном списке.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def list_length(head: ListNode) -> int:
"""
Подсчитывает количество узлов в списке.
"""
count = 0
current = head
while current:
count += 1
current = current.next
return count
# Создаём список: 1 -> 2 -> 3 -> 4
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
print(f"Длина списка: {list_length(head)}") # 4
Задача 5.2: Поиск элемента в списке
Задача: Проверить, содержится ли значение в односвязном списке.
def contains_value(head: ListNode, target: int) -> bool:
"""
Проверяет, содержится ли значение в списке.
"""
current = head
while current:
if current.val == target:
return True
current = current.next
return False
# Создаём список: 5 -> 10 -> 15 -> 20
head = ListNode(5, ListNode(10, ListNode(15, ListNode(20))))
print(contains_value(head, 15)) # True
print(contains_value(head, 25)) # False
Задача 5.3: Поиск середины списка (медленный и быстрый указатели)
Задача: Найти средний узел односвязного списка.
def find_middle(head: ListNode) -> ListNode:
"""
Находит средний узел списка методом двух указателей.
"""
if not head:
return None
slow = head # Медленный указатель (1 шаг за раз)
fast = head # Быстрый указатель (2 шага за раз)
while fast and fast.next:
slow = slow.next # Медленный на 1 шаг
fast = fast.next.next # Быстрый на 2 шага
return slow # Когда быстрый достиг конца, медленный в середине
# Создаём список: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
middle = find_middle(head)
print(f"Средний элемент: {middle.val}") # 3
# Для списка с чётным количеством: 1 -> 2 -> 3 -> 4
head2 = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
middle2 = find_middle(head2)
print(f"Средний элемент (чётный список): {middle2.val}") # 3 (второй из двух средних)
6. ДЕРЕВЬЯ
Задача 6.1: Поиск в бинарном дереве поиска (BST)
Задача: Проверить, содержится ли значение в бинарном дереве поиска.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def search_bst(root: TreeNode, target: int) -> bool:
"""
Ищет значение в бинарном дереве поиска.
"""
current = root
while current:
if current.val == target:
return True
elif target < current.val: # Идём влево
current = current.left
else: # Идём вправо
current = current.right
return False
# Создаём BST:
# 5
# / \
# 3 7
# / \ \
# 2 4 8
root = TreeNode(5)
root.left = TreeNode(3, TreeNode(2), TreeNode(4))
root.right = TreeNode(7, None, TreeNode(8))
print(search_bst(root, 4)) # True
print(search_bst(root, 6)) # False
Задача 6.2: Высота бинарного дерева
Задача: Найти высоту (максимальную глубину) бинарного дерева.
def tree_height(root: TreeNode) -> int:
"""
Вычисляет высоту бинарного дерева.
Высота пустого дерева = -1, дерева с одним узлом = 0.
"""
if not root:
return -1 # Или 0, зависит от определения
left_height = tree_height(root.left)
right_height = tree_height(root.right)
return max(left_height, right_height) + 1
# Создаём дерево:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2, TreeNode(4), TreeNode(5))
root.right = TreeNode(3)
print(f"Высота дерева: {tree_height(root)}") # 2
Задача 6.3: Симметричное дерево
Задача: Проверить, является ли бинарное дерево симметричным (зеркальным).
def is_symmetric(root: TreeNode) -> bool:
"""
Проверяет, является ли дерево симметричным.
"""
def is_mirror(left: TreeNode, right: TreeNode) -> bool:
if not left and not right:
return True
if not left or not right:
return False
# Значения должны совпадать, и поддеревья быть зеркальными
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
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
7. КУЧИ (ОЧЕРЕДИ С ПРИОРИТЕТОМ)
Задача 7.1: K-й наименьший элемент (через кучу)
Задача: Найти k-й наименьший элемент в массиве с использованием кучи.
import heapq
def kth_smallest(arr: list, k: int) -> int:
"""
Находит k-й наименьший элемент с помощью кучи.
"""
if k <= 0 or k > len(arr):
return None
# Создаём минимальную кучу из всех элементов
heapq.heapify(arr) # Преобразуем список в кучу за O(n)
# Извлекаем k раз минимальный элемент
for _ in range(k-1):
heapq.heappop(arr)
return heapq.heappop(arr) # k-й наименьший
# Пример
arr = [7, 10, 4, 3, 20, 15]
k = 3
print(f"{k}-й наименьший элемент: {kth_smallest(arr.copy(), k)}") # 7
Задача 7.2: Слияние отсортированных списков
Задача: Объединить K отсортированных списков в один отсортированный список.
def merge_sorted_lists(lists: list[list]) -> list:
"""
Объединяет несколько отсортированных списков в один.
"""
result = []
heap = []
# Добавляем первые элементы каждого списка в кучу
for i, lst in enumerate(lists):
if lst: # Если список не пустой
heapq.heappush(heap, (lst[0], i, 0)) # (значение, индекс_списка, индекс_элемента)
while heap:
value, list_idx, element_idx = heapq.heappop(heap)
result.append(value)
# Если в текущем списке есть следующий элемент
if element_idx + 1 < len(lists[list_idx]):
next_value = lists[list_idx][element_idx + 1]
heapq.heappush(heap, (next_value, list_idx, element_idx + 1))
return result
# Пример
list1 = [1, 4, 7]
list2 = [2, 5, 8]
list3 = [3, 6, 9]
merged = merge_sorted_lists([list1, list2, list3])
print(f"Объединённый список: {merged}") # [1, 2, 3, 4, 5, 6, 7, 8, 9]
Задача 7.3: Сортировка почти отсортированного массива
Задача: Отсортировать массив, в котором каждый элемент находится не дальше чем K позиций от своей правильной позиции.
def sort_k_sorted(arr: list, k: int) -> list:
"""
Сортирует почти отсортированный массив.
Каждый элемент находится не дальше чем k позиций от своего места.
"""
if not arr or k <= 0:
return arr
result = []
heap = []
# Добавляем первые k+1 элементов в кучу
for i in range(min(k + 1, len(arr))):
heapq.heappush(heap, arr[i])
# Для оставшихся элементов
for i in range(k + 1, len(arr)):
result.append(heapq.heappop(heap)) # Минимальный элемент
heapq.heappush(heap, arr[i])
# Добавляем оставшиеся элементы из кучи
while heap:
result.append(heapq.heappop(heap))
return result
# Пример
arr = [3, 2, 1, 5, 4, 7, 6, 8]
k = 2 # Каждый элемент не дальше чем на 2 позиции от своего места
print(f"Отсортированный массив: {sort_k_sorted(arr, k)}") # [1, 2, 3, 4, 5, 6, 7, 8]
8. ГРАФЫ
Задача 8.1: Поиск в глубину (DFS) рекурсивный
Задача: Обойти граф в глубину, начиная с заданной вершины.
def dfs_recursive(graph: dict, start: int, visited=None) -> list:
"""
Рекурсивный поиск в глубину.
"""
if visited is None:
visited = set()
result = []
visited.add(start)
result.append(start)
for neighbor in graph.get(start, []):
if neighbor not in visited:
result.extend(dfs_recursive(graph, neighbor, visited))
return result
# Граф: 0-1-2, 0-3, 1-4
graph = {
0: [1, 3],
1: [0, 2, 4],
2: [1],
3: [0],
4: [1]
}
print("DFS обход (рекурсивный):")
print(dfs_recursive(graph, 0)) # [0, 1, 2, 4, 3] (порядок может отличаться)
Задача 8.2: Поиск в ширину (BFS) для поиска кратчайшего пути в невзвешенном графе
Задача: Найти длину кратчайшего пути между двумя вершинами в невзвешенном графе.
from collections import deque
def shortest_path_bfs(graph: dict, start: int, end: int) -> int:
"""
Находит длину кратчайшего пути между двумя вершинами.
"""
if start == end:
return 0
visited = set([start])
queue = deque([(start, 0)]) # (вершина, расстояние от start)
while queue:
vertex, distance = queue.popleft()
for neighbor in graph.get(vertex, []):
if neighbor == end:
return distance + 1
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, distance + 1))
return -1 # Пути не существует
# Граф: 0-1-2-3
# | |
# 4-5-6
graph = {
0: [1, 4],
1: [0, 2],
2: [1, 3, 6],
3: [2],
4: [0, 5],
5: [4, 6],
6: [2, 5]
}
print(f"Кратчайший путь от 0 до 3: {shortest_path_bfs(graph, 0, 3)}") # 3 (0-1-2-3)
Задача 8.3: Подсчёт компонент связности
Задача: Найти количество компонент связности в неориентированном графе.
def count_connected_components(graph: dict) -> int:
"""
Подсчитывает количество компонент связности в графе.
"""
visited = set()
components = 0
def dfs(node):
"""Вспомогательная DFS-функция для обхода компоненты."""
stack = [node]
visited.add(node)
while stack:
current = stack.pop()
for neighbor in graph.get(current, []):
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
# Обходим все вершины графа
for vertex in graph:
if vertex not in visited:
components += 1
dfs(vertex)
return components
# Граф с 3 компонентами связности:
# 0-1 2-3 4
graph = {
0: [1],
1: [0],
2: [3],
3: [2],
4: []
}
print(f"Количество компонент связности: {count_connected_components(graph)}") # 3
Краткое резюме по всем задачам:
Строки:
- Подсчёт гласных - базовый перебор с проверкой вхождения
- Анаграммы - сравнение отсортированных символов
- Самый частый символ - подсчёт через словарь
Списки:
- Min/Max - один проход с двумя переменными
- Разворот - срез [::-1] или цикл
- Удаление дубликатов - два указателя для отсортированного массива
Числа:
- Чётность - проверка остатка от деления
- Сумма цифр - цикл с % 10 и // 10
- Фибоначчи - итеративное заполнение списка
Матрицы:
- Сумма элементов - двойной цикл
- Транспонирование - [j][i] вместо [i][j]
- Главная диагональ - элементы с одинаковыми индексами
Связанные списки:
- Длина списка - простой перебор
- Поиск элемента - перебор с проверкой
- Середина - метод двух указателей (черепаха и заяц)
Деревья:
- Поиск в BST - сравнение и переход влево/вправо
- Высота дерева - рекурсия с max(left, right) + 1
- Симметрия - проверка зеркальности поддеревьев
Кучи:
- K-й наименьший - heapify и k раз heappop
- Слияние списков - куча с кортежами (значение, индекс_списка)
- Сортировка почти отсортированного - скользящее окно размера k+1
Графы:
- DFS рекурсивный - рекурсия с посещёнными вершинами
- BFS кратчайший путь - очередь с расстояниями
- Компоненты связности - DFS/ BFS по непосещённым вершинам
Эти 24 задачи охватывают все базовые алгоритмические паттерны и дают прочную основу для решения более сложных задач.