企业官网建设流程全解析

1. 从一份“Python经典算法大全”清单说起：谁在搜，搜到了什么

每次有人在群里甩出一句“有没有Python经典算法大全”，我基本能猜到对方处在什么阶段：要么是刚学完语法、准备刷题找工作，要么是工作几年突然发现业务代码写得再溜，一碰到性能瓶颈和复杂逻辑还是得回头补算法功底。这两类人搜到的结果往往一样——一张长长的名词表：排序、查找、递归、分治、动态规划、贪心、回溯、图论、字符串匹配，后面跟着一堆代码片段，但没人告诉你哪些该手写、哪些该直接调库、哪些在真实项目里其实根本用不上。这份清单真正能帮到你的地方，不是把算法名字背下来，而是搞清楚每个算法解决的是什么形状的问题、在Python里它的代价是多少、什么场景下用它才不会给自己挖坑。这篇文章就是干这个的，我会按照自己平时带人和做项目的顺序，把Python算法的全貌拆成若干块，配上能直接粘进文件里跑的实现、复杂度取舍和踩坑记录，适合刚入门想建立体系的人，也适合有基础但想理清边界的人对着查漏补缺。

1.1 算法清单到底该按什么维度分类

市面上流传的算法清单大多按“名字”罗列，这种排法对学习没什么帮助，因为你看不出它们之间的替代关系。我更习惯按“问题的形状”来分，同一类问题下的算法才有比较意义。比如“在一堆数据里找东西”这一类，二分查找、哈希查找、二叉搜索树查找才是可互相替换的选项；“把一堆数据排好序”这一类，插入、归并、快排、堆排才是同台竞技的选手。按形状分类还有个好处，就是你能快速判断该不该动用某个算法——如果问题的输入规模只有几十个元素，你上什么算法都差不多，纠结复杂度纯属浪费。

下面这张表是我自己用来给新人做入门定位的，把常见算法按类别、典型问题形状、工程里的实际出现频率列在一起，频率这一列按我个人的经验给的主观判断，仅供参考。

看这张表你会发现一个有意思的现象：面试频率和工程频率并不完全重合。回溯在面试里出现得很多，因为它的代码结构漂亮、能考察思维，但真实业务里除了配置生成、路径枚举这类场景，平时很少需要手写。反过来，图论里的BFS和拓扑排序在工程里到处都是——依赖解析、任务调度、层级展开，但面试里问得相对少。搞清楚这个错位，你就不会把时间平均分配，而是按自己的目标加权投入。

1.2 Python写算法的三个现实约束

用Python写算法和用C++写，最大的区别不在语法，而在你脚下的运行时环境。第一约束是递归深度。Python默认的递归上限是1000层左右，超过就抛RecursionError。这意味着你写深度优先搜索、写归并排序的递归版本，在数据规模上千的时候随时可能炸。sys.setrecursionlimit()能调高，但调太高有把C栈撑爆导致解释器直接崩溃的风险，我一般调到10000以内就收手，真正深的遍历老老实实改成显式栈的迭代写法。

第二约束是内置函数是C实现的。sorted()、list.sort()用的是Timsort，min()、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, lo=0, hi=None): 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

把这几个放在一起对比，适用边界就清楚了：

注意：说“内置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, eps=1e-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次方量级，n=30时调用次数已经上百万，n=40时基本卡死。这就是为什么面试官看到这个写法会追问“怎么优化”。

优化手段就是记忆化：把算过的结果存起来，下次直接查。Python里最省事的做法是用functools.lru_cache，一行装饰器搞定。

from functools import lru_cache @lru_cache(maxsize=None) 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 res

not 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标识，这是棋盘类问题的通用技巧，换到数独、八数码也一样能用。这里没有显式的剪枝语句，但冲突判断本身就起到了剪枝作用——不符合条件的分支根本不会进入下一层。

心得：回溯题的调试成本很高，因为分支太多。我的做法是先用最小的输入（n=3、数组长度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(maxsize=None) 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(i+1, ...)，也就是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[i+1]，所以二维数组可以压成一维。压缩的关键是内层循环要倒序，因为正序会让同一件物品被重复使用，那就变成完全背包了。

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(key=lambda 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枚；但最优是3+3，2枚。贪心在这里失效，必须用动态规划。

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 dist

if 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 -1

next数组的含义是“p[0..i]这段里，最长的相等前后缀长度”。这个定义一开始很难直观理解，我的建议是拿一个具体例子手推一遍，比如"ababaca"，把每一步的nxt值写在纸上，推完你就懂了。工程里如果只是判断子串存在，永远优先用in和find，KMP只在需要自定义匹配逻辑时才派上用场。

编辑距离是字符串相似度的基础，动态规划的经典题：

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 复杂度与性能问题速查表

这张表里最值得展开的是第一条。很多人写算法只关心正确性，不关心规模。我见过一个用三重循环做去重的实现，在几百条数据上跑得好好的，上线之后数据量涨到几万，直接把接口拖垮。判断复杂度的办法很简单：数一下嵌套循环的层数，再乘以每层的数据量，如果结果超过一千万次操作，就要考虑优化了。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.1+0.2不等于0.3，导致明明该命中的缓存没命中。我的做法是把浮点状态转成整数，比如乘以精度倍数后取整，或者干脆改用递推避免哈希。

坑五：排序时key函数有副作用。sorted(a, key=f)里，f会被调用多次，如果你的f里做了什么修改状态的操作，结果就不可控了。key函数必须是纯函数，这一点在写复杂排序逻辑时一定要守住。

坑六：忘记处理空输入。二分查找里数组为空、图算法里节点数为零、字符串匹配里模式串为空，这些边界如果不处理，轻则返回错误结果，重则抛IndexError。我的习惯是在每个函数开头写几行防御性判断，看起来啰嗦，但省下的调试时间远大于写这几行的时间。

经验：算法题的调试和业务代码不一样，业务代码可以加日志慢慢看，算法题一旦出错往往是逻辑层面的，日志会刷屏。我的办法是构造最小可复现用例——能把bug触发出来的最短输入，然后手动单步走一遍。90%的bug在最小用例上会暴露得非常明显。

7. 我个人在实际操作中的体会

算法这东西，学一遍和用一遍是两回事。我最早也是照着清单一个个背，背完就忘，直到开始用它们解决具体问题，才真正记住。所以我给的建议是别追求“大全”，而是挑几个你真的会用的方向深下去：如果你做后端，图论和字符串值得多花时间，因为依赖调度和文本处理天天见；如果你做数据分析，排序、二分、前缀和这些基础容器操作更实用；如果你在准备面试，回溯和动态规划必须练到能默写模板。至于那些一辈子用不上一次的算法，知道它存在、知道它解决什么形状的问题就够了，不必强求手写。

另外，Python这门语言的特点是“库比手写快”，所以我的原则始终是：理解阶段手写，交付阶段调库。手写是为了在库函数不适用的时候有兜底方案，调库是为了不为没必要的事情浪费时间。这两者不矛盾，关键是你要清楚自己当下在做哪件事。