★ FEATURED ARTICLE 1. 从一份“Python经典算法大全”清单说起谁在搜搜到了什么每次有人在群里甩出一句“有没有Python经典算法大全”我基本能猜到对方处在什么阶段要么是刚学完语法、准备刷题找工作要么是工作几年突然发现业务代码写得再溜一碰到性能瓶颈和复杂逻辑还是得回头补算法功底。这两类人搜到的结果往往一样——一张长长的名词表排序、查找、递归、分治、动态规划、贪心、回溯、图论、字符串匹配后面跟着一堆代码片段但没人告诉你哪些该手写、哪些该直接调库、哪些在真实项目里其实根本用不上。这份清单真正能帮到你的地方不是把算法名字背下来而是搞清楚每个算法解决的是什么形状的问题、在Python里它的代价是多少、什么场景下用它才不会给自己挖坑。这篇文章就是干这个的我会按照自己平时带人和做项目的顺序把Python算法的全貌拆成若干块配上能直接粘进文件里跑的实现、复杂度取舍和踩坑记录适合刚入门想建立体系的人也适合有基础但想理清边界的人对着查漏补缺。1.1 算法清单到底该按什么维度分类市面上流传的算法清单大多按“名字”罗列这种排法对学习没什么帮助因为你看不出它们之间的替代关系。我更习惯按“问题的形状”来分同一类问题下的算法才有比较意义。比如“在一堆数据里找东西”这一类二分查找、哈希查找、二叉搜索树查找才是可互相替换的选项“把一堆数据排好序”这一类插入、归并、快排、堆排才是同台竞技的选手。按形状分类还有个好处就是你能快速判断该不该动用某个算法——如果问题的输入规模只有几十个元素你上什么算法都差不多纠结复杂度纯属浪费。下面这张表是我自己用来给新人做入门定位的把常见算法按类别、典型问题形状、工程里的实际出现频率列在一起频率这一列按我个人的经验给的主观判断仅供参考。类别代表算法解决的问题形状面试频率工程频率排序插入、归并、快排、堆排让数据有序高中多直接调sorted查找二分、哈希在有序或可索引集合里定位高高递归与分治归并、快排、树的遍历大问题拆成同构子问题高高回溯全排列、N皇后、子集在解空间里枚举可行解高低动态规划背包、编辑距离、最长递增子序列有重叠子问题的最优化高中贪心区间调度、跳跃游戏每步取局部最优即全局最优中中图论BFS、DFS、Dijkstra、拓扑排序关系网络上的遍历与最短路中高字符串KMP、Rabin-Karp、编辑距离模式匹配与相似度中高数据结构配套堆、并查集、前缀和支撑上述算法的容器高高看这张表你会发现一个有意思的现象面试频率和工程频率并不完全重合。回溯在面试里出现得很多因为它的代码结构漂亮、能考察思维但真实业务里除了配置生成、路径枚举这类场景平时很少需要手写。反过来图论里的BFS和拓扑排序在工程里到处都是——依赖解析、任务调度、层级展开但面试里问得相对少。搞清楚这个错位你就不会把时间平均分配而是按自己的目标加权投入。1.2 Python写算法的三个现实约束用Python写算法和用C写最大的区别不在语法而在你脚下的运行时环境。第一约束是递归深度。Python默认的递归上限是1000层左右超过就抛RecursionError。这意味着你写深度优先搜索、写归并排序的递归版本在数据规模上千的时候随时可能炸。sys.setrecursionlimit()能调高但调太高有把C栈撑爆导致解释器直接崩溃的风险我一般调到10000以内就收手真正深的遍历老老实实改成显式栈的迭代写法。第二约束是内置函数是C实现的。sorted()、list.sort()用的是Timsortmin()、max()、sum()、any()、all()都是C层循环。在绝大多数场景下你手写的纯Python排序跑不过sorted()手写的求和跑不过sum()。所以我的原则很明确理解算法时手写交付代码时调库。手写是为了知道边界在哪、什么时候库函数不适用调库是因为你的业务代码没理由去和C比速度。第三约束是整数没有溢出但浮点有精度问题。Python的int是任意精度的所以你在写累加、写大数运算时不用担心溢出这是相对C的便利。但一旦引入浮点二分查找里用(lo hi) / 2就可能出现精度误差导致死循环必须用//整除。另外求平方根、比较浮点相等这些操作都要留个心眼用误差范围判断。这三个约束贯穿后面所有代码先摆在这里。2. 排序与查找手写是为了理解调用是为了交付排序是所有人学算法的第一站也是最容易产生“学完就忘”错觉的地方。原因很简单实际工作中你几乎不会手写排序sorted()一行就解决了。但我还是建议你至少能手写插入排序、归并排序和快速排序这三个因为它们的思路会反复出现在别的算法里——归并的分治思想是后面很多题的基础快排的partition技巧能直接迁移到“找第k大元素”这类问题上。至于冒泡和选择排序知道原理就行没必要花时间默写它们在真实场景里没有任何性能优势。2.1 五种排序的Python实现与适用边界先把代码摆出来每一个我都尽量写得短、写得没有花活方便你直接跑。插入排序的核心是维护一个已排序的前缀每次把新元素插到正确位置。它在小数组上表现很好因为常数因子小、没有递归开销Python标准库的Timsort在数组长度小于64时会退化成插入排序就是这个道理。def insertion_sort(a): for i in range(1, len(a)): key a[i] j i - 1 while j 0 and a[j] key: a[j 1] a[j] j - 1 a[j 1] key return a归并排序是分治的标准模板拆两半、各自排好、合并。它的价值在于稳定且最坏情况也是O(n log n)代价是需要额外的O(n)空间。Python里写归并要注意切片的开销a[:mid]每次都会复制数据量大时这份复制成本不能忽略。如果在意性能可以传索引区间而不是切片。def merge_sort(a): if len(a) 1: return a mid len(a) // 2 left merge_sort(a[:mid]) right merge_sort(a[mid:]) res, i, j [], 0, 0 while i len(left) and j len(right): if left[i] right[j]: # 保证稳定性 res.append(left[i]); i 1 else: res.append(right[j]); j 1 res.extend(left[i:]) res.extend(right[j:]) return res快速排序的关键在主元选择。教科书上取第一个元素做基准遇到已经有序的输入会退化成O(n²)这是新手最常踩的坑。我的做法是三数取中比较首、中、尾三个位置取中间值当主元能大幅降低踩到最坏情况的概率。def quick_sort(a, lo0, hiNone): if hi is None: hi len(a) - 1 if lo hi: return a mid (lo hi) // 2 # 三数取中把中位数换到 lo 位置 if a[lo] a[mid]: a[lo], a[mid] a[mid], a[lo] if a[lo] a[hi]: a[lo], a[hi] a[hi], a[lo] if a[mid] a[hi]: a[mid], a[hi] a[hi], a[mid] a[mid], a[hi] a[hi], a[mid] # 主元暂存到末尾 pivot a[hi] i lo for j in range(lo, hi): if a[j] pivot: a[i], a[j] a[j], a[i] i 1 a[i], a[hi] a[hi], a[i] quick_sort(a, lo, i - 1) quick_sort(a, i 1, hi) return a堆排序是唯一能在O(1)额外空间下保证O(n log n)的原地排序。它的实现分两步先自底向上建堆再反复把堆顶换到末尾并下沉。很多人卡在range(n//2 - 1, -1, -1)这个起点上其实原因很简单——叶子节点本身就是一个合法的堆不需要下沉从最后一个非叶子节点开始就够了。def sift_down(a, i, n): while True: l, r 2 * i 1, 2 * i 2 largest i if l n and a[l] a[largest]: largest l if r n and a[r] a[largest]: largest r if largest i: break a[i], a[largest] a[largest], a[i] i largest def heap_sort(a): n len(a) for i in range(n // 2 - 1, -1, -1): sift_down(a, i, n) for end in range(n - 1, 0, -1): a[0], a[end] a[end], a[0] sift_down(a, 0, end) return a把这几个放在一起对比适用边界就清楚了算法平均时间最坏时间额外空间稳定性我的使用建议插入排序O(n²)O(n²)O(1)稳定小数组、近乎有序时首选归并排序O(n log n)O(n log n)O(n)稳定需要稳定且数据大时用快速排序O(n log n)O(n²)O(log n)不稳定通用场景注意主元选择堆排序O(n log n)O(n log n)O(1)不稳定内存敏感、只要前k个时用内置 sortedO(n log n)O(n log n)O(n)稳定生产代码默认选它注意说“内置sorted最快”是有前提的。当你的比较逻辑复杂、key函数本身开销很大时不同实现之间的差距会被摊薄这时候选一个你能把控的写法比盲目追求快更重要。2.2 二分查找的四个变体与边界坑如果说排序是“学完就忘”那二分查找就是“一写就错”。我见过的错误版本比正确版本还多核心问题几乎都出在边界处理上。二分查找真正需要掌握的其实不是“找某个值”而是“找第一个满足条件的位置”这个通用模型——bisect模块里的bisect_left和bisect_right就是干这个的你手写的时候照着它们的语义写出错率能降一大截。先看最基础的两种找第一个大于等于x的位置和找第一个大于x的位置。注意区间统一用左闭右开[lo, hi)循环条件用lo hi这样不用纠结最后返回lo还是hi。def lower_bound(a, x): 第一个 x 的下标 lo, hi 0, len(a) # 左闭右开 while lo hi: mid (lo hi) // 2 if a[mid] x: lo mid 1 else: hi mid return lo def upper_bound(a, x): 第一个 x 的下标 lo, hi 0, len(a) while lo hi: mid (lo hi) // 2 if a[mid] x: lo mid 1 else: hi mid return lo这两个函数是很多题型的地基。比如“在有序数组里统计等于x的个数”答案就是upper_bound(a, x) - lower_bound(a, x)一次都不用遍历。再比如“找插入位置”直接就是lower_bound。生产代码里我基本不手写直接用bisect.bisect_left和bisect.bisect_right它们是C实现的速度比手写快一个数量级。第二个高频变体是旋转数组找最小值。这类题出现在面试里的频率极高思路是按中点与右端点比较来判断最小值落在哪半边。def find_min_rotated(nums): lo, hi 0, len(nums) - 1 while lo hi: mid (lo hi) // 2 if nums[mid] nums[hi]: lo mid 1 # 最小值在右半边 else: hi mid # 最小值在左半边含mid return nums[lo]第三个变体是二分答案也就是“答案具有单调性可以对答案本身二分”。这类题的特点是check函数写起来比二分本身难常见的有“分割数组的最大值最小化”“运送包裹的最少天数”。模板和普通二分一样只是判断条件换成了check(mid)。def binary_search_answer(lo, hi, check): check(x) 单调x 越大越容易满足返回最小可行 x while lo hi: mid (lo hi) // 2 if check(mid): hi mid else: lo mid 1 return lo第四个变体是浮点二分用在求方程近似解、求平方根这类场景。这里就要注意精度控制了循环条件不能写lo hi而要固定迭代次数或者写hi - lo 1e-9。def sqrt_binary(x, eps1e-9): lo, hi 0.0, max(1.0, x) while hi - lo eps: mid (lo hi) / 2 if mid * mid x: lo mid else: hi mid return (lo hi) / 2提示浮点二分固定迭代100次几乎能覆盖所有精度需求比写eps判断更稳因为eps设得太小会导致死循环。边界这块我踩过的坑总结起来就三条。第一mid的计算在Python里用(lo hi) // 2不会溢出所以不用像C那样写lo (hi - lo) / 2但如果你是从其他语言转过来的保持那个写法也无害。第二区间开闭一定要在写之前定死全程不要混用混用是绝大多数死循环的根源。第三while lo hi和while lo hi对应的是两套不同的不变式选一套用到底别看到别人怎么写就跟着改。3. 递归、分治与回溯把套路固化成模板递归是很多人学算法的分水岭。有人觉得它优雅有人觉得它绕脑子。我的经验是递归不用去“理解”而是要“套模板”把三个要素固定下来终止条件、当前层做什么、返回值怎么传。三要素想清楚了代码自然就出来了。分治是递归的一种特化回溯是递归加状态恢复三者其实是同一套东西的不同用法。3.1 递归三要素与记忆化改造拿最经典的斐波那契举例。朴素递归的写法是这样def fib(n): if n 2: return n return fib(n - 1) fib(n - 2)这段代码的问题是重复计算。fib(5)会算fib(3)两次fib(4)会算fib(2)三次调用次数呈指数增长。具体算一下调用次数约等于2的n次方量级n30时调用次数已经上百万n40时基本卡死。这就是为什么面试官看到这个写法会追问“怎么优化”。优化手段就是记忆化把算过的结果存起来下次直接查。Python里最省事的做法是用functools.lru_cache一行装饰器搞定。from functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 2: return n return fib(n - 1) fib(n - 2)改造后的复杂度从O(2ⁿ)降到O(n)因为每个状态只算一次。但lru_cache不是免费的它要为每个参数组合计算哈希、维护字典参数是列表或字典这类不可哈希对象时直接报错。所以我的使用建议是参数是整数、字符串、元组这类简单类型时放心用参数是复杂结构时老老实实自己开一个字典手动缓存或者干脆改写成递推。def fib_iter(n): if n 2: return n a, b 0, 1 for _ in range(n): a, b b, a b return a递推版本空间O(1)速度最快缺点是有些问题的状态转移不好想。这里有个很实用的经验任何记忆化搜索都能机械地改写成递推方法是先写出记忆化版本观察状态依赖的方向然后按依赖顺序填表。这个转换技巧在动态规划那一节还会细说。递归还有个绕不开的话题是递归深度。Python默认限制在1000层左右fib(1000)这种写法会直接抛异常。这时候要么改成递推要么用显式栈迭代别去盲目调setrecursionlimit因为栈溢出导致的崩溃是不可恢复的。3.2 回溯模板与剪枝时机回溯的本质是“在解空间树上做深度优先搜索走不通就退回来换条路”。它的代码结构高度固定我一般让新人先背熟这个骨架再往里填业务逻辑。def backtrack(path, state): if 到达叶子: result.append(path[:]) # 一定要复制 return for choice in 当前可选集合: if not 满足约束(choice, state): continue # 剪枝 path.append(choice) 更新 state backtrack(path, state) 恢复 state # 撤销选择 path.pop()这个骨架里有三个地方最容易出错。第一处是path[:]如果直接append(path)最后所有结果都会指向同一个列表对象输出全一样这是新手最经典的bug。第二处是状态恢复加了什么就要减回去顺序不能乱。第三处是剪枝条件的位置放在for循环开头和放在递归入口效果可能不同要按具体问题判断。拿全排列来说最朴素的写法是每次从全部元素里挑一个没被用过的def permute(nums): res [] used [False] * len(nums) def dfs(path): if len(path) len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) dfs(path) path.pop() used[i] False dfs([]) return res如果数组里有重复元素上面这个写法会产生重复结果。去重的标准做法是先排序然后在同一层里跳过重复元素def permute_unique(nums): nums.sort() res [] used [False] * len(nums) def dfs(path): if len(path) len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue if i 0 and nums[i] nums[i - 1] and not used[i - 1]: continue # 同层去重 used[i] True path.append(nums[i]) dfs(path) path.pop() used[i] False dfs([]) return resnot used[i - 1]这个条件很多人看不懂。它的意思是如果前一个相同元素在这一层还没被用过说明当前元素是这一层重复的起点之后的跳过它。反过来说如果used[i - 1]是True说明前一个相同元素在路径上当前元素是它的下一层这种情况要保留。这个判断逻辑建议直接记住推导一遍容易绕晕。再看N皇后这是剪枝的经典案例。用三个集合分别记录列、主对角线、副对角线是否被占用判断冲突就是O(1)的def solve_n_queens(n): res [] cols, diag1, diag2 set(), set(), set() def dfs(r, path): if r n: res.append(path[:]) return for c in range(n): if c in cols or (r - c) in diag1 or (r c) in diag2: continue cols.add(c); diag1.add(r - c); diag2.add(r c) path.append(c) dfs(r 1, path) path.pop() cols.remove(c); diag1.remove(r - c); diag2.remove(r c) dfs(0, []) return res主对角线用r - c标识、副对角线用r c标识这是棋盘类问题的通用技巧换到数独、八数码也一样能用。这里没有显式的剪枝语句但冲突判断本身就起到了剪枝作用——不符合条件的分支根本不会进入下一层。心得回溯题的调试成本很高因为分支太多。我的做法是先用最小的输入n3、数组长度2跑一遍打印每一步的path和state确认状态恢复正确之后再上大规模数据。直接拿大案例调试你会被输出淹没。4. 动态规划与贪心状态定义决定生死动态规划是算法里劝退率最高的部分但它的核心其实只有一句话把大问题拆成有重叠的子问题把子问题的答案存下来复用。难的不是这句话而是“状态怎么定义”。状态定义对了转移方程是水到渠成的事状态定义错了你怎么推都推不出来。我见过太多人卡在背包问题上不是不会写循环是一开始就没想清楚dp[i][j]到底代表什么。4.1 从记忆化搜索到递推的机械转换我的建议是先写记忆化搜索再改递推。记忆化搜索的思维负担最低你只需要写出暴力递归然后加个缓存正确性立刻就有了。等这个版本跑通了再观察状态依赖关系改成递推性能还能再提一截。这个流程走熟了之后你可以跳过第一步直接写递推但对新手来说跳过第一步就是在赌自己的状态定义没写错。拿0-1背包举例。问题是有n件物品每件有重量w[i]和价值v[i]背包容量W每件物品最多拿一次求最大价值。先写记忆化版本from functools import lru_cache def knapsack_memo(weights, values, W): n len(weights) lru_cache(maxsizeNone) def dfs(i, cap): if i n: return 0 # 不拿第 i 件 best dfs(i 1, cap) # 拿第 i 件 if cap weights[i]: best max(best, dfs(i 1, cap - weights[i]) values[i]) return best return dfs(0, W)状态是(i, cap)表示“从第i件开始考虑、剩余容量cap时的最大价值”。这个定义很直观转移就是“拿或不拿”两个分支取最大。时间复杂度O(nW)空间是缓存的大小。改成递推就需要把状态按依赖方向填表。观察一下dfs(i, cap)依赖dfs(i1, ...)也就是i大的先算。所以外层循环i从n-1倒着走内层循环cap从0到W。def knapsack_dp(weights, values, W): n len(weights) dp [[0] * (W 1) for _ in range(n 1)] for i in range(n - 1, -1, -1): for cap in range(W 1): dp[i][cap] dp[i 1][cap] if cap weights[i]: dp[i][cap] max(dp[i][cap], dp[i 1][cap - weights[i]] values[i]) return dp[0][W]到这一步已经能用了但还能压缩空间。注意到dp[i]只依赖dp[i1]所以二维数组可以压成一维。压缩的关键是内层循环要倒序因为正序会让同一件物品被重复使用那就变成完全背包了。def knapsack_1d(weights, values, W): dp [0] * (W 1) for i in range(len(weights)): for cap in range(W, weights[i] - 1, -1): # 倒序 dp[cap] max(dp[cap], dp[cap - weights[i]] values[i]) return dp[W]倒序这个点我强调一百遍都不嫌多。它的原理是倒序遍历时dp[cap - weights[i]]还没被本轮更新过读到的是上一轮的值符合“每件物品只用一次”的约束正序遍历时它已经被本轮更新过相当于这件物品可以无限次拿。完全背包就是把倒序改成正序一行之差语义完全不同。4.2 贪心的适用判定与反例贪心和动态规划经常被放在一起比较因为两者都是求最优化问题。区别在于贪心每步取局部最优不回头所以它要求问题具备贪心选择性质——局部最优能推出全局最优。这个性质不是所有问题都有判断方法一般有两个一是尝试构造反例二是用交换论证证明。区间调度是贪心的标准正例给一堆区间选出最多的互不重叠区间。策略是按右端点排序能选就选。def max_intervals(intervals): intervals.sort(keylambda x: x[1]) count, last_end 0, float(-inf) for s, e in intervals: if s last_end: count 1 last_end e return count为什么按右端点排而不是左端点因为右端点越小留给后面区间的空间越大。这个直觉可以严格证明但面试里说清楚这个逻辑就够了。反例的经典是零钱兑换。如果硬币面值是[1, 3, 4]凑6元贪心会先拿4再拿1和1共3枚但最优是332枚。贪心在这里失效必须用动态规划。def coin_change(coins, amount): INF float(inf) dp [0] [INF] * amount for i in range(1, amount 1): for c in coins: if c i: dp[i] min(dp[i], dp[i - c] 1) return -1 if dp[amount] INF else dp[amount]所以我的判断流程是先想贪心策略如果能找到反例就直接放弃老老实实上DP如果找不到反例再用交换论证试着证一下证不出来也要谨慎因为有些问题的反例藏得很深。工程里我更保守能用DP就用DP因为DP的正确性是结构保证的贪心一旦判错结果错了还不容易发现。5. 图与字符串工程里撞见频率最高的两类如果让我只保留两类算法带到工作中我会选图和字符串。原因是这两类问题在业务代码里出现得太频繁了依赖解析是拓扑排序推荐关系是多跳遍历权限继承是树上的DFS日志解析是字符串匹配输入纠错是编辑距离。它们不像回溯那样“面试专用”而是你写业务逻辑时真的会撞上。5.1 图遍历、最短路与拓扑排序图的表示我一般用邻接表Python里就是一个列表套列表或者字典套列表。BFS用队列DFS用栈或递归这两个是基础中的基础但工程里真正高频的是带权最短路和拓扑排序。单源最短路用Dijkstra核心是用优先队列每次取当前距离最小的节点。Python的heapq是小顶堆正好够用。import heapq def dijkstra(graph, src, n): INF float(inf) dist [INF] * n dist[src] 0 pq [(0, src)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue # 过期条目跳过 for v, w in graph[u]: nd d w if nd dist[v]: dist[v] nd heapq.heappush(pq, (nd, v)) return distif d dist[u]: continue这一行不能省。因为heapq不支持修改已有元素我们只能往堆里塞新条目同一个节点可能被塞进去多次。取出来的时候如果发现这个距离已经不是最新的直接丢掉。这就是所谓的“惰性删除”是Python里写Dijkstra的标准姿势。Dijkstra有个前提边权非负。如果图里有负权边就得用Bellman-Ford复杂度高一个量级。实际业务里负权边很少见但如果你在做的成本模型里有退款、抵扣这类“负收益”就要警惕。拓扑排序处理的是有向无环图的线性排序问题Kahn算法的思路是不断取出入度为0的节点from collections import deque def topo_sort(n, edges): g [[] for _ in range(n)] indeg [0] * n for u, v in edges: g[u].append(v) indeg[v] 1 q deque(i for i in range(n) if indeg[i] 0) order [] while q: u q.popleft() order.append(u) for v in g[u]: indeg[v] - 1 if indeg[v] 0: q.append(v) return order if len(order) n else [] # 空列表代表有环这个算法我用来做过任务依赖调度每个任务是一个节点依赖关系是一条边拓扑序就是合法的执行顺序。返回的列表长度小于n说明有环也就是依赖关系出现了循环这时候要报错而不是硬跑。注意Kahn算法给出的拓扑序不唯一只要满足所有边从前指向后就算合法。如果你的业务要求“同样合法的情况下优先执行某个任务”就要把队列换成优先队列每次取优先级最高的入度为零节点。5.2 字符串匹配与编辑距离字符串匹配最直接的做法是str.find()底层是高度优化的算法日常用足够了。但有些场景你需要自己控制匹配过程比如流式数据、需要返回所有匹配位置、需要处理通配符这时候就要手写。KMP是绕不开的一个它的核心是next数组表示“匹配失败时模式串应该退到哪个位置”。def build_next(p): nxt [0] * len(p) j 0 for i in range(1, len(p)): while j 0 and p[i] ! p[j]: j nxt[j - 1] if p[i] p[j]: j 1 nxt[i] j return nxt def kmp_search(s, p): if not p: return 0 nxt build_next(p) j 0 for i, ch in enumerate(s): while j 0 and ch ! p[j]: j nxt[j - 1] if ch p[j]: j 1 if j len(p): return i - len(p) 1 return -1next数组的含义是“p[0..i]这段里最长的相等前后缀长度”。这个定义一开始很难直观理解我的建议是拿一个具体例子手推一遍比如ababaca把每一步的nxt值写在纸上推完你就懂了。工程里如果只是判断子串存在永远优先用in和findKMP只在需要自定义匹配逻辑时才派上用场。编辑距离是字符串相似度的基础动态规划的经典题def edit_distance(s, t): m, n len(s), len(t) dp list(range(n 1)) # 一维滚动 for i in range(1, m 1): prev dp[0] dp[0] i for j in range(1, n 1): cur dp[j] cost 0 if s[i - 1] t[j - 1] else 1 dp[j] min(dp[j] 1, # 删除 dp[j - 1] 1, # 插入 prev cost) # 替换 prev cur return dp[n]这里的一维滚动比背包稍微绕一点因为每个位置依赖左上、左、上三个方向。用一个prev变量存住左上的旧值就行。这段代码我在做输入纠错、模糊匹配的时候用过很多次稳定性没问题但要注意它对中文是按字符算的如果你需要按词算得先分词再套这个函数。6. 常见问题与排查技巧实录前面几节讲的是“怎么写”这一节讲“写完为什么不работает”——开个玩笑讲写完为什么不工作。算法代码的bug有个特点小数据能过大数据就崩或者结果看着对边界一测就错。下面这些是我和身边人真实踩过的整理成速查表加经验条目你写代码卡住的时候可以对着翻。6.1 复杂度与性能问题速查表现象大概率原因排查手段解决方向小数据秒出大数据卡死算法复杂度过高打印输入规模算一下n log n和n²的差距换算法或加剪枝递归报RecursionError递归深度超过1000在递归入口打印深度改迭代或控制深度结果全是同一个列表回溯里没复制path检查res.append(path)改成path[:]循环不结束二分边界写错打印lo、hi、mid统一区间开闭动态规划结果偏大一维背包用了正序检查内层循环方向0-1背包改倒序图最短路结果不对堆里过期条目没跳过检查d dist[u]加上continue匹配结果错位KMP的next数组构建错打印nxt数组对照例子手推排序后结果不稳定用了快排或堆排看相等元素的相对顺序改用归并或sorted这张表里最值得展开的是第一条。很多人写算法只关心正确性不关心规模。我见过一个用三重循环做去重的实现在几百条数据上跑得好好的上线之后数据量涨到几万直接把接口拖垮。判断复杂度的办法很简单数一下嵌套循环的层数再乘以每层的数据量如果结果超过一千万次操作就要考虑优化了。Python每秒大概能执行几千万次简单操作超过这个量级就会明显卡顿。第二条也值得说。递归深度问题的隐蔽之处在于它可能只在特定输入下触发。比如你写树的遍历平时处理的树深度只有几层某天来了一棵畸形树深度两千直接崩。防御性做法是在递归函数入口加一个深度参数超过阈值就抛自定义异常或者切换成迭代而不是等它崩在线上。6.2 我踩过的六个坑与规避方法坑一可变默认参数。写递归辅助函数时很多人喜欢写成def dfs(node, path[], res[])觉得省事。Python的默认参数只在函数定义时求值一次所以多次调用会共享同一个列表结果就是上一次的残留数据混进下一次。正确做法是默认值写None函数体内判断后初始化。这个坑在回溯里尤其致命因为回溯本来就是多次调用。坑二用list.pop(0)当队列。BFS里需要从头部取元素pop(0)的时间复杂度是O(n)因为要移动后面所有元素。数据量上万时BFS会慢得莫名其妙。正确做法是用collections.deque的popleft()O(1)。这个替换我做过很多次改完之后性能提升肉眼可见。坑三在循环里做字符串拼接。s ch在Python里看起来是原地操作实际上每次都会创建新字符串循环n次就是O(n²)。数据量小的时候看不出来上万次拼接就会明显卡顿。正确做法是收集到列表里最后.join()。坑四浮点数当字典键。动态规划里如果用浮点数做状态键会遇到精度问题0.10.2不等于0.3导致明明该命中的缓存没命中。我的做法是把浮点状态转成整数比如乘以精度倍数后取整或者干脆改用递推避免哈希。坑五排序时key函数有副作用。sorted(a, keyf)里f会被调用多次如果你的f里做了什么修改状态的操作结果就不可控了。key函数必须是纯函数这一点在写复杂排序逻辑时一定要守住。坑六忘记处理空输入。二分查找里数组为空、图算法里节点数为零、字符串匹配里模式串为空这些边界如果不处理轻则返回错误结果重则抛IndexError。我的习惯是在每个函数开头写几行防御性判断看起来啰嗦但省下的调试时间远大于写这几行的时间。经验算法题的调试和业务代码不一样业务代码可以加日志慢慢看算法题一旦出错往往是逻辑层面的日志会刷屏。我的办法是构造最小可复现用例——能把bug触发出来的最短输入然后手动单步走一遍。90%的bug在最小用例上会暴露得非常明显。7. 我个人在实际操作中的体会算法这东西学一遍和用一遍是两回事。我最早也是照着清单一个个背背完就忘直到开始用它们解决具体问题才真正记住。所以我给的建议是别追求“大全”而是挑几个你真的会用的方向深下去如果你做后端图论和字符串值得多花时间因为依赖调度和文本处理天天见如果你做数据分析排序、二分、前缀和这些基础容器操作更实用如果你在准备面试回溯和动态规划必须练到能默写模板。至于那些一辈子用不上一次的算法知道它存在、知道它解决什么形状的问题就够了不必强求手写。另外Python这门语言的特点是“库比手写快”所以我的原则始终是理解阶段手写交付阶段调库。手写是为了在库函数不适用的时候有兜底方案调库是为了不为没必要的事情浪费时间。这两者不矛盾关键是你要清楚自己当下在做哪件事。
阅读完成 · 觉得有帮助？
