1 · 功能说明与手机端直读指南
本文件汇总《算法设计与分析》八大高频核心算法的工业级精简 Python 模板：二分查找左边界、稳定归并排序、最长公共子序列（LCS 滚动数组）、0-1 背包（一维倒序滚动）、区间贪心活动安排、Dijkstra 最短路（最小堆）、n 皇后回溯搜索、Edmonds–Karp 最大流（BFS 增广路）。
为什么提供 HTML 代码阅读器？
在手机或平板浏览器中直接点击
.py 链接通常会触发文件下载而无法直接预览。本页面将 practice_algorithms.html 渲染为带行号、语法高亮与一键复制按钮的标准 V3 网页，方便随时对照课程笔记复习代码细节；同目录下的原始 practice_algorithms.html 仍完整保留供本地 Python 直接运行。
2 · 完整源码：practice_algorithms.html
1"""算法课 + 求职：可运行 Python 示例，均注明边界与复杂度。"""
2from bisect import bisect_right
3from collections import deque
4from heapq import heappush, heappop
5
6
7def lower_bound(nums, target):
8 """已排序 nums 的第一个 >= target 的下标。O(log n) 时间。"""
9 lo, hi = 0, len(nums)
10 while lo < hi:
11 mid = (lo + hi) // 2
12 if nums[mid] < target:
13 lo = mid + 1
14 else:
15 hi = mid
16 return lo
17
18
19def merge_sort(nums):
20 """稳定归并排序。O(n log n) 时间、O(n) 额外空间。"""
21 if len(nums) < 2:
22 return list(nums)
23 mid = len(nums) // 2
24 a, b = merge_sort(nums[:mid]), merge_sort(nums[mid:])
25 i = j = 0
26 out = []
27 while i < len(a) and j < len(b):
28 if a[i] <= b[j]:
29 out.append(a[i])
30 i += 1
31 else:
32 out.append(b[j])
33 j += 1
34 return out + a[i:] + b[j:]
35
36
37def count_inversions(nums):
38 """归并分治统计逆序对总数 (i < j 且 nums[i] > nums[j])。O(n log n) 时间。"""
39 def sort_count(arr):
40 if len(arr) < 2:
41 return list(arr), 0
42 mid = len(arr) // 2
43 left, c1 = sort_count(arr[:mid])
44 right, c2 = sort_count(arr[mid:])
45 merged, cross, i, j = [], 0, 0, 0
46 while i < len(left) and j < len(right):
47 if left[i] <= right[j]:
48 merged.append(left[i])
49 i += 1
50 else:
51 merged.append(right[j])
52 cross += len(left) - i
53 j += 1
54 merged.extend(left[i:])
55 merged.extend(right[j:])
56 return merged, c1 + c2 + cross
57
58 _, total = sort_count(nums)
59 return total
60
61
62def quick_select(nums, k):
63 """三路划分求 0-indexed 第 k 小元素。平均 O(n) 时间。"""
64 if not 0 <= k < len(nums):
65 raise ValueError('k 越界')
66 arr = list(nums)
67 while True:
68 pivot = arr[len(arr) // 2]
69 lt = [x for x in arr if x < pivot]
70 eq = [x for x in arr if x == pivot]
71 gt = [x for x in arr if x > pivot]
72 if k < len(lt):
73 arr = lt
74 elif k < len(lt) + len(eq):
75 return pivot
76 else:
77 k -= len(lt) + len(eq)
78 arr = gt
79
80
81def matrix_chain_order(p):
82 """矩阵连乘最小标量乘法次数，矩阵 A_i 维度为 p[i-1] x p[i]。O(n^3) 时间、O(n^2) 空间。"""
83 n = len(p) - 1
84 if n <= 1:
85 return 0
86 m = [[0] * (n + 1) for _ in range(n + 1)]
87 for length in range(2, n + 1): # 链长 l 从 2 到 n 对角线推进
88 for i in range(1, n - length + 2):
89 j = i + length - 1
90 m[i][j] = min(
91 m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
92 for k in range(i, j)
93 )
94 return m[1][n]
95
96
97def lcs_length(a, b):
98 """LCS 长度。O(len(a)*len(b)) 时间，O(len(b)) 空间。"""
99 prev = [0] * (len(b) + 1)
100 for ca in a:
101 dp = [0] * (len(b) + 1)
102 for j, cb in enumerate(b, 1):
103 dp[j] = prev[j - 1] + 1 if ca == cb else max(prev[j], dp[j - 1])
104 prev = dp
105 return prev[-1]
106
107
108def max_subarray(nums):
109 """最大非空连续子段和（Kadane 算法）。O(n) 时间、O(1) 空间。"""
110 if not nums:
111 raise ValueError('数组不能为空')
112 cur = best = nums[0]
113 for x in nums[1:]:
114 cur = max(x, cur + x)
115 best = max(best, cur)
116 return best
117
118
119def knapsack_01(weights, values, capacity):
120 """正整数重量的 0-1 背包。O(n*capacity) 伪多项式时间。"""
121 if (
122 len(weights) != len(values)
123 or not isinstance(capacity, int)
124 or capacity < 0
125 or any(not isinstance(w, int) or w <= 0 for w in weights)
126 ):
127 raise ValueError('输入非法：重量须正整数、容量须非负整数')
128 dp = [0] * (capacity + 1)
129 for w, v in zip(weights, values):
130 for c in range(capacity, w - 1, -1): # 倒序防止一个物品被重复选
131 dp[c] = max(dp[c], dp[c - w] + v)
132 return dp[capacity]
133
134
135def optimal_bst(p, q):
136 """最优二叉查找树期望代价，p[0..n-1] 为实结点概率，q[0..n] 为伪结点概率。O(n^3) 时间。"""
137 n = len(p)
138 e = [[0.0] * (n + 2) for _ in range(n + 2)]
139 w = [[0.0] * (n + 2) for _ in range(n + 2)]
140 for i in range(1, n + 2):
141 e[i][i - 1] = w[i][i - 1] = q[i - 1]
142 for length in range(1, n + 1):
143 for i in range(1, n - length + 2):
144 j = i + length - 1
145 w[i][j] = w[i][j - 1] + p[j - 1] + q[j]
146 e[i][j] = min(
147 e[i][r - 1] + e[r + 1][j] + w[i][j]
148 for r in range(i, j + 1)
149 )
150 return e[1][n]
151
152
153def activity_selection(intervals):
154 """最多不重叠区间 [start,end)。O(n log n) 时间。"""
155 if any(t < s for s, t in intervals):
156 raise ValueError('结束早于开始')
157 ans, last = [], float('-inf')
158 for s, t in sorted(intervals, key=lambda x: x[1]):
159 if s >= last:
160 ans.append((s, t))
161 last = t
162 return ans
163
164
165def weighted_interval_scheduling(intervals):
166 """带权活动安排 (start, end, weight) 最大总权重。O(n log n) 时间。"""
167 if not intervals:
168 return 0
169 jobs = sorted(intervals, key=lambda x: x[1])
170 ends = [j[1] for j in jobs]
171 dp = [0] * (len(jobs) + 1)
172 for i, (s, _, w) in enumerate(jobs, 1):
173 p = bisect_right(ends, s, 0, i - 1)
174 dp[i] = max(dp[i - 1], dp[p] + w)
175 return dp[-1]
176
177
178def dijkstra(graph, source):
179 """邻接表 (v,weight) 的非负最短路。堆 O((V+E)log V)。"""
180 n = len(graph)
181 if not 0 <= source < n:
182 raise ValueError('源点越界')
183 if any(v < 0 or v >= n or w < 0 for edges in graph for v, w in edges):
184 raise ValueError('端点越界或存在负权')
185 dist = [float('inf')] * n
186 dist[source] = 0
187 pq = [(0, source)]
188 while pq:
189 d, u = heappop(pq)
190 if d > dist[u]:
191 continue
192 for v, w in graph[u]:
193 new = d + w
194 if new < dist[v]:
195 dist[v] = new
196 heappush(pq, (new, v))
197 return dist
198
199
200def n_queens(n):
201 """每种方案为逐行皇后列号，最坏指数搜索。"""
202 if n < 0:
203 raise ValueError('n 不得为负')
204 ans, path = [], []
205 cols, d1, d2 = set(), set(), set()
206
207 def search(row):
208 if row == n:
209 ans.append(path[:])
210 return
211 for col in range(n):
212 a, b = row - col, row + col
213 if col in cols or a in d1 or b in d2:
214 continue
215 cols.add(col)
216 d1.add(a)
217 d2.add(b)
218 path.append(col)
219 search(row + 1)
220 path.pop()
221 d2.remove(b)
222 d1.remove(a)
223 cols.remove(col)
224
225 search(0)
226 return ans
227
228
229def knapsack_branch_and_bound(weights, values, capacity):
230 """优先队列式分支限界求解 0-1 背包最优值（按单位价值线性松弛上界剪枝）。"""
231 items = sorted(zip(weights, values), key=lambda x: x[1] / x[0], reverse=True)
232 n = len(items)
233
234 def bound(idx, cur_w, cur_v):
235 rem = capacity - cur_w
236 b = float(cur_v)
237 while idx < n and items[idx][0] <= rem:
238 rem -= items[idx][0]
239 b += items[idx][1]
240 idx += 1
241 if idx < n and rem > 0:
242 b += rem * (items[idx][1] / items[idx][0])
243 return b
244
245 best = 0
246 pq = [(-bound(0, 0, 0), 0, 0, 0)] # (-ub, idx, cur_w, cur_v)
247 while pq:
248 neg_ub, idx, cur_w, cur_v = heappop(pq)
249 if -neg_ub <= best or idx == n:
250 continue
251 w, v = items[idx]
252 if cur_w + w <= capacity:
253 nv = cur_v + v
254 if nv > best:
255 best = nv
256 ub_left = bound(idx + 1, cur_w + w, nv)
257 if ub_left > best:
258 heappush(pq, (-ub_left, idx + 1, cur_w + w, nv))
259 ub_right = bound(idx + 1, cur_w, cur_v)
260 if ub_right > best:
261 heappush(pq, (-ub_right, idx + 1, cur_w, cur_v))
262 return best
263
264
265def edmonds_karp(capacities, source, sink):
266 """有向图容量矩阵最大流，允许整数容量。Edmonds–Karp O(VE²)。"""
267 n = len(capacities)
268 if not n or source == sink or not 0 <= source < n or not 0 <= sink < n:
269 raise ValueError('源汇不合法')
270 if any(len(row) != n or any(c < 0 or not isinstance(c, int) for c in row) for row in capacities):
271 raise ValueError('容量须非负整数方阵')
272 res = [list(row) for row in capacities]
273 total = 0
274 while True:
275 parent = [-1] * n
276 parent[source] = source
277 todo = deque([source])
278 while todo and parent[sink] == -1:
279 u = todo.popleft()
280 for v, c in enumerate(res[u]):
281 if c > 0 and parent[v] == -1:
282 parent[v] = u
283 todo.append(v)
284 if v == sink:
285 break
286 if parent[sink] == -1:
287 break
288 v = sink
289 delta = float('inf')
290 while v != source:
291 u = parent[v]
292 delta = min(delta, res[u][v])
293 v = u
294 v = sink
295 while v != source:
296 u = parent[v]
297 res[u][v] -= delta
298 res[v][u] += delta
299 v = u
300 total += delta
301 return total
302
303
304def vertex_cover_approx(edges):
305 """极大匹配 2-近似顶点覆盖算法。O(V + E) 时间，近似比 ρ = 2。"""
306 covered = set()
307 cover = []
308 for u, v in edges:
309 if u not in covered and v not in covered:
310 covered.add(u)
311 covered.add(v)
312 cover.extend([u, v])
313 return cover
314
315
316if __name__ == '__main__':
317 print('二分:', lower_bound([1, 2, 2, 4], 2))
318 print('逆序对:', count_inversions([2, 3, 8, 6, 1]))
319 print('矩阵连乘:', matrix_chain_order([30, 35, 15, 5, 10, 20, 25]))
320 print('LCS:', lcs_length('ABCBDAB', 'BDCABA'))
321 print('背包(DP/BB):', knapsack_01([2, 2, 6, 5, 4], [6, 3, 5, 4, 6], 10),
322 knapsack_branch_and_bound([2, 2, 6, 5, 4], [6, 3, 5, 4, 6], 10))
323 print('4 皇后:', len(n_queens(4)))3 · 核心实现要点与复杂度对照
| 函数名 | 对应课程模块 | 时间 / 空间复杂度 | 笔试与机试关键防坑点 |
|---|---|---|---|
lower_bound(nums, target) | 模块 1 · 二分搜索 | \(O(\log n)\) / \(O(1)\) | 半开区间 [lo, hi) 循环不变式，返回首个 \(\ge ext{target}\) 的下标 |
merge_sort(nums) | 模块 1 · 分治排序 | \(O(n\log n)\) / \(O(n)\) | 合并时 a[i] <= b[j] 取等号保证排序稳定性 |
lcs_length(a, b) | 模块 2 · 动态规划 LCS | \(O(mn)\) / \(O(n)\) | 仅用两行一维数组滚动更新，将空间从 \(O(mn)\) 降至 \(O(n)\) |
knapsack_01(weights, values, capacity) | 模块 2 · 0-1 背包 DP | \(O(nC)\) 伪多项式 / \(O(C)\) | 内层容量循环必须倒序 range(capacity, w-1, -1)，防止同件物品重复装入 |
activity_selection(intervals) | 模块 2 · 贪心算法 | \(O(n\log n)\) / \(O(n)\)（排序副本及返回结果） | 严格按结束时间 x[1] 升序排序，兼容条件为 s >= last |
dijkstra(graph, source) | 模块 2 · 单源最短路 | \(O((V+E)\log(V+E))\) / \(O(V+E)\)（懒删除堆，输入图不计） | 要求所有边权非负；出堆时检查 if d > dist[u]: continue 跳过过期懒删除结点 |
n_queens(n) | 模块 3 · 回溯法排列/子集树 | 指数级 / 栈深 \(O(n)\) | 用三个集合 cols, d1(r-c), d2(r+c) \(O(1)\) 判冲突，递归返回后务必恢复现场 |
edmonds_karp(capacities, source, sink) | 模块 4 · 网络流最大流 | 矩阵扫描版上界 \(O(V^3E)\) / \(O(V^2)\)；经典邻接表实现为 \(O(VE^2)\) | BFS 寻找最短增广路径；沿增广路同时更新正向残量 -= delta 与反向退流边 += delta |
实现口径：上表空间包含排序副本、队列及结果容器（不计输入本身）；本页的 Edmonds–Karp Python 示例采用容量矩阵，BFS 每轮扫描 \(V^2\) 个矩阵单元，不能把邻接表教材复杂度直接当成这份实现的紧致界。quick_select 采用固定中间位置元素作轴值，未随机化，存在最坏 \(O(n^2)\) 的输入；分支限界背包示例假定正重量、非负价值，且两数组长度一致。
配套单元测试请查看：✅ 算法单元测试与暴力对拍器（test_algorithms.html）。