《算法设计与分析》电子笔记

Python 实践与求职衔接

从原专题文件整合而来，直接在本课程目录内阅读。

目标：课内能证明、Python 能实现、面试能解释。适用于后端、测试开发、软件开发等岗位的通用算法能力培养；实际考核依公司、岗位而定。

一、课程知识 → Python → 高频面试场景

二、8 周可调整路线（每周 3–4 次，每次 30–60 分钟）

• 第 1 周：Python 容器、复杂度、二分边界；能手写二分左边界与右边界。
• 第 2 周：双指针、滑动窗口、排序与归并；理解输入规模和时间上界。
• 第 3 周：树与图、BFS/DFS；能够解释队列与栈的使用条件。
• 第 4 周：优先队列与 Dijkstra；用 heapq，验证无负权限制。
• 第 5 周：动态规划基础（爬楼梯、背包、LCS），写状态、转移、初值、遍历顺序。
• 第 6 周：贪心、区间问题、回溯；每个贪心方案至少尝试一个反例。
• 第 7 周：网络流/NP/近似理论以课内为主，编码完成一个最大流实现。
• 第 8 周：模拟笔试与复盘：45 分钟内实现 2 道简单/中等题，复核异常输入、复杂度和解释。

三、Python 标准库速查与正确使用

from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect_right
from heapq import heappush, heappop
from functools import lru_cache

q = deque([0]); q.append(1); q.popleft()    # 两端操作 O(1)
idx = bisect_left([1, 2, 2, 4], 2)          # 最左 2，下标 1

• list.append/pop() 尾端摊还 O(1)；pop(0) 是 O(n)；deque.popleft() O(1)。
• dict/set 的哈希操作平均 O(1)，理论最坏情况不保证 O(1)。
• heapq 是最小堆，入堆/出堆 O(log n)，取堆顶 O(1)。
• bisect 查找 O(log n)，但向列表插入元素仍是 O(n)。
• Python 递归深度有限；大图 DFS 生产环境更倾向显式栈，避免递归深度异常。

四、做一道题的 5 句话（面试答题模板）

1. 澄清输入：空数组、重复值、边界、是否有负数，约束范围是什么？
2. 说朴素法：明确它为什么太慢，时间空间各多少。
3. 提出优化：为什么选择某数据结构或状态转移，给出不变量。
4. 分析复杂度：最坏/平均/均摊不要混用；说明额外空间。
5. 举例测试：空集、单元素、重复值、极端值、无解/多解；必要时与暴力解交叉验证。

五、与项目和岗位结合

后端侧：可将优先队列用于异步任务调度、最短路用于路径搜索；测试开发侧：用随机对照测试与性质测试验证算法；数据方向：把随机过程仿真结果与数学期望对照，强调模型假设。项目叙述不要只说“用了 DP”，应说清数据规模、算法选择、测试覆盖与性能改善是否有实测证据。

六、随附代码

• practice_algorithms.html — 二分、归并、LCS、0-1 背包、活动安排、Dijkstra、n 皇后、最大流。
• tests/test_algorithms.html — 单元测试 + 小规模暴力对照。
• 在 算法/ 目录运行：python -m unittest discover -s tests -v。
• 本课目录（公式/证明与考试）→ 本指南（Python 实现）→ 实际岗位真题（按 JD 分类）。

七、资料推荐

• MIT 6.006 Introduction to Algorithms（系统课）
• Python heapq 官方文档、bisect 官方文档（实现细节）
• 《算法设计与分析》课堂课件与当前模块（考试题型）；求职题型按岗位补充，不宜把单一刷题清单当成所有公司的标准。

↑ 返回本课目录 · 课程资源与视频