بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 35: درهم‌سازی و گراف‌ها Hashing and Graphs

الگوهای پرکاربرد dict و Counter (مثل two-sum و گروه‌بندی آناگرام‌ها) را می‌بینیم، گراف را با فهرست مجاورت (adjacency list) مدل می‌کنیم و با BFS کوتاه‌ترین مسیر را پیدا می‌کنیم.

در این جلسه یاد می‌گیری

درس

dict و set با hash کار می‌کنند: کلید به یک عدد تبدیل می‌شود و مستقیم به خانه‌ی مربوط می‌رود؛ خواندن و نوشتن میانگین O(1). کلید باید hashable (تغییرناپذیر) باشد: str، int، tuple بله؛ list نه.

from collections import Counter, defaultdict

words = "to be or not to be".split()
print(Counter(words).most_common(2))
groups = defaultdict(list)
for w in words:
    groups[len(w)].append(w)
print(dict(groups))

الگوی two-sum: به‌جای امتحان همه‌ی جفت‌ها (O(n²))، در یک گذر برای هر x بپرسید آیا target - x قبلاً دیده شده؛ dict مقدار ← اندیس آن را در O(1) جواب می‌دهد. همین ایده با پیشوند جمع، «تعداد زیرآرایه‌هایی با جمع k» را در O(n) حل می‌کند.

def two_sum(nums, target):
    seen = {}
    for j, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], j
        seen[x] = j
    return None

print(two_sum([2, 7, 11, 15], 9))

گراف = گره‌ها (node) + یال‌ها (edge). فهرست مجاورت یک dict از گره به لیست همسایه‌هاست؛ حافظه O(V + E). در گراف بدون جهت هر یال را در دو جهت اضافه کنید.

from collections import defaultdict

edges = [("A", "B"), ("A", "C"), ("B", "D")]
graph = defaultdict(list)
for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)
print(dict(graph))

جست‌وجوی سطح‌اول (BFS) از مبدأ لایه‌به‌لایه پیش می‌رود: اول همه‌ی گره‌های با فاصله‌ی ۱، بعد ۲ و... پس در گراف بدون وزن، اولین باری که به گره‌ای می‌رسیم کوتاه‌ترین فاصله را داریم. صف (deque) + dist (که نقش visited را هم دارد)؛ زمان O(V + E).

from collections import deque

def bfs(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist

برای بازسازی مسیر، هنگام کشف هر گره والدش (parent) را ذخیره کنید و از مقصد به عقب برگردید. شبکه‌ی دوبعدی (grid) هم گراف است: هر خانه‌ی باز یک گره و چهار همسایه‌ی بالا/پایین/چپ/راست یال‌ها هستند.

def path_to(parent, goal):
    path = []
    while goal is not None:
        path.append(goal)
        goal = parent[goal]
    return path[::-1]

print(path_to({"A": None, "B": "A", "D": "B"}, "D"))

مثال‌های این جلسه

چالش‌ها

  1. Top Words (آسان)
  2. Two Sum (آسان)
  3. Adjacency List (آسان)
  4. Anagram Groups (متوسط)
  5. BFS Order (متوسط)
  6. Degrees of Separation (متوسط)
  7. First Unique Character (متوسط)
  8. Route Planner (سخت)
  9. Grid Shortest Path (سخت)
  10. Connected Components (سخت)
  11. Subarrays with Sum K (متوسط)
  12. Build Order (سخت)

بیشتر بخوان

← جلسه‌ی 34: پشته و صف جلسه‌ی 36: پروژه: حل‌کننده‌ی ماز →