Python算法模板：面试刷题必备的二分查找、并查集与动态规划代码底稿-北京尧图网络

简介这是一份面向LeetCode与OJ刷题者的Python3算法模板合集定位为面试与日常练习的通用代码参考帮助读者摆脱重复造轮子的低效状态。作者系统梳理了常见数据结构与算法的通用写法并附上典型例题、题号与简要说明便于对照理解与迁移。资源包共71个文件以46个py模板与示例脚本为主辅以7个md笔记、11张png示意图及pdf速查表压缩后约951KB涵盖数组、链表、栈队列、堆、字典、二叉树、并查集、Trie以及二分、双指针、滑动窗口、回溯、分治、动态规划、BFS/DFS、位运算等专题。已有362人学习。读者可直接获得可编译运行的模板骨架、配套示例与Python3语法笔记既能用于面试前的快速复习也适合作为刷题时的代码底稿按注释替换为自身实现即可。1. 从刷题到面试这套 Python 算法模板到底能省多少时间如果你刷过 LeetCode 或者任何 OJ大概率经历过这种循环打开一道题先想思路再翻自己以前写的代码发现二分边界又写错了或者并查集的路径压缩忘了加然后花十分钟重新推导一遍。这套 Python_Algorithm_Templates 就是冲着这个场景来的——它把刷题和面试中最常用的算法与数据结构整理成了一套可以直接复制、直接改参数、直接跑测试的 Python 模板集合。它解决的不是“教你算法”的问题而是“你已经知道思路但每次都要重新处理边界和实现细节”的问题。适合两类人一是正在准备技术面试、需要快速手写代码的开发者二是平时打比赛或刷 OJ想有一套稳定可靠的代码底稿的人。模板覆盖了二分查找、排序、并查集、图论遍历、动态规划、字符串处理等常见模块每个模块都按“最小可用可扩展”的方式组织不是伪代码是能直接提交的 Python 实现。我见过太多人把算法模板当成“背下来就行”的东西结果面试时一紧张边界条件全乱。这套模板的价值在于它把边界处理显式地写进了代码结构里你只要理解每个参数的含义就能在压力下稳定输出。2. 模板的代码组织与核心模块拆解2.1 为什么按“算法族”而不是按“题目”来组织很多刷题笔记是按题目编号整理的第 1 题、第 2 题、第 15 题……这种组织方式适合复习特定题目但不适合面试场景。面试官不会问你“第 704 题怎么做”他会问“给你一个有序数组找目标值”。你需要的是从问题特征快速映射到算法族的能力。这套模板按算法族划分二分查找、双指针、滑动窗口、并查集、拓扑排序、Dijkstra、动态规划、回溯、单调栈等。每个族下面有基础版本和变体版本。比如二分查找它区分了“找精确值”“找左边界”“找右边界”三种场景而不是只给一个bisect调用。这种组织方式的好处是你在面试时先判断问题属于哪个族然后直接调用对应的模板结构只需要改比较条件和边界更新逻辑。我一般会建议把每个族的模板都手写三遍以上直到不用看代码就能写出正确的边界。2.2 二分查找模板三个版本与边界处理二分查找是面试中翻车率最高的算法之一不是因为思路难而是因为边界条件太多。这套模板给出了三个版本分别对应不同的查找目标。# 版本一查找精确值不存在返回 -1 def binary_search_exact(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 # 防止溢出Python 其实不会但习惯要好 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1 # 版本二查找左边界即第一个 target 的位置 def binary_search_left(nums, target): left, right 0, len(nums) # 注意右边界是 len(nums)不是 len(nums)-1 while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left # 可能等于 len(nums)表示所有元素都小于 target # 版本三查找右边界即最后一个 target 的位置 def binary_search_right(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left - 1 # 可能等于 -1表示所有元素都大于 target这三个版本的关键差异在三个地方右边界初始值是len(nums)-1还是len(nums)循环条件是left right还是left right更新时是right mid - 1还是right mid。很多人写二分时凭感觉改结果就是死循环或者漏掉边界元素。我一般会这样记如果搜索区间是闭区间[left, right]用版本一的结构如果搜索区间是左闭右开[left, right)用版本二或版本三的结构。版本二和版本三的区别只在于比较条件里有没有等号。这个规律一旦记住就不容易写错了。参数说明nums必须是有序数组升序排列。target是目标值。版本二返回的是插入位置版本三返回的是最后一个小于等于目标值的位置。如果返回值等于len(nums)或-1说明目标值超出了数组范围。2.3 并查集模板路径压缩与按秩合并并查集在图的连通性问题、朋友圈问题、冗余连接问题中非常常见。这套模板给出了完整的并查集实现包括路径压缩和按秩合并两个优化。class UnionFind: def __init__(self, n): self.parent list(range(n)) # 每个元素的父节点初始指向自己 self.rank [0] * n # 秩用于按秩合并 def find(self, x): # 路径压缩查找过程中把沿途节点的父节点直接指向根 if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return False # 已经在同一个集合中 # 按秩合并把秩小的树合并到秩大的树上 if self.rank[root_x] self.rank[root_y]: self.parent[root_x] root_y elif self.rank[root_x] self.rank[root_y]: self.parent[root_y] root_x else: self.parent[root_y] root_x self.rank[root_x] 1 return True def connected(self, x, y): return self.find(x) self.find(y)路径压缩的作用是在find过程中把树压平使得后续查找接近 O(1)。按秩合并的作用是避免树退化成链表。两个优化一起用并查集的操作复杂度接近常数级别。参数说明n是元素个数元素编号从 0 到 n-1。find(x)返回 x 所在集合的根节点。union(x, y)合并两个集合返回 True 表示合并成功False 表示已经在同一集合。connected(x, y)判断两个元素是否连通。常见坑如果只写路径压缩不写按秩合并在极端情况下仍然可能退化如果只写按秩合并不写路径压缩查找效率会低一些。两个都写是最稳的。另外find用递归实现时如果数据量特别大可能触发递归深度限制可以改成迭代版本。2.4 图论遍历模板BFS 与 DFS 的适用场景图论遍历是面试中的高频考点但很多人分不清什么时候用 BFS什么时候用 DFS。这套模板给出了两个版本的实现并且标注了适用场景。from collections import deque # BFS适合找最短路径、层序遍历、连通分量 def bfs(graph, start): visited set([start]) queue deque([start]) distance {start: 0} # 记录到起点的距离 while queue: node queue.popleft() for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) distance[neighbor] distance[node] 1 return visited, distance # DFS适合找所有路径、拓扑排序、回溯类问题 def dfs(graph, start, visitedNone): if visited is None: visited set() visited.add(start) for neighbor in graph[start]: if neighbor not in visited: dfs(graph, neighbor, visited) return visitedBFS 用队列实现按层扩展所以第一次访问到某个节点时走过的路径一定是最短的。DFS 用递归或栈实现一条路走到黑适合需要探索所有可能性的场景。参数说明graph是邻接表表示的图通常用字典或列表的列表。start是起始节点。BFS 返回访问过的节点集合和距离字典DFS 返回访问过的节点集合。我一般会这样选如果问题问“最短”“最少几步”“最近”用 BFS如果问题问“所有方案”“是否存在”“能否完成”用 DFS。这个判断规则能覆盖大部分场景。3. 动态规划与回溯模板的实战用法3.1 动态规划从记忆化搜索到递推动态规划是面试中最难临时推导的算法之一因为状态定义和转移方程需要根据题目现场设计。但这套模板给出了一个通用的思考框架先写记忆化搜索再改写成递推。# 记忆化搜索版本自顶向下适合状态转移不明显的题目 from functools import lru_cache def dp_memo(nums): n len(nums) lru_cache(maxsizeNone) def dfs(i, state): if i n: return 0 # 边界条件 # 转移逻辑根据 state 决定下一步 res float(inf) # 这里根据具体题目填充 return res return dfs(0, initial_state) # 递推版本自底向上适合状态转移清晰的题目 def dp_iter(nums): n len(nums) dp [0] * (n 1) # 根据状态维度调整 # 初始化边界 for i in range(1, n 1): # 转移方程 pass return dp[n]记忆化搜索的好处是不用考虑遍历顺序直接按递归逻辑写加上lru_cache就能自动缓存。缺点是递归深度可能受限而且有些题目用递推更直观。我一般会先用记忆化搜索把状态定义和转移方程理清楚然后再改写成递推版本这样既保证了正确性又避免了递归的性能问题。参数说明nums是输入数组state是附加状态比如是否持有股票、当前剩余次数等。lru_cache的参数maxsizeNone表示不限制缓存大小。递推版本中dp数组的维度取决于状态数量。常见坑记忆化搜索时如果状态参数包含可变对象比如列表lru_cache会报错需要转成元组。递推版本中遍历顺序很重要必须保证计算dp[i]时依赖的状态已经计算过。3.2 回溯模板排列、组合、子集的统一写法回溯类问题在面试中出现的频率很高但很多人写回溯时容易漏掉去重或者剪枝。这套模板给出了排列、组合、子集三种场景的统一写法。def backtrack(nums, path, res, start0, usedNone): # 终止条件根据题目调整 if len(path) len(nums): # 排列的终止条件 res.append(path[:]) return for i in range(start, len(nums)): # 剪枝同一层不能重复选择 if used and used[i]: continue # 去重排序后跳过相邻重复元素 if i start and nums[i] nums[i-1] and not (used and used[i-1]): continue path.append(nums[i]) if used: used[i] True backtrack(nums, path, res, i 1 if not used else start, used) if used: used[i] False path.pop()这个模板的关键在于start参数和used数组的配合。组合和子集问题用start控制选择范围排列问题用used标记已选元素。去重逻辑需要先对数组排序然后跳过同一层中重复的元素。参数说明nums是输入数组path是当前路径res是结果集start是选择起始位置used是标记数组。排列问题传入used数组组合和子集问题不传。我一般会先判断问题类型如果顺序重要用排列模板如果顺序不重要用组合模板如果要求所有子集用子集模板。判断清楚之后再根据是否需要去重来调整剪枝条件。4. 避坑与常见问题排查4.1 二分查找死循环现象、原因与解决现象代码运行后一直不结束或者提交后报超时。原因循环条件写成了while left right但更新时用了left mid或right mid导致区间没有缩小。解决检查循环条件和更新逻辑是否匹配。如果循环条件是left right那么更新时必须保证区间缩小通常用left mid 1或right mid。如果循环条件是left right更新时用left mid 1和right mid - 1。4.2 并查集路径压缩递归爆栈现象、原因与解决现象数据量较大时find方法报递归深度超限。原因路径压缩用递归实现树的高度虽然被压缩了但递归调用本身仍然可能很深。解决改成迭代版本用循环实现路径压缩。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 root4.3 BFS 忘记标记已访问现象、原因与解决现象程序陷入死循环或者内存溢出。原因在 BFS 中节点出队时才标记已访问导致同一个节点被多次入队。解决在节点入队时就标记已访问而不是出队时标记。这样能保证每个节点最多入队一次。4.4 动态规划数组越界现象、原因与解决现象提交后报IndexError。原因dp数组的长度没有根据状态维度正确设置或者遍历时索引超出了数组范围。解决先确定状态数量和边界条件再决定dp数组的长度。通常dp数组长度是n1或n2具体取决于转移方程中是否用到dp[i-1]或dp[i-2]。4.5 回溯去重不彻底现象、原因与解决现象结果集中出现重复的排列或组合。原因去重条件写错了或者没有先对数组排序。解决先对数组排序然后在循环中判断i start and nums[i] nums[i-1]同时结合used数组判断是否是同一层重复。如果是排列问题还需要判断used[i-1]是否为 False确保跳过的是同一层的重复元素而不是不同层的相同元素。5. 把模板变成肌肉记忆我的练习方法与验证技巧模板看得再多不练都是别人的。我自己的做法是每个模板手写三遍第一遍照着抄第二遍默写第三遍在 LeetCode 上找三道对应的题目用模板去套看看能不能通过。如果某道题套不进去说明我对模板的适用边界还没理解清楚需要回去看模板的参数说明和适用场景。验证模板是否正确我一般会用三个测试用例空输入、单元素输入、正常多元素输入。比如二分查找我会测空数组、只有一个元素的数组、目标值在数组开头、目标值在数组结尾、目标值不存在这五种情况。并查集会测合并两个不同集合、合并两个相同集合、查找不存在的元素。BFS 会测只有一个节点的图、有环的图、不连通的图。还有一个技巧是把模板代码放在一个单独的文件里用pytest或者简单的assert写测试。这样每次修改模板后跑一遍测试就知道有没有改坏。我一般会在模板文件末尾加一段if __name__ __main__:的测试代码方便快速验证。if __name__ __main__: # 二分查找测试 assert binary_search_exact([1, 2, 3, 4, 5], 3) 2 assert binary_search_exact([1, 2, 3, 4, 5], 6) -1 assert binary_search_left([1, 2, 2, 2, 3], 2) 1 assert binary_search_right([1, 2, 2, 2, 3], 2) 3 # 并查集测试 uf UnionFind(5) assert uf.union(0, 1) True assert uf.union(1, 2) True assert uf.connected(0, 2) True assert uf.connected(0, 3) False # BFS 测试 graph {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]} visited, distance bfs(graph, 0) assert visited {0, 1, 2, 3} assert distance[3] 2 print(所有测试通过)从那以后我每次改模板都会先跑一遍这个测试脚本确认没有引入回归问题。这个习惯帮我省了很多调试时间也让我对模板的边界条件更有信心。希望帮到你。本文还有配套的精品资源点击获取

Python算法模板：面试刷题必备的二分查找、并查集与动态规划代码底稿

相关推荐

Java实现ε-closure：NFA转DFA的核心算法实战

Python LSTM日志异常检测实战：无需标注数据的时序建模方案

SpringBoot+Vue前后端分离：电商商品管理系统完整实战

更多资讯

多模态手机认知筛查：把评估融入日常行为

OpenCV双目三维重建从标定到点云：SGBM匹配与三角测量实战指南

如何让项目对AI编程助手友好：full-stack-ai-agent-template的CLAUDE.md与.claude工具集完全指南

Nezha Hook机制揭秘：不改用户配置给Claude Code和Codex注入事件监听的设计之道

Ogre双渲染后端与网络同步架构实战解析

文献综述降AI检测实操：嘎嘎降AI怎么用才不翻车

今日更新

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？