数据结构与算法

面试与工程优化都依赖复杂度意识与标准结构的熟练实现。Python 内置 list/dict 已很强，本课补 deque、heapq、bisect 与常见模式。语言基础 python-fundamentals；Agent 检索/RAG 涉及向量与排序，见 ai-agents-essentials；/roadmaps/python。

学习目标

• 分析时间/空间复杂度（Big-O 直觉）
• 熟练使用 collections.deque、heapq、bisect
• 实现 BFS/DFS 与二分查找模板

复杂度速查

操作	list	dict	deque
末尾 append	O(1)*	—	O(1)
头部 pop	O(n)	—	O(1)
按键查找	—	O(1) avg	—

* 均摊

deque 与 BFS

from collections import deque

def bfs(graph: dict[str, list[str]], start: str) -> list[str]:
    visited: set[str] = set()
    order: list[str] = []
    queue: deque[str] = deque([start])
    while queue:
        node = queue.popleft()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        queue.extend(graph.get(node, []))
    return order

graph = {"a": ["b", "c"], "b": ["d"], "c": [], "d": []}
print(bfs(graph, "a"))  # ['a', 'b', 'c', 'd']

heapq Top-K

import heapq

def top_k_lessons(scores: dict[str, int], k: int) -> list[tuple[int, str]]:
    # 最小堆维护 K 个最大分数
    heap: list[tuple[int, str]] = []
    for slug, score in scores.items():
        heapq.heappush(heap, (score, slug))
        if len(heap) > k:
            heapq.heappop(heap)
    return sorted(heap, reverse=True)

scores = {"pya-intro": 90, "pya-async": 95, "pya-dsa": 88}
print(top_k_lessons(scores, 2))

二分查找

import bisect

sorted_slugs = ["pya-async", "pya-dsa", "pya-intro", "pya-web"]
idx = bisect.bisect_left(sorted_slugs, "pya-intro")
print(idx)  # 2

LeetCode / 剑指 Offer 可用 Python 练手；注意 Python 递归深度限制（DFS 深图改迭代或 sys.setrecursionlimit 谨慎使用）。

练习

• 用 DFS 递归实现图的遍历，与 BFS 结果对比