Ниже — краткие задачи и компактные решения на Python для уровней $3$–$10$. К каждому уровню — задача, код и сложность.
Уровень $3$ — сумма массива
Задача: вернуть сумму элементов.
Код:
def sum_arr(a):
return sum(a)
Сложность: $O(n)$.
Уровень $4$ — количество различных элементов
Задача: вернуть число уникальных элементов.
Код:
def count_unique(a):
return len(set(a))
Сложность: $O(n)$.
Уровень $5$ — Two Sum (пара с заданной суммой)
Задача: найти индексы двух чисел с суммой target.
Код:
def two_sum(a, target):
seen = {}
for i, x in enumerate(a):
need = target - x
if need in seen:
return (seen[need], i)
seen[x] = i
return None
Сложность: $O(n)$.
Уровень $6$ — бинарный поиск
Задача: найти индекс элемента в отсортированном массиве.
Код:
def binary_search(a, x):
l, r = 0, len(a) - 1
while l <= r:
m = (l + r) // 2
if a[m] == x: return m
if a[m] < x: l = m + 1
else: r = m - 1
return -1
Сложность: $O(\log n)$.
Уровень $7$ — группировка анаграмм
Задача: сгруппировать слова-анagramмы.
Код:
from collections import defaultdict
def group_anagrams(words):
d = defaultdict(list)
for w in words:
d[''.join(sorted(w))].append(w)
return list(d.values())
Сложность: $O(nk\log k)$ (где $k$ — средняя длина слова).
Уровень $8$ — топологическая сортировка (Kahn)
Задача: топологическая сортировка ориентированного ацикличного графа (вернуть None при цикле).
Код:
from collections import deque
def topo_sort(n, edges):
g = [[] for _ in range(n)]
indeg = [0]*n
for u, v in edges:
g[u].append(v); indeg[v] += 1
q = deque([i for i in range(n) if indeg[i] == 0])
res = []
while q:
u = q.popleft(); res.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0: q.append(v)
return res if len(res) == n else None
Сложность: $O(n+m)$ (где $m$ — число рёбер).
Уровень $9$ — Dijkstra (кратчайшие пути с неотрицательными весами)
Задача: расстояния от источника в взвешенном графе.
Код:
import heapq
def dijkstra(n, adj, src):
dist = [float('inf')]*n
dist[src] = 0
pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: continue
for v, w in adj[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist
Сложность: $O((n+m)\log n)$.
Уровень $10$ — Edmonds–Karp (максимальный поток)
Задача: найти максимальный поток между s и t.
Код:
from collections import deque
def edmonds_karp(n, edges, s, t):
cap = [[0]*n for _ in range(n)]
g = [[] for _ in range(n)]
for u, v, c in edges:
cap[u][v] += c
g[u].append(v); g[v].append(u)
flow = 0
while True:
q = deque([s]); parent = [-1]*n; parent[s] = s
while q and parent[t] == -1:
u = q.popleft()
for v in g[u]:
if parent[v] == -1 and cap[u][v] > 0:
parent[v] = u; q.append(v)
if parent[t] == -1: break
f = float('inf'); v = t
while v != s:
u = parent[v]; f = min(f, cap[u][v]); v = u
v = t
while v != s:
u = parent[v]
cap[u][v] -= f
cap[v][u] += f
v = u
flow += f
return flow
Сложность: $O(V{E}^2)$.
Если нужен конкретный язык, вход/выход или тесты — уточните.