1. 我重新梳理这套Python算法清单的缘由每隔一段时间总会有人在群里问一句python经典算法大全到底该从哪儿看起python算法有哪些是真正需要花时间掌握的。这个问题我回答过不下十遍但每次回答都不太一样因为提问的人背景差别太大。有的是刚学完语法想做点练习的有的是工作两年突然要准备技术考察的还有的是写业务代码写久了想回头把基础重新打一遍。所以这次索性把我会反复翻看的那部分算法整理成一份清单把每个模块为什么这么选、代码怎么写、哪些地方最容易出错都写清楚。这份内容适合谁如果你是刚接触 Python、能写函数但一遇到复杂度分析就发懵的新人可以从第 2、3 节顺着读如果你已经有项目经验只想找回手感、顺手补一下动态规划和图论直接跳到第 4、5 节也没问题。我不会把几十种算法全部罗列一遍那种清单在搜索结果的首页能找到一大堆但大多只有名字和一句解释看完还是不知道该怎么用。我关注的是那些在真实场景里被反复调用、被反复写错、被反复讨论的算法以及围绕它们的一整套工程习惯。先交代一个前提算法清单不应该按“考试大纲”来组织而应该按“使用频率 出错代价”来组织。一个排序写错可能只是结果顺序不对一个二分边界写错可能就是线上数据查不到一个并查集漏了路径压缩可能就让程序从毫秒级变成分钟级。这个思路决定了下面所有内容的排列顺序和取舍方式。2. 排序与查找最基础也是最容易出问题的地方2.1 快速排序、归并与堆排序之间的选择排序是所有人学算法的第一站但真正到了写代码的时候绝大多数情况直接调用sorted()就够了。Python 内置的 Timsort 是归并和插入排序的混合实现平均和最坏都是 O(n log n)而且对部分有序的数据有额外优化手写基本不可能比它快。所以我一般只在两种情况下手写排序一是需要理解分治思想二是需要做“部分排序”或者“只取前 K 个”这类内置函数不方便处理的场景。快速排序值得手写的核心原因不是它快而是它把“分治 原地交换”这套模式展示得最干净。我常用的版本做了两件事三数取中选基准以及小区间切换插入排序。前者用来规避已经有序的输入导致的 O(n²) 退化后者是因为递归到 16 个元素以下时递归开销已经超过比较开销了。def quick_sort(arr, lo0, hiNone): if hi is None: hi len(arr) - 1 while lo hi: if hi - lo 16: insertion_sort(arr, lo, hi) return mid lo (hi - lo) // 2 # 三数取中把中位数换到 lo 位置 if arr[mid] arr[lo]: arr[lo], arr[mid] arr[mid], arr[lo] if arr[hi] arr[lo]: arr[lo], arr[hi] arr[hi], arr[lo] if arr[hi] arr[mid]: arr[mid], arr[hi] arr[hi], arr[mid] arr[lo], arr[mid] arr[mid], arr[lo] pivot arr[lo] i, j lo, hi while i j: while i j and arr[j] pivot: j - 1 arr[i] arr[j] while i j and arr[i] pivot: i 1 arr[j] arr[i] arr[i] pivot # 先递归较短的一侧控制栈深度 if i - lo hi - i: quick_sort(arr, lo, i - 1) lo i 1 else: quick_sort(arr, i 1, hi) hi i - 1 return arr这段代码有两个细节值得单独拿出来说。第一个是i, j双指针加“挖坑填数”的写法比左右交换的写法少一半赋值操作实测在几十万级别的列表上差距能到 15% 左右。第二个是“先递归较短的一侧”这个尾递归优化它把最坏情况下的递归栈深度从 O(n) 压到 O(log n)避免数据量一大就触发递归深度限制。归并排序的适用场景和快排不太一样。快排是原地排序空间 O(log n)归并需要额外 O(n) 空间但它是稳定排序而且天然适合处理外部排序和链表排序。我处理链表排序时基本只用归并因为链表没法随机访问快排的 partition 在链表上非常别扭。堆排序的优势在于最坏情况也是 O(n log n) 且空间 O(1)但它不稳定、缓存不友好实际项目里我用它的次数屈指可数更多是拿堆这个结构去做优先队列而不是拿堆排序去排数组。下面这张表是我自己整理的选择依据遇到具体问题时可以直接对照场景推荐方案理由通用列表排序内置sorted()Timsort 稳定且有局部有序优化教学 / 理解分治快排原地、思路清晰、参数少链表排序归并不需要随机访问稳定只取前 K 个heapq.nlargest/ 小顶堆复杂度 O(n log k)不必全排数据量大且内存吃紧堆排序原地最坏 O(n log n)注意手写快排时不要用arr[0]当基准也不要对已经有序的数据做测试就下结论。真实数据里“部分有序”非常常见比如按时间戳追加的日志这时候固定基准会直接退化。2.2 二分查找边界写错一次就够记一辈子二分查找的代码只有十来行但它是公认最容易写错的算法之一。根因不在算法本身而在于“区间定义”这件事没有被统一。我现在的习惯是全程只用左闭右开区间[lo, hi)所有变体都在这套约定下推不再混用闭区间写法。def lower_bound(arr, target): 返回第一个 target 的下标找不到返回 len(arr) lo, hi 0, len(arr) while lo hi: mid lo (hi - lo) // 2 if arr[mid] target: lo mid 1 else: hi mid return lo这个模板能覆盖绝大部分需求要判断存在性就看lo len(arr) and arr[lo] target要找最后一个小于等于 target 的位置就换成upper_bound再减一要在旋转数组里查找只改判断条件不改框架。统一模板的价值在于你不需要每次重新推导边界只要记住“循环结束时 lo 是答案”这一条。mid lo (hi - lo) // 2这种写法不是为了好看。在支持 int 溢出的语言里它能防止溢出在 Python 里虽然没有溢出问题但保持这个习惯可以让你在跨语言写代码时不用重新想一遍。有一个坑我踩过对浮点数做二分时用while lo hi会陷入死循环因为两个浮点数之间永远存在更近的值。这种情况要么改成固定迭代次数比如 100 次要么给区间加一个精度阈值while hi - lo 1e-7。我一般用固定次数因为精度阈值在不同量级的数据上不好统一。3. 数据结构类算法栈、队列、哈希与并查集3.1 该用内置结构还是自己手写这个问题的答案很明确业务代码里全部用内置结构。list当栈用collections.deque当队列用dict当哈希表用heapq当优先队列用。Python 的内置实现是 C 层优化过的手写一遍性能只会更差。但“用内置”不等于“不用懂”。栈和队列的价值在于它们约束了访问顺序这个约束本身就是算法设计的一部分。比如用栈做括号匹配、用单调栈求下一个更大元素、用 deque 做滑动窗口最大值这些都是把数据结构当成“状态容器”来用而不是简单地存数据。单调栈这个模式特别值得单独练它的核心是“维护一个单调递增或递减的栈入栈前弹掉破坏单调性的元素”一旦理解了这个动作接雨水、柱状图最大矩形、滑动窗口最大值这一串题目就是同一套逻辑换个外套。哈希表这块我要提醒的是“哈希冲突”和“可哈希性”两个概念。Python 的dict用开放寻址法处理冲突平均 O(1)但如果你自定义了__eq__却没定义__hash__这个类就变成不可哈希的塞不进set和dict。反过来如果两个对象相等但哈希值不同字典查找就会失效。这是一个很隐蔽的 bug表现出来是“明明放进去了却查不到”。3.2 并查集路径压缩不能省并查集是那种“代码极短、作用极大、细节极易漏”的结构典型用于连通性判断、朋友圈合并、岛屿数量统计这类问题。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n self.count n # 连通分量个数 def find(self, x): # 迭代版路径压缩避免递归深度问题 root x while self.parent[root] ! root: root self.parent[root] while self.parent[x] ! root: self.parent[x], x root, self.parent[x] return root def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return False # 按秩合并把矮树挂到高树下面 if self.rank[rx] self.rank[ry]: rx, ry ry, rx self.parent[ry] rx if self.rank[rx] self.rank[ry]: self.rank[rx] 1 self.count - 1 return True三个细节第一find用迭代不用递归因为路径压缩后的树虽然矮但极端情况下仍可能很深递归有栈溢出风险第二路径压缩和按秩合并一起用复杂度才接近常数只用其中一个会退化成 O(log n)第三用count维护连通分量个数比每次遍历统计快得多这是图上判环的关键。我见过一个真实案例某项目用并查集做大批量数据的分组只做了路径压缩没做按秩合并单次操作平均下来还是很快但在“先大量 union 再集中 find”的模式下性能比两者都用慢了将近 3 倍。这不是理论问题是实测出来的。4. 动态规划与贪心思路永远比代码重要4.1 动态规划的四步定式动态规划是很多人卡住的地方卡点通常不是写不出代码而是不知道状态该怎么定义。我现在的做法是固定走四步定义状态、写转移方程、确定初始值和边界、确定遍历顺序。这四步里第一步和第四步最容易错代码反而是最简单的。以 0-1 背包为例。状态定义成dp[i][j]表示“前 i 个物品、容量 j 时的最大价值”转移方程是“不选第 i 个”和“选第 i 个”取较大值。到这里还没完关键在遍历顺序01 背包用一维数组优化时容量必须从大到小遍历因为每个物品只能用一次完全背包则从小到大因为物品可以重复用。这个顺序差异不是记忆题而是由“当前状态依赖的是本层还是上一层”决定的。def knapsack_01(weights, values, cap): dp [0] * (cap 1) for i in range(len(weights)): # 倒序遍历保证每件物品只被选一次 for j in range(cap, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[cap]另一个高频模式是最长递增子序列。O(n²) 的写法是dp[i]表示以 i 结尾的最长长度状态转移要遍历前面所有元素O(n log n) 的写法维护一个“最小结尾数组”用二分插入。后者不好想但它其实是“贪心 二分”的组合理解了“让每个长度的结尾尽可能小”这个贪心策略代码就只是辅助。我在实际使用中发现动态规划真正难的地方在于“能不能把问题拆成重叠子问题”。有些题看起来像 DP其实是贪心有些看起来像贪心其实必须 DP。判断标准是局部最优能不能推出全局最优。能就是贪心不能才需要 DP 枚举所有状态。4.2 贪心的适用边界与验证方法贪心的坑在于“看起来对”但实际不成立。我验证一个贪心策略是否正确的土办法是构造三个反例。第一个是“相邻两项交换后结果变差”的边界第二个是“局部最优但全局不是最优”的构造第三个是“相等值导致的并列选择”。三个都能顶住才敢用。典型的贪心场景包括区间调度按结束时间排序、分发饼干双指针匹配、跳跃游戏维护最远可达位置。这些问题的共性是存在一个明确的“排序依据”排完序之后每一步的最优选择都是确定的。如果没有明确的排序依据或者排序依据需要反复调整那多半不是贪心。提示写完贪心不要急着提交先用小规模数据暴力枚举所有方案和贪心结果对比。这一步花不了五分钟但能省掉一次返工。5. 图论与字符串工程里真正会碰到的部分5.1 图遍历与最短路的选择图的表示我一般只用两种邻接表用dict[list]存适合稀疏图邻接矩阵用二维列表存适合稠密图或者需要 O(1) 判断两点是否相邻的场景。绝大多数业务问题是稀疏图所以邻接表用得最多。BFS 和 DFS 的选择取决于你要什么。求最短步数用 BFS因为它是按层扩展的第一次访问到目标时路径一定最短求所有路径、做连通性判断、做拓扑排序用 DFS因为它的递归结构天然适合回溯。这里有个细节BFS 的 visited 标记必须在入队时就打上不能等出队才打否则同一个节点可能被重复入队队列会急剧膨胀。这个错误在网格类问题上特别常见。Dijkstra 是带权最短路的默认选择用heapq实现优先队列复杂度 O((VE) log V)。它的前提是边权非负一旦出现负权就必须换 Bellman-Ford 或 SPFA。这一点在实际项目里要特别注意因为“负数权重”往往不会写在需求里而是从数据里冒出来的。import heapq def dijkstra(graph, start): dist {node: float(inf) for node in graph} dist[start] 0 heap [(0, start)] while heap: d, u heapq.heappop(heap) if d dist[u]: continue # 过期数据直接跳过 for v, w in graph[u]: nd d w if nd dist[v]: dist[v] nd heapq.heappush(heap, (nd, v)) return distif d dist[u]: continue这一行是懒删除的关键。Python 的heapq不支持修改堆中元素的优先级所以每次更新距离就重新 push 一份堆里会有历史数据。不做这个判断算法仍然正确但会多做很多无用功。5.2 字符串匹配什么时候该手写 KMPPython 的str.find和in操作底层是高效的字符串匹配实现日常开发直接用它就行。手写 KMP 的意义在于理解“失配时利用已有信息”这个思想以及处理一些内置函数覆盖不到的需求比如“求所有匹配位置”、“求最小循环节”、“求字符串的 border 结构”。KMP 的核心是next数组也叫失配数组它记录的是“到当前位置为止前缀和后缀相等的最大长度”。构造next的过程本身就是一次自我匹配这一步是整段代码里最难理解的部分。def build_next(p): nxt [0] * len(p) k 0 for i in range(1, len(p)): while k 0 and p[i] ! p[k]: k nxt[k - 1] if p[i] p[k]: k 1 nxt[i] k return nxt def kmp_search(s, p): if not p: return 0 nxt build_next(p) k 0 for i, ch in enumerate(s): while k 0 and ch ! p[k]: k nxt[k - 1] if ch p[k]: k 1 if k len(p): return i - len(p) 1 return -1k nxt[k - 1]这个回退动作是 KMP 的灵魂。它的含义是“当前这个前缀已经对不上了退而求其次看看更短的前缀还能不能对上”。理解了这句话next数组的构造就不需要死记了。6. 常见问题与排查技巧实录6.1 复杂度误判与性能陷阱最常见的误判是把“嵌套循环”直接等同于 O(n²)。实际上要看内层循环的执行次数总和比如双指针、单调栈这些写法外层是循环、内层是 while但内层指针不会回退总执行次数是 O(n)。判断方法是看“指针是否有单调性”单调就是均摊分析不单调就得老实算。第二个高频陷阱是隐性复杂度。list.pop(0)是 O(n)在循环里做就成了 O(n²)x in list是 O(n)换成set就是 O(1)字符串拼接s ch在循环里是 O(n²)换成.join(parts)是 O(n)。这些问题不会报错只会让程序在数据量上来之后突然变慢排查起来非常费劲。第三个是递归深度。Python 默认递归深度限制是 1000 左右DFS 遍历深度较大的树或图时很容易触发RecursionError。解决方案要么改成显式栈的迭代写法要么用sys.setrecursionlimit调大限制但后者要配合更大的栈空间才有意义否则可能直接段错误。现象可能原因排查手段数据量小时正常大了就超时隐性 O(n²)定位内层操作看是否有in list、pop(0)、字符串拼接结果偶尔不对复现困难相等元素的处理顺序用固定随机种子跑多组数据重点查比较条件里的和程序直接退出无报错递归过深或内存溢出加sys.setrecursionlimit或改成迭代哈希结构查不到数据自定义类未正确实现__hash__打印hash(obj)和obj obj2的结果图算法结果偏大边权出现负数打印最小边权负权换 Bellman-Ford6.2 我的几个实操心得第一个心得每写完一个算法用三组数据验证——空输入、单元素、含重复元素。这三组能挡住 80% 的边界错误。空输入考验的是提前返回单元素考验的是循环条件重复元素考验的是比较符号。第二个心得不要在没有性能需求的时候做“提前优化”。我见过有人把所有查找都改成手写二分结果代码可读性大幅下降而实际数据量只有几百条in操作完全够用。算法的选择要看数据规模n 小于 1000 的时候常数因子比复杂度更重要。第三个心得复杂度分析最好写成注释。写# O(n log n)排序 单次遍历这种比只写# 排序有用得多。过几个月回头看你能立刻想起当时的取舍理由。第四个心得动态规划的调试不要靠打印整个 dp 表先手动推演前三个状态确认初始值对了再看转移方程。绝大多数 DP 的 bug 都在初始值而不是转移方程。第五个心得图论题目先把图画出来标上节点和边权再动笔写代码。直接在脑子里推演图的遍历顺序出错概率非常高而且错了很难定位。7. 一个补充算法清单的练习节奏最后分享一点关于练习节奏的体会。我自己的习惯是每个模块只精做五到八道题做完之后隔一周再重写一遍不看之前代码。第二遍能独立写出来的才算真的会了写不出来的说明当时是靠记忆而不是靠理解。排序和二分属于“必须肌肉记忆”的部分快排模板、二分模板、并查集模板这几个要能做到提笔就写。动态规划和图论属于“必须理解思路”的部分代码可以查但状态定义和算法选择必须自己想清楚。字符串算法属于“知道有这个东西就行”的部分真要用的时候再翻文档没必要全部背下来。这套清单我前后改过三四版删掉了很多“考试会考但实际用不上”的内容比如 AVL 树的完整旋转实现、红黑树的插入删除这些了解概念即可。留下来的都是会在实际代码里反复出现的或者是在技术讨论中必须能讲清楚的。要是你正在按某个“大全”清单从头刷不妨先停下来看看自己真正需要的是哪一部分把有限的时间投在出错代价最高的地方。 Python经典算法清单：按使用频率与出错代价精讲核心算法
1. 我重新梳理这套Python算法清单的缘由每隔一段时间总会有人在群里问一句python经典算法大全到底该从哪儿看起python算法有哪些是真正需要花时间掌握的。这个问题我回答过不下十遍但每次回答都不太一样因为提问的人背景差别太大。有的是刚学完语法想做点练习的有的是工作两年突然要准备技术考察的还有的是写业务代码写久了想回头把基础重新打一遍。所以这次索性把我会反复翻看的那部分算法整理成一份清单把每个模块为什么这么选、代码怎么写、哪些地方最容易出错都写清楚。这份内容适合谁如果你是刚接触 Python、能写函数但一遇到复杂度分析就发懵的新人可以从第 2、3 节顺着读如果你已经有项目经验只想找回手感、顺手补一下动态规划和图论直接跳到第 4、5 节也没问题。我不会把几十种算法全部罗列一遍那种清单在搜索结果的首页能找到一大堆但大多只有名字和一句解释看完还是不知道该怎么用。我关注的是那些在真实场景里被反复调用、被反复写错、被反复讨论的算法以及围绕它们的一整套工程习惯。先交代一个前提算法清单不应该按“考试大纲”来组织而应该按“使用频率 出错代价”来组织。一个排序写错可能只是结果顺序不对一个二分边界写错可能就是线上数据查不到一个并查集漏了路径压缩可能就让程序从毫秒级变成分钟级。这个思路决定了下面所有内容的排列顺序和取舍方式。2. 排序与查找最基础也是最容易出问题的地方2.1 快速排序、归并与堆排序之间的选择排序是所有人学算法的第一站但真正到了写代码的时候绝大多数情况直接调用sorted()就够了。Python 内置的 Timsort 是归并和插入排序的混合实现平均和最坏都是 O(n log n)而且对部分有序的数据有额外优化手写基本不可能比它快。所以我一般只在两种情况下手写排序一是需要理解分治思想二是需要做“部分排序”或者“只取前 K 个”这类内置函数不方便处理的场景。快速排序值得手写的核心原因不是它快而是它把“分治 原地交换”这套模式展示得最干净。我常用的版本做了两件事三数取中选基准以及小区间切换插入排序。前者用来规避已经有序的输入导致的 O(n²) 退化后者是因为递归到 16 个元素以下时递归开销已经超过比较开销了。def quick_sort(arr, lo0, hiNone): if hi is None: hi len(arr) - 1 while lo hi: if hi - lo 16: insertion_sort(arr, lo, hi) return mid lo (hi - lo) // 2 # 三数取中把中位数换到 lo 位置 if arr[mid] arr[lo]: arr[lo], arr[mid] arr[mid], arr[lo] if arr[hi] arr[lo]: arr[lo], arr[hi] arr[hi], arr[lo] if arr[hi] arr[mid]: arr[mid], arr[hi] arr[hi], arr[mid] arr[lo], arr[mid] arr[mid], arr[lo] pivot arr[lo] i, j lo, hi while i j: while i j and arr[j] pivot: j - 1 arr[i] arr[j] while i j and arr[i] pivot: i 1 arr[j] arr[i] arr[i] pivot # 先递归较短的一侧控制栈深度 if i - lo hi - i: quick_sort(arr, lo, i - 1) lo i 1 else: quick_sort(arr, i 1, hi) hi i - 1 return arr这段代码有两个细节值得单独拿出来说。第一个是i, j双指针加“挖坑填数”的写法比左右交换的写法少一半赋值操作实测在几十万级别的列表上差距能到 15% 左右。第二个是“先递归较短的一侧”这个尾递归优化它把最坏情况下的递归栈深度从 O(n) 压到 O(log n)避免数据量一大就触发递归深度限制。归并排序的适用场景和快排不太一样。快排是原地排序空间 O(log n)归并需要额外 O(n) 空间但它是稳定排序而且天然适合处理外部排序和链表排序。我处理链表排序时基本只用归并因为链表没法随机访问快排的 partition 在链表上非常别扭。堆排序的优势在于最坏情况也是 O(n log n) 且空间 O(1)但它不稳定、缓存不友好实际项目里我用它的次数屈指可数更多是拿堆这个结构去做优先队列而不是拿堆排序去排数组。下面这张表是我自己整理的选择依据遇到具体问题时可以直接对照场景推荐方案理由通用列表排序内置sorted()Timsort 稳定且有局部有序优化教学 / 理解分治快排原地、思路清晰、参数少链表排序归并不需要随机访问稳定只取前 K 个heapq.nlargest/ 小顶堆复杂度 O(n log k)不必全排数据量大且内存吃紧堆排序原地最坏 O(n log n)注意手写快排时不要用arr[0]当基准也不要对已经有序的数据做测试就下结论。真实数据里“部分有序”非常常见比如按时间戳追加的日志这时候固定基准会直接退化。2.2 二分查找边界写错一次就够记一辈子二分查找的代码只有十来行但它是公认最容易写错的算法之一。根因不在算法本身而在于“区间定义”这件事没有被统一。我现在的习惯是全程只用左闭右开区间[lo, hi)所有变体都在这套约定下推不再混用闭区间写法。def lower_bound(arr, target): 返回第一个 target 的下标找不到返回 len(arr) lo, hi 0, len(arr) while lo hi: mid lo (hi - lo) // 2 if arr[mid] target: lo mid 1 else: hi mid return lo这个模板能覆盖绝大部分需求要判断存在性就看lo len(arr) and arr[lo] target要找最后一个小于等于 target 的位置就换成upper_bound再减一要在旋转数组里查找只改判断条件不改框架。统一模板的价值在于你不需要每次重新推导边界只要记住“循环结束时 lo 是答案”这一条。mid lo (hi - lo) // 2这种写法不是为了好看。在支持 int 溢出的语言里它能防止溢出在 Python 里虽然没有溢出问题但保持这个习惯可以让你在跨语言写代码时不用重新想一遍。有一个坑我踩过对浮点数做二分时用while lo hi会陷入死循环因为两个浮点数之间永远存在更近的值。这种情况要么改成固定迭代次数比如 100 次要么给区间加一个精度阈值while hi - lo 1e-7。我一般用固定次数因为精度阈值在不同量级的数据上不好统一。3. 数据结构类算法栈、队列、哈希与并查集3.1 该用内置结构还是自己手写这个问题的答案很明确业务代码里全部用内置结构。list当栈用collections.deque当队列用dict当哈希表用heapq当优先队列用。Python 的内置实现是 C 层优化过的手写一遍性能只会更差。但“用内置”不等于“不用懂”。栈和队列的价值在于它们约束了访问顺序这个约束本身就是算法设计的一部分。比如用栈做括号匹配、用单调栈求下一个更大元素、用 deque 做滑动窗口最大值这些都是把数据结构当成“状态容器”来用而不是简单地存数据。单调栈这个模式特别值得单独练它的核心是“维护一个单调递增或递减的栈入栈前弹掉破坏单调性的元素”一旦理解了这个动作接雨水、柱状图最大矩形、滑动窗口最大值这一串题目就是同一套逻辑换个外套。哈希表这块我要提醒的是“哈希冲突”和“可哈希性”两个概念。Python 的dict用开放寻址法处理冲突平均 O(1)但如果你自定义了__eq__却没定义__hash__这个类就变成不可哈希的塞不进set和dict。反过来如果两个对象相等但哈希值不同字典查找就会失效。这是一个很隐蔽的 bug表现出来是“明明放进去了却查不到”。3.2 并查集路径压缩不能省并查集是那种“代码极短、作用极大、细节极易漏”的结构典型用于连通性判断、朋友圈合并、岛屿数量统计这类问题。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n self.count n # 连通分量个数 def find(self, x): # 迭代版路径压缩避免递归深度问题 root x while self.parent[root] ! root: root self.parent[root] while self.parent[x] ! root: self.parent[x], x root, self.parent[x] return root def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return False # 按秩合并把矮树挂到高树下面 if self.rank[rx] self.rank[ry]: rx, ry ry, rx self.parent[ry] rx if self.rank[rx] self.rank[ry]: self.rank[rx] 1 self.count - 1 return True三个细节第一find用迭代不用递归因为路径压缩后的树虽然矮但极端情况下仍可能很深递归有栈溢出风险第二路径压缩和按秩合并一起用复杂度才接近常数只用其中一个会退化成 O(log n)第三用count维护连通分量个数比每次遍历统计快得多这是图上判环的关键。我见过一个真实案例某项目用并查集做大批量数据的分组只做了路径压缩没做按秩合并单次操作平均下来还是很快但在“先大量 union 再集中 find”的模式下性能比两者都用慢了将近 3 倍。这不是理论问题是实测出来的。4. 动态规划与贪心思路永远比代码重要4.1 动态规划的四步定式动态规划是很多人卡住的地方卡点通常不是写不出代码而是不知道状态该怎么定义。我现在的做法是固定走四步定义状态、写转移方程、确定初始值和边界、确定遍历顺序。这四步里第一步和第四步最容易错代码反而是最简单的。以 0-1 背包为例。状态定义成dp[i][j]表示“前 i 个物品、容量 j 时的最大价值”转移方程是“不选第 i 个”和“选第 i 个”取较大值。到这里还没完关键在遍历顺序01 背包用一维数组优化时容量必须从大到小遍历因为每个物品只能用一次完全背包则从小到大因为物品可以重复用。这个顺序差异不是记忆题而是由“当前状态依赖的是本层还是上一层”决定的。def knapsack_01(weights, values, cap): dp [0] * (cap 1) for i in range(len(weights)): # 倒序遍历保证每件物品只被选一次 for j in range(cap, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[cap]另一个高频模式是最长递增子序列。O(n²) 的写法是dp[i]表示以 i 结尾的最长长度状态转移要遍历前面所有元素O(n log n) 的写法维护一个“最小结尾数组”用二分插入。后者不好想但它其实是“贪心 二分”的组合理解了“让每个长度的结尾尽可能小”这个贪心策略代码就只是辅助。我在实际使用中发现动态规划真正难的地方在于“能不能把问题拆成重叠子问题”。有些题看起来像 DP其实是贪心有些看起来像贪心其实必须 DP。判断标准是局部最优能不能推出全局最优。能就是贪心不能才需要 DP 枚举所有状态。4.2 贪心的适用边界与验证方法贪心的坑在于“看起来对”但实际不成立。我验证一个贪心策略是否正确的土办法是构造三个反例。第一个是“相邻两项交换后结果变差”的边界第二个是“局部最优但全局不是最优”的构造第三个是“相等值导致的并列选择”。三个都能顶住才敢用。典型的贪心场景包括区间调度按结束时间排序、分发饼干双指针匹配、跳跃游戏维护最远可达位置。这些问题的共性是存在一个明确的“排序依据”排完序之后每一步的最优选择都是确定的。如果没有明确的排序依据或者排序依据需要反复调整那多半不是贪心。提示写完贪心不要急着提交先用小规模数据暴力枚举所有方案和贪心结果对比。这一步花不了五分钟但能省掉一次返工。5. 图论与字符串工程里真正会碰到的部分5.1 图遍历与最短路的选择图的表示我一般只用两种邻接表用dict[list]存适合稀疏图邻接矩阵用二维列表存适合稠密图或者需要 O(1) 判断两点是否相邻的场景。绝大多数业务问题是稀疏图所以邻接表用得最多。BFS 和 DFS 的选择取决于你要什么。求最短步数用 BFS因为它是按层扩展的第一次访问到目标时路径一定最短求所有路径、做连通性判断、做拓扑排序用 DFS因为它的递归结构天然适合回溯。这里有个细节BFS 的 visited 标记必须在入队时就打上不能等出队才打否则同一个节点可能被重复入队队列会急剧膨胀。这个错误在网格类问题上特别常见。Dijkstra 是带权最短路的默认选择用heapq实现优先队列复杂度 O((VE) log V)。它的前提是边权非负一旦出现负权就必须换 Bellman-Ford 或 SPFA。这一点在实际项目里要特别注意因为“负数权重”往往不会写在需求里而是从数据里冒出来的。import heapq def dijkstra(graph, start): dist {node: float(inf) for node in graph} dist[start] 0 heap [(0, start)] while heap: d, u heapq.heappop(heap) if d dist[u]: continue # 过期数据直接跳过 for v, w in graph[u]: nd d w if nd dist[v]: dist[v] nd heapq.heappush(heap, (nd, v)) return distif d dist[u]: continue这一行是懒删除的关键。Python 的heapq不支持修改堆中元素的优先级所以每次更新距离就重新 push 一份堆里会有历史数据。不做这个判断算法仍然正确但会多做很多无用功。5.2 字符串匹配什么时候该手写 KMPPython 的str.find和in操作底层是高效的字符串匹配实现日常开发直接用它就行。手写 KMP 的意义在于理解“失配时利用已有信息”这个思想以及处理一些内置函数覆盖不到的需求比如“求所有匹配位置”、“求最小循环节”、“求字符串的 border 结构”。KMP 的核心是next数组也叫失配数组它记录的是“到当前位置为止前缀和后缀相等的最大长度”。构造next的过程本身就是一次自我匹配这一步是整段代码里最难理解的部分。def build_next(p): nxt [0] * len(p) k 0 for i in range(1, len(p)): while k 0 and p[i] ! p[k]: k nxt[k - 1] if p[i] p[k]: k 1 nxt[i] k return nxt def kmp_search(s, p): if not p: return 0 nxt build_next(p) k 0 for i, ch in enumerate(s): while k 0 and ch ! p[k]: k nxt[k - 1] if ch p[k]: k 1 if k len(p): return i - len(p) 1 return -1k nxt[k - 1]这个回退动作是 KMP 的灵魂。它的含义是“当前这个前缀已经对不上了退而求其次看看更短的前缀还能不能对上”。理解了这句话next数组的构造就不需要死记了。6. 常见问题与排查技巧实录6.1 复杂度误判与性能陷阱最常见的误判是把“嵌套循环”直接等同于 O(n²)。实际上要看内层循环的执行次数总和比如双指针、单调栈这些写法外层是循环、内层是 while但内层指针不会回退总执行次数是 O(n)。判断方法是看“指针是否有单调性”单调就是均摊分析不单调就得老实算。第二个高频陷阱是隐性复杂度。list.pop(0)是 O(n)在循环里做就成了 O(n²)x in list是 O(n)换成set就是 O(1)字符串拼接s ch在循环里是 O(n²)换成.join(parts)是 O(n)。这些问题不会报错只会让程序在数据量上来之后突然变慢排查起来非常费劲。第三个是递归深度。Python 默认递归深度限制是 1000 左右DFS 遍历深度较大的树或图时很容易触发RecursionError。解决方案要么改成显式栈的迭代写法要么用sys.setrecursionlimit调大限制但后者要配合更大的栈空间才有意义否则可能直接段错误。现象可能原因排查手段数据量小时正常大了就超时隐性 O(n²)定位内层操作看是否有in list、pop(0)、字符串拼接结果偶尔不对复现困难相等元素的处理顺序用固定随机种子跑多组数据重点查比较条件里的和程序直接退出无报错递归过深或内存溢出加sys.setrecursionlimit或改成迭代哈希结构查不到数据自定义类未正确实现__hash__打印hash(obj)和obj obj2的结果图算法结果偏大边权出现负数打印最小边权负权换 Bellman-Ford6.2 我的几个实操心得第一个心得每写完一个算法用三组数据验证——空输入、单元素、含重复元素。这三组能挡住 80% 的边界错误。空输入考验的是提前返回单元素考验的是循环条件重复元素考验的是比较符号。第二个心得不要在没有性能需求的时候做“提前优化”。我见过有人把所有查找都改成手写二分结果代码可读性大幅下降而实际数据量只有几百条in操作完全够用。算法的选择要看数据规模n 小于 1000 的时候常数因子比复杂度更重要。第三个心得复杂度分析最好写成注释。写# O(n log n)排序 单次遍历这种比只写# 排序有用得多。过几个月回头看你能立刻想起当时的取舍理由。第四个心得动态规划的调试不要靠打印整个 dp 表先手动推演前三个状态确认初始值对了再看转移方程。绝大多数 DP 的 bug 都在初始值而不是转移方程。第五个心得图论题目先把图画出来标上节点和边权再动笔写代码。直接在脑子里推演图的遍历顺序出错概率非常高而且错了很难定位。7. 一个补充算法清单的练习节奏最后分享一点关于练习节奏的体会。我自己的习惯是每个模块只精做五到八道题做完之后隔一周再重写一遍不看之前代码。第二遍能独立写出来的才算真的会了写不出来的说明当时是靠记忆而不是靠理解。排序和二分属于“必须肌肉记忆”的部分快排模板、二分模板、并查集模板这几个要能做到提笔就写。动态规划和图论属于“必须理解思路”的部分代码可以查但状态定义和算法选择必须自己想清楚。字符串算法属于“知道有这个东西就行”的部分真要用的时候再翻文档没必要全部背下来。这套清单我前后改过三四版删掉了很多“考试会考但实际用不上”的内容比如 AVL 树的完整旋转实现、红黑树的插入删除这些了解概念即可。留下来的都是会在实际代码里反复出现的或者是在技术讨论中必须能讲清楚的。要是你正在按某个“大全”清单从头刷不妨先停下来看看自己真正需要的是哪一部分把有限的时间投在出错代价最高的地方。