简介这是一份面向LeetCode与OJ刷题者的Python3算法模板合集定位为面试与日常练习的通用代码参考帮助读者摆脱重复造轮子的低效状态。作者系统整理了常用数据结构与经典算法的通用模板并附上典型例题、题号与简要说明便于对照理解与迁移。资源包共71个文件以46个py模板脚本为主体覆盖数组、链表、栈、队列、堆、字典、并查集、字典树、二叉树等数据结构以及二分、双指针、滑动窗口、回溯、分治、动态规划、BFS、DFS、位运算等算法另有7个md笔记、11张png示意图、2份pdf速查资料及若干说明文件压缩包约951KB。目前已有362人学习。读者可借此快速掌握各算法的标准写法与最佳实践理解模板背后的共性思路并依据注释替换语法糖轻松扩展到Java、C等其他语言。1. 刷题效率翻倍的秘密为什么你需要一套 Python 算法模板如果你在 LeetCode 或各类 OJ 平台上刷过 50 道以上的题大概率经历过这样的场景明明上周刚做过一道二分查找这周遇到「搜索旋转排序数组」时边界条件又开始靠玄学调试或者面试白板上写快速排序left right和left right纠结了半分钟。问题不在于你不会算法而在于每次都在从零推导细节没有把可复用的部分沉淀成模板。Python 算法模板要解决的就是这件事把二分、双指针、回溯、动态规划、并查集、图论遍历这些高频考点的代码骨架固定下来让大脑专注于「这题该用哪个模板」而不是「这个模板的边界怎么写」。它适合三类人准备技术面试的求职者、打周赛想提速的竞赛选手、以及想系统整理算法知识体系的开发者。接下来的内容会从模板的设计原则讲起逐个拆解核心模板的代码、参数和适用边界最后给出组合使用与验证的方法。2. 模板设计的底层逻辑从题目特征到代码骨架的映射2.1 为什么「背模板」比「背题解」更抗遗忘很多人刷题的方式是记住某道题的具体解法比如「两数之和用哈希表」。但题目一变——变成「三数之和」「最接近的三数之和」——记忆就失效了。模板的思路不同它提取的是问题结构与代码结构之间的映射关系。以二分查找为例它的本质不是「在有序数组里找目标」而是「在一个具有单调性的判定函数上找分界点」。一旦你接受这个抽象就会发现「找第一个大于等于 target 的位置」「找旋转数组最小值」「找峰值」全部是同一个骨架只是判定条件不同。模板把骨架固定下来你只需要替换判定逻辑。这种做法的好处是记忆负担从 O(题目数) 降到 O(模板数)。LeetCode 上千道题核心模板不超过 20 个。而且模板经过大量验证边界条件已经被打磨过不会因为手抖写错mid的取整方向而翻车。2.2 模板的四个设计原则我在整理自己的模板库时遵循四条原则这里直接给出来后面每个模板都会体现原则一接口统一。所有二分模板统一返回「第一个满足条件的位置」不返回-1或布尔值。调用方根据返回值判断是否存在。这样避免每个模板的返回值语义不一致。原则二区间语义明确。要么全用左闭右闭[lo, hi]要么全用左闭右开[lo, hi)绝不混用。混用是二分 bug 的头号来源。原则三循环不变量写在注释里。每个模板的 while 循环上方必须有一行注释说明「循环结束时lo 指向什么」。这不是写给读者看的是写给自己调试时看的。原则四模板只保留骨架不包含题目特定逻辑。比如并查集模板只包含find、union、init不包含「统计连通分量个数」这种题目逻辑。题目逻辑在调用处写。下面这张表是我常用的模板清单按考察频率排序模板名称典型触发词时间复杂度易错点二分查找有序、单调、第 K 小O(log n)边界更新方向双指针有序数组、去重、滑动窗口O(n)指针移动条件回溯全排列、子集、组合总和指数级剪枝与去重动态规划最值、方案数、可行性视状态而定状态定义与转移并查集连通性、朋友圈、冗余连接近 O(1)路径压缩写法BFS/DFS网格、图遍历、层序O(VE)访问标记时机2.3 一个最小可用的二分模板及其参数说明先看最核心的二分模板。这个模板解决的是「在有序数组中找第一个大于等于 target 的位置」也叫lower_bounddef lower_bound(nums, target): 返回第一个 target 的下标。 如果所有元素都 target返回 len(nums)。 区间语义左闭右闭 [lo, hi]初始 hi len(nums) - 1。 循环不变量循环结束时lo 是第一个满足 nums[lo] target 的位置。 lo, hi 0, len(nums) - 1 while lo hi: mid lo (hi - lo) // 2 # 防止溢出的写法Python 里其实不会溢出但保持习惯 if nums[mid] target: hi mid - 1 # mid 满足条件但可能不是第一个继续往左找 else: lo mid 1 # mid 不满足条件答案一定在右边 return lo # lo 就是第一个满足条件的位置这段代码的关键在于hi mid - 1和lo mid 1的对称性。当nums[mid] target时mid本身可能是答案但我们要找的是第一个所以把搜索区间收缩到[lo, mid-1]同时用hi记录「已知不满足条件的位置」。循环结束时lo hilo恰好是第一个满足条件的位置。参数说明nums必须是有序数组升序target是目标值。返回值范围是[0, len(nums)]注意可能等于len(nums)调用方需要判断lo len(nums) and nums[lo] target才能确认目标存在。如果题目要求「找最后一个小于等于 target 的位置」不需要重写模板只需要对nums取反或者把判定条件改成nums[mid] target并调整返回值。这就是模板的价值变体通过参数化解决不重新推导。3. 高频模板逐个拆解二分、双指针、回溯的代码与边界3.1 二分查找的三种变体与统一写法上一节给了lower_bound实际刷题中还会遇到另外两种变体找最后一个 target的位置upper_bound的变体以及浮点数二分。先看整数二分的统一写法。我习惯把二分写成「判定函数 找分界点」的形式。定义一个布尔函数check(x)它在前半段为False后半段为True或者反过来二分的目标就是找到第一个True的位置。这样所有整数二分都可以套同一个骨架def binary_search(lo, hi, check): 在 [lo, hi] 范围内找第一个使 check(x) 为 True 的位置。 前提check 具有单调性即存在分界点 p使得 x p 时 check(x) 为 False x p 时 check(x) 为 True。 如果不存在这样的 p返回 hi 1。 while lo hi: mid lo (hi - lo) // 2 if check(mid): hi mid - 1 else: lo mid 1 return lo这个骨架的妙处在于check是外部传入的你可以把任何单调判定塞进去。比如「找第一个大于等于 target 的位置」check(x)就是nums[x] target「找旋转数组最小值」check(x)就是nums[x] nums[-1]。浮点数二分则不同它不依赖整数下标而是直接对实数区间收缩。模板如下def float_binary_search(lo, hi, check, eps1e-7): 在实数区间 [lo, hi] 上二分直到区间长度小于 eps。 返回满足 check 的近似分界点。 while hi - lo eps: mid (lo hi) / 2 if check(mid): hi mid else: lo mid return lo浮点数二分的坑在于精度选择。eps太小会导致死循环或超时太大则答案不够精确。经验值是1e-7如果题目要求保留 6 位小数1e-7足够如果要求 10 位需要调到1e-10。另外浮点二分通常固定循环 100 次而不是用eps判断因为 100 次后区间长度已经缩小到2^-100远超任何精度要求而且避免了eps选择不当的问题。3.2 双指针从「两数之和」到「滑动窗口」的通用框架双指针的触发信号通常是「有序数组」或「连续子数组」。它有两个分支对撞指针和快慢指针。对撞指针用于有序数组的求和、去重快慢指针用于链表找环、数组原地删除。先看对撞指针的通用框架以「两数之和 II」为例def two_sum_sorted(nums, target): 在升序数组 nums 中找两个数使它们的和等于 target。 返回这两个数的下标1-based如果不存在返回 []。 对撞指针左指针从 0 开始右指针从末尾开始。 lo, hi 0, len(nums) - 1 while lo hi: s nums[lo] nums[hi] if s target: return [lo 1, hi 1] elif s target: lo 1 # 和太小左指针右移增大和 else: hi - 1 # 和太大右指针左移减小和 return []这段代码的正确性依赖于数组有序当s target时nums[lo]与任何nums[hi]的组合都不可能等于target因为nums[hi]已经是最大的可选值所以lo可以安全右移。这个推理过程是双指针模板的核心不理解它就会在「三数之和」的去重逻辑上翻车。滑动窗口是双指针的另一个分支框架如下def sliding_window(nums, condition): 在 nums 上维护一个窗口 [left, right)使窗口内元素满足 condition。 返回满足条件的最短/最长窗口长度。 left 0 result 0 # 根据题目改成 float(inf) 或 0 window_state {} # 窗口内的统计信息如字符计数、和等 for right in range(len(nums)): # 1. 右边界进入窗口更新 window_state # update(window_state, nums[right]) while not condition(window_state): # 2. 条件不满足左边界收缩 # remove(window_state, nums[left]) left 1 # 3. 此时窗口满足条件更新答案 # result max(result, right - left 1) return result这个框架的注释部分需要根据题目填充。关键点是while循环的条件是「窗口不满足条件」而不是「窗口满足条件」。很多人在这一步写反导致窗口无限扩张或收缩过度。另外window_state的更新和移除必须对称进入时加什么离开时就减什么。3.3 回溯模板排列、组合、子集的统一骨架回溯的题目看起来五花八门但骨架高度统一。核心是「做选择 → 递归 → 撤销选择」三步。下面是一个通用回溯模板def backtrack(nums, path, result, used): 通用回溯骨架。 nums: 输入数组 path: 当前路径 result: 结果集 used: 标记数组记录哪些元素已被使用 # 终止条件根据题目决定比如 len(path) len(nums) if len(path) len(nums): result.append(path[:]) # 注意拷贝不能直接 append(path) return for i in range(len(nums)): # 剪枝条件根据题目决定 if used[i]: continue # 做选择 used[i] True path.append(nums[i]) # 递归 backtrack(nums, path, result, used) # 撤销选择 path.pop() used[i] False这个模板能解决全排列问题。如果换成组合问题如「组合总和」需要引入start参数避免重复def backtrack_combination(nums, target, start, path, result): 组合问题回溯模板。 start: 本轮搜索的起始下标保证组合不重复。 if target 0: result.append(path[:]) return if target 0: return for i in range(start, len(nums)): # 剪枝如果 nums 已排序且 nums[i] target后面的更大直接 break if nums[i] target: break path.append(nums[i]) backtrack_combination(nums, target - nums[i], i, path, result) # 注意是 i 不是 i1 path.pop()组合模板与排列模板的关键区别在start参数和递归时的下标传递。排列用used数组标记组合用start控制搜索起点。如果允许重复使用元素递归传i不允许重复传i1。这个细节是回溯题最容易混淆的地方建议在模板注释里写清楚。4. 动态规划与图论模板状态定义、转移方程与遍历顺序4.1 动态规划从「爬楼梯」到「背包」的状态设计动态规划的难点不在代码而在状态定义。模板能帮你固定代码结构但状态定义需要你自己想。先看最基础的线性 DP 模板def linear_dp(n): 线性 DP 模板以爬楼梯为例。 dp[i] 表示到达第 i 阶的方法数。 转移方程dp[i] dp[i-1] dp[i-2] if n 2: return n dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]这个模板可以优化空间到 O(1)但初学时建议先写完整数组确认转移方程正确后再优化。空间优化的版本容易在「滚动变量更新顺序」上出错比如prev, curr curr, prev curr这种写法如果顺序写反就会得到错误结果。背包问题是 DP 的另一个高频分支。01 背包的模板如下def knapsack_01(weights, values, capacity): 01 背包模板。 dp[j] 表示容量为 j 时能装的最大价值。 外层遍历物品内层逆序遍历容量。 dp [0] * (capacity 1) for i in range(len(weights)): for j in range(capacity, weights[i] - 1, -1): # 逆序 dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]内层循环必须逆序这是 01 背包的核心。如果正序就变成了完全背包每个物品可以用无限次。这个区别在面试中经常被追问建议在模板注释里用感叹号标出来。完全背包的模板只需要把内层循环改成正序def knapsack_complete(weights, values, capacity): 完全背包模板。 与 01 背包的唯一区别内层循环正序。 dp [0] * (capacity 1) for i in range(len(weights)): for j in range(weights[i], capacity 1): # 正序 dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]4.2 并查集路径压缩与按秩合并的完整实现并查集用于处理连通性问题模板非常固定。下面是一个带路径压缩和按秩合并的完整实现class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n # 秩用于按秩合并 self.count 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]: root_x, root_y root_y, root_x self.parent[root_y] root_x if self.rank[root_x] self.rank[root_y]: self.rank[root_x] 1 self.count - 1 return True def connected(self, x, y): return self.find(x) self.find(y)路径压缩的递归写法简洁但可能栈溢出数据量大时建议改成迭代def find_iterative(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并查集的坑主要在union的返回值上。有些题目需要判断「这条边是否连接了两个不同的连通分量」此时union返回False表示已经在同一分量这条边是冗余的。这个返回值在「冗余连接」类题目中直接决定答案。4.3 BFS 与 DFS网格遍历的两种写法与选择依据网格遍历是图论的基础BFS 和 DFS 都能做但适用场景不同。BFS 适合找最短路径DFS 适合找所有路径或连通块。先看 BFS 模板from collections import deque def bfs_grid(grid, start, target): 网格 BFS 模板找从 start 到 target 的最短步数。 grid: 二维数组0 表示可走1 表示障碍。 rows, cols len(grid), len(grid[0]) queue deque([(start[0], start[1], 0)]) # (行, 列, 步数) visited {(start[0], start[1])} directions [(0, 1), (0, -1), (1, 0), (-1, 0)] while queue: r, c, steps queue.popleft() if (r, c) target: return steps for dr, dc in directions: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and grid[nr][nc] 0 and (nr, nc) not in visited: visited.add((nr, nc)) queue.append((nr, nc, steps 1)) return -1BFS 的关键是「入队时标记 visited」而不是「出队时标记」。如果出队时才标记同一个节点可能被多次入队导致超时或重复计算。这个细节在网格题中非常关键。DFS 模板则用递归或栈实现def dfs_grid(grid, r, c, visited): 网格 DFS 模板用于遍历连通块。 rows, cols len(grid), len(grid[0]) if r 0 or r rows or c 0 or c cols: return if grid[r][c] 1 or (r, c) in visited: return visited.add((r, c)) # 处理当前节点 for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: dfs_grid(grid, r dr, c dc, visited)DFS 的坑在于递归深度。网格最大可能有 10^5 个节点Python 默认递归深度 1000 会直接报RecursionError。解决办法是sys.setrecursionlimit(1000000)或者改用栈模拟递归。我一般会在模板文件开头统一设置递归深度避免每道题都忘记。5. 避坑与排查模板用错时的 5 个典型症状5.1 二分死循环lo和hi更新不对称现象程序卡在 while 循环里不退出或者提交后超时。原因lo mid和hi mid同时出现且mid取整方向导致区间不收缩。比如mid (lo hi) // 2时如果lo mid当hi lo 1时mid lo区间不变死循环。解决统一用lo mid 1和hi mid - 1或者用mid (lo hi 1) // 2配合lo mid。关键是保证每次迭代区间长度至少减少 1。我的习惯是永远用lo mid 1和hi mid - 1配合while lo hi这样不会死循环。5.2 回溯结果重复忘记去重或start参数用错现象结果集中出现重复的组合或排列。原因组合问题中递归传了下标i而不是i1导致同一元素被重复使用或者数组有重复元素但没有排序去重。解决组合问题先排序然后在 for 循环中加if i start and nums[i] nums[i-1]: continue。排列问题用used数组同时排序后加if i 0 and nums[i] nums[i-1] and not used[i-1]: continue。这个条件的意思是「如果前一个相同元素没被使用说明当前是重复分支跳过」。5.3 滑动窗口越界left收缩过度或不足现象答案偏小窗口收缩过度或超时窗口不收缩。原因while条件写反或者left更新后没有重新检查条件。解决记住「窗口不满足条件时收缩」这个原则。写完后用一个小例子手动模拟比如nums [1,2,3]condition是「窗口和 3」手动走一遍看left和right的变化。如果模拟结果和预期不符检查while条件。5.4 并查集find栈溢出递归深度过大现象数据量大时RecursionError。原因路径压缩的递归写法在树退化成链时递归深度等于节点数。解决改用迭代版find或者设置sys.setrecursionlimit。但设置递归深度只是缓解根本办法是迭代。我在模板库里默认用迭代版递归版只作为备选。5.5 DP 空间优化后答案错误滚动变量更新顺序现象完整数组版答案正确空间优化版答案错误。原因滚动变量更新时新值覆盖了旧值导致后续计算使用了错误的数据。解决在更新前先用临时变量保存旧值或者调整更新顺序。比如 01 背包的空间优化版内层必须逆序就是为了避免同一物品被多次使用。如果正序dp[j]会用到已经更新过的dp[j - weights[i]]相当于完全背包。6. 模板的组合使用与验证从刷题到面试的最后一公里模板单独会写只是第一步真正拉开差距的是组合使用和快速验证。一道中等难度的题往往需要两个模板拼接比如「二分 贪心」「BFS 状态压缩」「DP 前缀和」。这时候模板的接口统一性就体现出价值了lower_bound返回下标可以直接作为另一个函数的输入并查集的union返回布尔值可以直接用于判断冗余边。我自己的验证习惯是「三组测试 一个暴力对拍」。三组测试分别是最小规模n0 或 n1、常规规模、边界规模全部相同元素、已排序、逆序。暴力对拍则是写一个 O(n^2) 或 O(2^n) 的暴力解法用随机数据跑 1000 次对比两个解法的输出。这个方法在周赛里救过我很多次尤其是 DP 题状态转移写错时暴力对拍能立刻定位。下面是一个对拍脚本的骨架可以直接套用import random def brute_force(nums): 暴力解法根据题目替换。 # 示例求最大子数组和 best float(-inf) for i in range(len(nums)): s 0 for j in range(i, len(nums)): s nums[j] best max(best, s) return best def fast_solution(nums): 模板解法根据题目替换。 # 示例Kadane 算法 best cur nums[0] for x in nums[1:]: cur max(x, cur x) best max(best, cur) return best def stress_test(): for _ in range(1000): n random.randint(1, 20) nums [random.randint(-10, 10) for _ in range(n)] if brute_force(nums) ! fast_solution(nums): print(Found mismatch:, nums) print(brute:, brute_force(nums), fast:, fast_solution(nums)) return print(All tests passed.) stress_test()这个脚本的关键是random.randint的范围要覆盖负数、零和正数否则可能漏掉边界情况。另外对拍次数建议至少 1000 次太少可能碰不到反例。最后一个技巧是关于模板的「版本管理」。我会把每个模板单独存成一个.py文件文件名就是模板名比如lower_bound.py、union_find.py。文件头部用注释写清楚适用场景、时间复杂度和易错点。刷题时直接from templates import lower_bound不重复造轮子。面试前一周我会把这些模板文件过一遍重点看注释里的易错点而不是重新推导。这个习惯让我在面试中写二分和并查集时几乎不再出错省下的时间可以用来思考题目本身的难点。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/13 20:54:38 · 阅读 1.2k Python算法模板：二分、双指针、回溯、DP与并查集高效刷题指南
简介这是一份面向LeetCode与OJ刷题者的Python3算法模板合集定位为面试与日常练习的通用代码参考帮助读者摆脱重复造轮子的低效状态。作者系统整理了常用数据结构与经典算法的通用模板并附上典型例题、题号与简要说明便于对照理解与迁移。资源包共71个文件以46个py模板脚本为主体覆盖数组、链表、栈、队列、堆、字典、并查集、字典树、二叉树等数据结构以及二分、双指针、滑动窗口、回溯、分治、动态规划、BFS、DFS、位运算等算法另有7个md笔记、11张png示意图、2份pdf速查资料及若干说明文件压缩包约951KB。目前已有362人学习。读者可借此快速掌握各算法的标准写法与最佳实践理解模板背后的共性思路并依据注释替换语法糖轻松扩展到Java、C等其他语言。1. 刷题效率翻倍的秘密为什么你需要一套 Python 算法模板如果你在 LeetCode 或各类 OJ 平台上刷过 50 道以上的题大概率经历过这样的场景明明上周刚做过一道二分查找这周遇到「搜索旋转排序数组」时边界条件又开始靠玄学调试或者面试白板上写快速排序left right和left right纠结了半分钟。问题不在于你不会算法而在于每次都在从零推导细节没有把可复用的部分沉淀成模板。Python 算法模板要解决的就是这件事把二分、双指针、回溯、动态规划、并查集、图论遍历这些高频考点的代码骨架固定下来让大脑专注于「这题该用哪个模板」而不是「这个模板的边界怎么写」。它适合三类人准备技术面试的求职者、打周赛想提速的竞赛选手、以及想系统整理算法知识体系的开发者。接下来的内容会从模板的设计原则讲起逐个拆解核心模板的代码、参数和适用边界最后给出组合使用与验证的方法。2. 模板设计的底层逻辑从题目特征到代码骨架的映射2.1 为什么「背模板」比「背题解」更抗遗忘很多人刷题的方式是记住某道题的具体解法比如「两数之和用哈希表」。但题目一变——变成「三数之和」「最接近的三数之和」——记忆就失效了。模板的思路不同它提取的是问题结构与代码结构之间的映射关系。以二分查找为例它的本质不是「在有序数组里找目标」而是「在一个具有单调性的判定函数上找分界点」。一旦你接受这个抽象就会发现「找第一个大于等于 target 的位置」「找旋转数组最小值」「找峰值」全部是同一个骨架只是判定条件不同。模板把骨架固定下来你只需要替换判定逻辑。这种做法的好处是记忆负担从 O(题目数) 降到 O(模板数)。LeetCode 上千道题核心模板不超过 20 个。而且模板经过大量验证边界条件已经被打磨过不会因为手抖写错mid的取整方向而翻车。2.2 模板的四个设计原则我在整理自己的模板库时遵循四条原则这里直接给出来后面每个模板都会体现原则一接口统一。所有二分模板统一返回「第一个满足条件的位置」不返回-1或布尔值。调用方根据返回值判断是否存在。这样避免每个模板的返回值语义不一致。原则二区间语义明确。要么全用左闭右闭[lo, hi]要么全用左闭右开[lo, hi)绝不混用。混用是二分 bug 的头号来源。原则三循环不变量写在注释里。每个模板的 while 循环上方必须有一行注释说明「循环结束时lo 指向什么」。这不是写给读者看的是写给自己调试时看的。原则四模板只保留骨架不包含题目特定逻辑。比如并查集模板只包含find、union、init不包含「统计连通分量个数」这种题目逻辑。题目逻辑在调用处写。下面这张表是我常用的模板清单按考察频率排序模板名称典型触发词时间复杂度易错点二分查找有序、单调、第 K 小O(log n)边界更新方向双指针有序数组、去重、滑动窗口O(n)指针移动条件回溯全排列、子集、组合总和指数级剪枝与去重动态规划最值、方案数、可行性视状态而定状态定义与转移并查集连通性、朋友圈、冗余连接近 O(1)路径压缩写法BFS/DFS网格、图遍历、层序O(VE)访问标记时机2.3 一个最小可用的二分模板及其参数说明先看最核心的二分模板。这个模板解决的是「在有序数组中找第一个大于等于 target 的位置」也叫lower_bounddef lower_bound(nums, target): 返回第一个 target 的下标。 如果所有元素都 target返回 len(nums)。 区间语义左闭右闭 [lo, hi]初始 hi len(nums) - 1。 循环不变量循环结束时lo 是第一个满足 nums[lo] target 的位置。 lo, hi 0, len(nums) - 1 while lo hi: mid lo (hi - lo) // 2 # 防止溢出的写法Python 里其实不会溢出但保持习惯 if nums[mid] target: hi mid - 1 # mid 满足条件但可能不是第一个继续往左找 else: lo mid 1 # mid 不满足条件答案一定在右边 return lo # lo 就是第一个满足条件的位置这段代码的关键在于hi mid - 1和lo mid 1的对称性。当nums[mid] target时mid本身可能是答案但我们要找的是第一个所以把搜索区间收缩到[lo, mid-1]同时用hi记录「已知不满足条件的位置」。循环结束时lo hilo恰好是第一个满足条件的位置。参数说明nums必须是有序数组升序target是目标值。返回值范围是[0, len(nums)]注意可能等于len(nums)调用方需要判断lo len(nums) and nums[lo] target才能确认目标存在。如果题目要求「找最后一个小于等于 target 的位置」不需要重写模板只需要对nums取反或者把判定条件改成nums[mid] target并调整返回值。这就是模板的价值变体通过参数化解决不重新推导。3. 高频模板逐个拆解二分、双指针、回溯的代码与边界3.1 二分查找的三种变体与统一写法上一节给了lower_bound实际刷题中还会遇到另外两种变体找最后一个 target的位置upper_bound的变体以及浮点数二分。先看整数二分的统一写法。我习惯把二分写成「判定函数 找分界点」的形式。定义一个布尔函数check(x)它在前半段为False后半段为True或者反过来二分的目标就是找到第一个True的位置。这样所有整数二分都可以套同一个骨架def binary_search(lo, hi, check): 在 [lo, hi] 范围内找第一个使 check(x) 为 True 的位置。 前提check 具有单调性即存在分界点 p使得 x p 时 check(x) 为 False x p 时 check(x) 为 True。 如果不存在这样的 p返回 hi 1。 while lo hi: mid lo (hi - lo) // 2 if check(mid): hi mid - 1 else: lo mid 1 return lo这个骨架的妙处在于check是外部传入的你可以把任何单调判定塞进去。比如「找第一个大于等于 target 的位置」check(x)就是nums[x] target「找旋转数组最小值」check(x)就是nums[x] nums[-1]。浮点数二分则不同它不依赖整数下标而是直接对实数区间收缩。模板如下def float_binary_search(lo, hi, check, eps1e-7): 在实数区间 [lo, hi] 上二分直到区间长度小于 eps。 返回满足 check 的近似分界点。 while hi - lo eps: mid (lo hi) / 2 if check(mid): hi mid else: lo mid return lo浮点数二分的坑在于精度选择。eps太小会导致死循环或超时太大则答案不够精确。经验值是1e-7如果题目要求保留 6 位小数1e-7足够如果要求 10 位需要调到1e-10。另外浮点二分通常固定循环 100 次而不是用eps判断因为 100 次后区间长度已经缩小到2^-100远超任何精度要求而且避免了eps选择不当的问题。3.2 双指针从「两数之和」到「滑动窗口」的通用框架双指针的触发信号通常是「有序数组」或「连续子数组」。它有两个分支对撞指针和快慢指针。对撞指针用于有序数组的求和、去重快慢指针用于链表找环、数组原地删除。先看对撞指针的通用框架以「两数之和 II」为例def two_sum_sorted(nums, target): 在升序数组 nums 中找两个数使它们的和等于 target。 返回这两个数的下标1-based如果不存在返回 []。 对撞指针左指针从 0 开始右指针从末尾开始。 lo, hi 0, len(nums) - 1 while lo hi: s nums[lo] nums[hi] if s target: return [lo 1, hi 1] elif s target: lo 1 # 和太小左指针右移增大和 else: hi - 1 # 和太大右指针左移减小和 return []这段代码的正确性依赖于数组有序当s target时nums[lo]与任何nums[hi]的组合都不可能等于target因为nums[hi]已经是最大的可选值所以lo可以安全右移。这个推理过程是双指针模板的核心不理解它就会在「三数之和」的去重逻辑上翻车。滑动窗口是双指针的另一个分支框架如下def sliding_window(nums, condition): 在 nums 上维护一个窗口 [left, right)使窗口内元素满足 condition。 返回满足条件的最短/最长窗口长度。 left 0 result 0 # 根据题目改成 float(inf) 或 0 window_state {} # 窗口内的统计信息如字符计数、和等 for right in range(len(nums)): # 1. 右边界进入窗口更新 window_state # update(window_state, nums[right]) while not condition(window_state): # 2. 条件不满足左边界收缩 # remove(window_state, nums[left]) left 1 # 3. 此时窗口满足条件更新答案 # result max(result, right - left 1) return result这个框架的注释部分需要根据题目填充。关键点是while循环的条件是「窗口不满足条件」而不是「窗口满足条件」。很多人在这一步写反导致窗口无限扩张或收缩过度。另外window_state的更新和移除必须对称进入时加什么离开时就减什么。3.3 回溯模板排列、组合、子集的统一骨架回溯的题目看起来五花八门但骨架高度统一。核心是「做选择 → 递归 → 撤销选择」三步。下面是一个通用回溯模板def backtrack(nums, path, result, used): 通用回溯骨架。 nums: 输入数组 path: 当前路径 result: 结果集 used: 标记数组记录哪些元素已被使用 # 终止条件根据题目决定比如 len(path) len(nums) if len(path) len(nums): result.append(path[:]) # 注意拷贝不能直接 append(path) return for i in range(len(nums)): # 剪枝条件根据题目决定 if used[i]: continue # 做选择 used[i] True path.append(nums[i]) # 递归 backtrack(nums, path, result, used) # 撤销选择 path.pop() used[i] False这个模板能解决全排列问题。如果换成组合问题如「组合总和」需要引入start参数避免重复def backtrack_combination(nums, target, start, path, result): 组合问题回溯模板。 start: 本轮搜索的起始下标保证组合不重复。 if target 0: result.append(path[:]) return if target 0: return for i in range(start, len(nums)): # 剪枝如果 nums 已排序且 nums[i] target后面的更大直接 break if nums[i] target: break path.append(nums[i]) backtrack_combination(nums, target - nums[i], i, path, result) # 注意是 i 不是 i1 path.pop()组合模板与排列模板的关键区别在start参数和递归时的下标传递。排列用used数组标记组合用start控制搜索起点。如果允许重复使用元素递归传i不允许重复传i1。这个细节是回溯题最容易混淆的地方建议在模板注释里写清楚。4. 动态规划与图论模板状态定义、转移方程与遍历顺序4.1 动态规划从「爬楼梯」到「背包」的状态设计动态规划的难点不在代码而在状态定义。模板能帮你固定代码结构但状态定义需要你自己想。先看最基础的线性 DP 模板def linear_dp(n): 线性 DP 模板以爬楼梯为例。 dp[i] 表示到达第 i 阶的方法数。 转移方程dp[i] dp[i-1] dp[i-2] if n 2: return n dp [0] * (n 1) dp[1] 1 dp[2] 2 for i in range(3, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]这个模板可以优化空间到 O(1)但初学时建议先写完整数组确认转移方程正确后再优化。空间优化的版本容易在「滚动变量更新顺序」上出错比如prev, curr curr, prev curr这种写法如果顺序写反就会得到错误结果。背包问题是 DP 的另一个高频分支。01 背包的模板如下def knapsack_01(weights, values, capacity): 01 背包模板。 dp[j] 表示容量为 j 时能装的最大价值。 外层遍历物品内层逆序遍历容量。 dp [0] * (capacity 1) for i in range(len(weights)): for j in range(capacity, weights[i] - 1, -1): # 逆序 dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]内层循环必须逆序这是 01 背包的核心。如果正序就变成了完全背包每个物品可以用无限次。这个区别在面试中经常被追问建议在模板注释里用感叹号标出来。完全背包的模板只需要把内层循环改成正序def knapsack_complete(weights, values, capacity): 完全背包模板。 与 01 背包的唯一区别内层循环正序。 dp [0] * (capacity 1) for i in range(len(weights)): for j in range(weights[i], capacity 1): # 正序 dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]4.2 并查集路径压缩与按秩合并的完整实现并查集用于处理连通性问题模板非常固定。下面是一个带路径压缩和按秩合并的完整实现class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n # 秩用于按秩合并 self.count 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]: root_x, root_y root_y, root_x self.parent[root_y] root_x if self.rank[root_x] self.rank[root_y]: self.rank[root_x] 1 self.count - 1 return True def connected(self, x, y): return self.find(x) self.find(y)路径压缩的递归写法简洁但可能栈溢出数据量大时建议改成迭代def find_iterative(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并查集的坑主要在union的返回值上。有些题目需要判断「这条边是否连接了两个不同的连通分量」此时union返回False表示已经在同一分量这条边是冗余的。这个返回值在「冗余连接」类题目中直接决定答案。4.3 BFS 与 DFS网格遍历的两种写法与选择依据网格遍历是图论的基础BFS 和 DFS 都能做但适用场景不同。BFS 适合找最短路径DFS 适合找所有路径或连通块。先看 BFS 模板from collections import deque def bfs_grid(grid, start, target): 网格 BFS 模板找从 start 到 target 的最短步数。 grid: 二维数组0 表示可走1 表示障碍。 rows, cols len(grid), len(grid[0]) queue deque([(start[0], start[1], 0)]) # (行, 列, 步数) visited {(start[0], start[1])} directions [(0, 1), (0, -1), (1, 0), (-1, 0)] while queue: r, c, steps queue.popleft() if (r, c) target: return steps for dr, dc in directions: nr, nc r dr, c dc if 0 nr rows and 0 nc cols and grid[nr][nc] 0 and (nr, nc) not in visited: visited.add((nr, nc)) queue.append((nr, nc, steps 1)) return -1BFS 的关键是「入队时标记 visited」而不是「出队时标记」。如果出队时才标记同一个节点可能被多次入队导致超时或重复计算。这个细节在网格题中非常关键。DFS 模板则用递归或栈实现def dfs_grid(grid, r, c, visited): 网格 DFS 模板用于遍历连通块。 rows, cols len(grid), len(grid[0]) if r 0 or r rows or c 0 or c cols: return if grid[r][c] 1 or (r, c) in visited: return visited.add((r, c)) # 处理当前节点 for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: dfs_grid(grid, r dr, c dc, visited)DFS 的坑在于递归深度。网格最大可能有 10^5 个节点Python 默认递归深度 1000 会直接报RecursionError。解决办法是sys.setrecursionlimit(1000000)或者改用栈模拟递归。我一般会在模板文件开头统一设置递归深度避免每道题都忘记。5. 避坑与排查模板用错时的 5 个典型症状5.1 二分死循环lo和hi更新不对称现象程序卡在 while 循环里不退出或者提交后超时。原因lo mid和hi mid同时出现且mid取整方向导致区间不收缩。比如mid (lo hi) // 2时如果lo mid当hi lo 1时mid lo区间不变死循环。解决统一用lo mid 1和hi mid - 1或者用mid (lo hi 1) // 2配合lo mid。关键是保证每次迭代区间长度至少减少 1。我的习惯是永远用lo mid 1和hi mid - 1配合while lo hi这样不会死循环。5.2 回溯结果重复忘记去重或start参数用错现象结果集中出现重复的组合或排列。原因组合问题中递归传了下标i而不是i1导致同一元素被重复使用或者数组有重复元素但没有排序去重。解决组合问题先排序然后在 for 循环中加if i start and nums[i] nums[i-1]: continue。排列问题用used数组同时排序后加if i 0 and nums[i] nums[i-1] and not used[i-1]: continue。这个条件的意思是「如果前一个相同元素没被使用说明当前是重复分支跳过」。5.3 滑动窗口越界left收缩过度或不足现象答案偏小窗口收缩过度或超时窗口不收缩。原因while条件写反或者left更新后没有重新检查条件。解决记住「窗口不满足条件时收缩」这个原则。写完后用一个小例子手动模拟比如nums [1,2,3]condition是「窗口和 3」手动走一遍看left和right的变化。如果模拟结果和预期不符检查while条件。5.4 并查集find栈溢出递归深度过大现象数据量大时RecursionError。原因路径压缩的递归写法在树退化成链时递归深度等于节点数。解决改用迭代版find或者设置sys.setrecursionlimit。但设置递归深度只是缓解根本办法是迭代。我在模板库里默认用迭代版递归版只作为备选。5.5 DP 空间优化后答案错误滚动变量更新顺序现象完整数组版答案正确空间优化版答案错误。原因滚动变量更新时新值覆盖了旧值导致后续计算使用了错误的数据。解决在更新前先用临时变量保存旧值或者调整更新顺序。比如 01 背包的空间优化版内层必须逆序就是为了避免同一物品被多次使用。如果正序dp[j]会用到已经更新过的dp[j - weights[i]]相当于完全背包。6. 模板的组合使用与验证从刷题到面试的最后一公里模板单独会写只是第一步真正拉开差距的是组合使用和快速验证。一道中等难度的题往往需要两个模板拼接比如「二分 贪心」「BFS 状态压缩」「DP 前缀和」。这时候模板的接口统一性就体现出价值了lower_bound返回下标可以直接作为另一个函数的输入并查集的union返回布尔值可以直接用于判断冗余边。我自己的验证习惯是「三组测试 一个暴力对拍」。三组测试分别是最小规模n0 或 n1、常规规模、边界规模全部相同元素、已排序、逆序。暴力对拍则是写一个 O(n^2) 或 O(2^n) 的暴力解法用随机数据跑 1000 次对比两个解法的输出。这个方法在周赛里救过我很多次尤其是 DP 题状态转移写错时暴力对拍能立刻定位。下面是一个对拍脚本的骨架可以直接套用import random def brute_force(nums): 暴力解法根据题目替换。 # 示例求最大子数组和 best float(-inf) for i in range(len(nums)): s 0 for j in range(i, len(nums)): s nums[j] best max(best, s) return best def fast_solution(nums): 模板解法根据题目替换。 # 示例Kadane 算法 best cur nums[0] for x in nums[1:]: cur max(x, cur x) best max(best, cur) return best def stress_test(): for _ in range(1000): n random.randint(1, 20) nums [random.randint(-10, 10) for _ in range(n)] if brute_force(nums) ! fast_solution(nums): print(Found mismatch:, nums) print(brute:, brute_force(nums), fast:, fast_solution(nums)) return print(All tests passed.) stress_test()这个脚本的关键是random.randint的范围要覆盖负数、零和正数否则可能漏掉边界情况。另外对拍次数建议至少 1000 次太少可能碰不到反例。最后一个技巧是关于模板的「版本管理」。我会把每个模板单独存成一个.py文件文件名就是模板名比如lower_bound.py、union_find.py。文件头部用注释写清楚适用场景、时间复杂度和易错点。刷题时直接from templates import lower_bound不重复造轮子。面试前一周我会把这些模板文件过一遍重点看注释里的易错点而不是重新推导。这个习惯让我在面试中写二分和并查集时几乎不再出错省下的时间可以用来思考题目本身的难点。希望帮到你。本文还有配套的精品资源点击获取