Структури даних і алгоритмиШпаргалка

Шпаргалка: структури даних і алгоритми

Класи складності, типовий фрагмент коду для кожного патерну і підказки «що брати на задачу». Корисна поруч із LeetCode-практикою курсу.

Складність

Порядок зростання
Порівнюйте класи, а не секунди на маленькому тесті. На співбесіді зазвичай мають на увазі найгірший випадок.
$O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(2^n)$
Евристика часу
Близько $10^8$ простих операцій за секунду. Якщо $n=10^5$ і складність $O(n^2)$ — майже напевно перевищення ліміту часу.
Спочатку наївний перебір + оцінка складності, потім шукайте, що в ньому повторюється.

Два вказівники

Один масив, назустріч із країв

left і right сходяться до центру: пари з умовою на суму, паліндром, розворот на місці.

Python

def fn(arr):
    left, right = 0, len(arr) - 1
    ans = 0
    while left < right:
        if arr[left] + arr[right] < target:
            left += 1
        else:
            right -= 1
    return ans

Два масиви, поки не вичерпаються обидва

Кожен вказівник іде по своєму масиву: злиття двох відсортованих списків, порівняння двох послідовностей.

Python

def fn(arr1, arr2):
    i = j = ans = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            i += 1
        else:
            j += 1
    while i < len(arr1):
        i += 1
    while j < len(arr2):
        j += 1
    return ans

Ковзне вікно

Вікно змінного розміру

Підрядок або підмасив зі змінними межами: розширюйте right, стискайте left за умовою, оновлюйте відповідь.

Python

def fn(arr):
    left = ans = curr = 0
    for right in range(len(arr)):
        curr += arr[right]
        while curr > limit:
            curr -= arr[left]
            left += 1
        ans = max(ans, right - left + 1)
    return ans

Префіксні суми

Побудова префіксної суми
Сума будь-якого діапазону — за $O(1)$ після одної підготовки за $O(n)$ .
$\mathrm{sum}[L..R]=\mathrm{prefix}[R]-\mathrm{prefix}[L-1]$
Python
```
def build_prefix(arr):
    prefix = [arr[0]]
    for i in range(1, len(arr)):
        prefix.append(prefix[-1] + arr[i])
    return prefix
```

Підмасиви з точною сумою

Скільки підмасивів мають суму $k$ — префіксна сума разом зі словником її частот.

Python

from collections import defaultdict

def fn(arr, k):
    counts = defaultdict(int)
    counts[0] = 1
    ans = curr = 0
    for num in arr:
        curr += num
        ans += counts[curr - k]
        counts[curr] += 1
    return ans

Звʼязані списки

Швидкий і повільний вказівник
slow рухається на один вузол, fast — на два: пошук середини списку або циклу в ньому.
Python
```
def fn(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow
```

Розворот списку

Перебудова посилань на місці: кожен вузол показує на попередній замість наступного.

Python

def fn(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

Стек і черга

Монотонний стек

Стек, що завжди зростає або спадає: наступний більший елемент, часовий проміжок до зростання ціни.

Python

def fn(arr):
    stack = []
    ans = [0] * len(arr)
    for i, num in enumerate(arr):
        while stack and arr[stack[-1]] < num:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

Дерева

Обхід у глибину (рекурсія)
Найкоротший запис DFS: спуститись у ліве й праве піддерево, обробити результат на шляху назад.
Python
```
def dfs(node):
    if not node:
        return 0
    left = dfs(node.left)
    right = dfs(node.right)
    return 1 + max(left, right)
```

Обхід у глибину (стек)

Та сама ідея без рекурсії — явний стек, коли глибина дерева ризикує перевищити ліміт викликів.

Python

def dfs(root):
    stack = [root]
    ans = 0
    while stack:
        node = stack.pop()
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return ans

Обхід у ширину

Черга замість стека: вузли обробляються рівень за рівнем — зручно для «найкоротший шлях у дереві» чи відповіді по рівнях.

Python

from collections import deque

def bfs(root):
    queue = deque([root])
    ans = 0
    while queue:
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return ans

Графи

Обхід у глибину (рекурсія)

Вузли нумеруються від 0 до n−1, граф — списком суміжності. DFS знаходить компоненти й шляхи.

Python

def dfs(graph, start):
    seen = {start}

    def visit(node):
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                visit(neighbor)

    visit(start)
    return seen

Обхід у ширину

Найкоротший шлях у графі без ваг ребер — черга гарантує, що вузол відвідують на мінімальній відстані від старту.

Python

from collections import deque

def bfs(graph, start):
    queue = deque([start])
    seen = {start}
    steps = 0
    while queue:
        for _ in range(len(queue)):
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in seen:
                    seen.add(neighbor)
                    queue.append(neighbor)
        steps += 1
    return steps

Алгоритм Дейкстри

Найкоротший шлях у графі з невідʼємними вагами ребер: завжди обробляти найближчий ще не завершений вузол.

O((V+E)\log V)

Python

from heapq import heappush, heappop

def dijkstra(graph, start, n):
    distances = [float("inf")] * n
    distances[start] = 0
    heap = [(0, start)]
    while heap:
        dist, node = heappop(heap)
        if dist > distances[node]:
            continue
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heappush(heap, (new_dist, neighbor))
    return distances

У курсі поки немає окремого уроку на зважені графи — цей фрагмент тут як довідка на майбутнє.

Купа (heap)

Топ-k елементів

Купа розміром k тримає лише k найкращих кандидатів — не треба сортувати весь масив.

Python

import heapq

def fn(arr, k):
    heap = []
    for num in arr:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap

Бінарний пошук

Класичний пошук

На відсортованому масиві: кожен крок відсікає половину діапазону.

O(\log n)

Python

def fn(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return left

Пошук по простору відповідей

Дані не обовʼязково відсортовані — відсортована сама відповідь: чи підходить кандидат x, перевіряє окрема функція.

Python

def fn(arr):
    def check(x):
        return True

    left, right = MIN_ANSWER, MAX_ANSWER
    while left < right:
        mid = (left + right) // 2
        if check(mid):
            right = mid
        else:
            left = mid + 1
    return left

Бектрекінг

Каркас перебору з відкатом
Будуємо кандидата крок за кроком, а після кожної спроби відкочуємо зміну — усі підмножини, розміщення, комбінації.
Python
```
def backtrack(curr, options):
    if is_valid(curr):
        record(curr)
        return
    for option in options:
        curr.append(option)
        backtrack(curr, options)
        curr.pop()
```

Динамічне програмування

Зверху вниз з мемоізацією
Рекурсія лишається, але кожен стан рахується один раз і кешується в словнику.
Python
```
def fn(arr):
    memo = {}

    def dp(state):
        if state in base_cases:
            return base_cases[state]
        if state in memo:
            return memo[state]
        memo[state] = recurrence(state)
        return memo[state]

    return dp(start_state)
```
Знизу вгору — той самий стан, але в масиві й циклами замість викликів: заповнюйте від базового випадку до відповіді на весь вхід.

Трі (префіксне дерево)

Побудова тРі зі слів

Кожен вузол — один символ; спільні префікси слів діляють один шлях у дереві. Швидкий пошук за префіксом.

Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

def build_trie(words):
    root = TrieNode()
    for word in words:
        curr = root
        for ch in word:
            if ch not in curr.children:
                curr.children[ch] = TrieNode()
            curr = curr.children[ch]
        curr.is_word = True
    return root

У курсі поки немає окремого уроку на трі — цей фрагмент тут як довідка на майбутнє.

← До програми курсу

Складність

Порядок зростання

Евристика часу

Два вказівники

Один масив, назустріч із країв

Два масиви, поки не вичерпаються обидва

Ковзне вікно

Вікно змінного розміру

Префіксні суми

Побудова префіксної суми

Підмасиви з точною сумою

Звʼязані списки

Швидкий і повільний вказівник

Розворот списку

Стек і черга

Монотонний стек

Дерева

Обхід у глибину (рекурсія)

Обхід у глибину (стек)

Обхід у ширину

Графи

Обхід у глибину (рекурсія)

Обхід у ширину

Алгоритм Дейкстри

Купа (heap)

Топ-k елементів

Бінарний пошук

Класичний пошук

Пошук по простору відповідей

Бектрекінг

Каркас перебору з відкатом

Динамічне програмування

Зверху вниз з мемоізацією

Трі (префіксне дерево)

Побудова тРі зі слів