简介这是一份面向LeetCode与OJ刷题者的Python3算法模板合集定位为面试与日常练习的通用代码参考帮助读者摆脱重复造轮子的困境。作者系统整理了常用数据结构与算法的通用模板并附上典型例题、题号与简要说明便于对照理解与迁移使用。资源包共71个文件以46个py模板脚本为主体覆盖数组、链表、栈、队列、堆、字典、并查集、字典树、二叉树等数据结构以及二分查找、双指针、滑动窗口、回溯、分治、动态规划、BFS、DFS、位运算、排序等算法模块另有7个md笔记、11张png与2张jpg图示、2份pdf速查资料及license等辅助文件压缩包约951KB结构清晰便于按模块检索。目前已有362人学习。读者可借此快速掌握各算法的标准写法与最佳实践配合示例与注释理解边界处理适合面试冲刺与日常刷题查漏补缺。1. 算法模板到底该背哪几套从 leetcode 和 oj 的差异说起刷 leetcode 和打 OJ 是两条不同的肌肉记忆路线。leetcode 偏重单函数补全输入输出都给你封装好了你只需要把Solution类里的方法填上而 OJ 往往要求你自己处理标准输入输出、多组测试用例、甚至手写快排和并查集。很多人 leetcode 刷到 500 题一到 OJ 上机就翻车原因不是算法不会而是模板不熟——边界处理、输入解析、递归深度这些脏活没人替你兜底。Python 算法模板的价值就在这里它把二分、滑动窗口、并查集、线段树、图论遍历这些高频结构固化成可复用的代码骨架让你在 leetcode 和 OJ 之间切换时不用重新推导。这套模板适合两类人一是准备机试和笔试的在校生二是工作中偶尔要写算法脚本的工程师。下面我按自己常用的顺序把模板拆成能直接抄的代码块和参数说明。2. 二分与滑动窗口两个最容易写挂的模板怎么固化2.1 整数二分的三种写法与死循环排查二分看着简单但left mid还是left mid 1while left right还是while left right组合起来有七八种变体写错一个就是死循环。我一般只保留两套一套找「第一个满足条件的下标」一套找「最后一个满足条件的下标」。下面这套是左闭右开区间写法好处是边界统一不用纠结 mid 加不加一。def lower_bound(nums, target): # 返回第一个 target 的下标找不到返回 len(nums) left, right 0, len(nums) # 左闭右开 while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid return left def upper_bound(nums, target): # 返回第一个 target 的下标 left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid return left逻辑说明lower_bound和upper_bound的区别只在nums[mid] target还是nums[mid] target。参数上nums必须是有序数组target是目标值。调用lower_bound([1,2,2,3], 2)返回 1upper_bound返回 3。死循环排查如果发现程序卡住先检查mid是否可能等于left且right mid导致区间不缩小左闭右开写法天然避免这个问题。注意Python 的//是向下取整所以mid永远偏向左边这也是为什么left mid 1是安全的。2.2 滑动窗口的通用骨架与窗口收缩条件滑动窗口的难点不在代码而在「什么时候收缩左边界」。我见过太多人把while写成if结果窗口该缩的时候没缩答案偏大。下面这个骨架把「扩张右边界」和「收缩左边界」拆成两个独立逻辑你只需要填need和valid的判断。from collections import defaultdict def sliding_window(s, t): need defaultdict(int) for c in t: need[c] 1 window defaultdict(int) left, right 0, 0 valid 0 start, length 0, float(inf) while right len(s): c s[right] right 1 if c in need: window[c] 1 if window[c] need[c]: valid 1 while valid len(need): # 收缩条件 if right - left length: start left length right - left d s[left] left 1 if d in need: if window[d] need[d]: valid - 1 window[d] - 1 return s[start:startlength] if length ! float(inf) else 逻辑说明need记录目标字符频次window记录当前窗口频次valid表示有多少字符已经满足频次要求。参数上s是源字符串t是目标字符串。收缩条件是valid len(need)意味着当前窗口已经覆盖了t的所有字符。注意window[d] need[d]的判断必须在window[d] - 1之前否则valid会少减。这个模板直接套「最小覆盖子串」改几行就能用于「最长无重复子串」和「找到字符串中所有字母异位词」。3. 并查集与图论遍历OJ 上机最常考的两类结构3.1 并查集的路径压缩与按秩合并并查集在 OJ 里出现频率极高尤其是「连通块数量」「冗余连接」这类题。很多人只写路径压缩不写按秩合并结果在极端数据下退化成链表。下面这套同时做了路径压缩和按秩合并find的均摊复杂度接近 O(1)。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [1] * 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 self.rank[root_x] self.rank[root_y] self.count - 1 return True逻辑说明parent记录每个节点的父节点rank记录树的高度或大小count维护连通块数量。参数上n是节点总数节点编号从 0 到 n-1。union返回False表示两个节点已经在同一集合可以用来检测环。注意递归版find在 Python 里默认递归深度只有 1000如果节点数超过 900建议改成迭代写法或者sys.setrecursionlimit(100000)。我一般会在 OJ 代码开头直接设递归深度省得后面翻车。3.2 BFS 与 DFS 的迭代写法与访问标记时机图论遍历的坑集中在「访问标记什么时候打」。BFS 如果入队时不标记同一个节点可能被重复入队队列爆炸DFS 如果递归太深直接栈溢出。下面这套 BFS 用visited在入队时标记DFS 用显式栈模拟递归避免深度限制。from collections import deque def bfs(graph, start): visited {start} queue deque([start]) order [] while queue: node queue.popleft() order.append(node) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) # 入队时标记 queue.append(neighbor) return order def dfs_iterative(graph, start): visited set() stack [start] order [] while stack: node stack.pop() if node in visited: continue visited.add(node) # 出栈时标记 order.append(node) for neighbor in graph[node]: if neighbor not in visited: stack.append(neighbor) return order逻辑说明graph是邻接表通常用defaultdict(list)构建。BFS 的visited在入队时添加保证每个节点只入队一次DFS 迭代版在出栈时标记因为栈里可能有重复节点。参数上start是起始节点。注意DFS 迭代版的顺序和递归版相反因为栈是后进先出如果要求顺序一致可以把邻居逆序压栈。这个细节在「按字典序输出路径」的题里会直接影响答案。4. 动态规划与线段树从记忆化搜索到区间查询4.1 记忆化搜索的 lru_cache 与手动备忘录对比动态规划入门最自然的是记忆化搜索Python 的functools.lru_cache能省掉手写备忘录但它有坑参数必须是可哈希的而且缓存不会自动清理。我一般先用lru_cache快速验证思路再改成手动备忘录或递推避免 OJ 上因为缓存过大被卡内存。from functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 2: return n return fib(n-1) fib(n-2) def fib_dp(n): if n 2: return n dp [0] * (n 1) dp[1] 1 for i in range(2, n 1): dp[i] dp[i-1] dp[i-2] return dp[n]逻辑说明lru_cache(maxsizeNone)表示不限制缓存大小适合状态数有限的场景。参数上n是输入规模。注意lru_cache对列表、字典等不可哈希参数会直接报错这时候必须手动用dict做备忘录把参数转成元组。另外递归深度超过 1000 时lru_cache也救不了栈溢出还是得改递推。我一般会在 OJ 上先交一版lru_cache如果 TLE 或 MLE再改成滚动数组优化。4.2 线段树的数组实现与区间更新懒标记线段树在 OJ 里属于「会写就多拿 20 分」的结构但代码量大容易写挂。下面这套用数组实现支持区间求和和区间加法更新懒标记在push_down里下传。class SegmentTree: def __init__(self, nums): self.n len(nums) self.tree [0] * (4 * self.n) self.lazy [0] * (4 * self.n) self._build(nums, 1, 0, self.n - 1) def _build(self, nums, node, l, r): if l r: self.tree[node] nums[l] return mid (l r) // 2 self._build(nums, node * 2, l, mid) self._build(nums, node * 2 1, mid 1, r) self.tree[node] self.tree[node * 2] self.tree[node * 2 1] def _push_down(self, node, l, r): if self.lazy[node] ! 0: mid (l r) // 2 left, right node * 2, node * 2 1 self.tree[left] self.lazy[node] * (mid - l 1) self.tree[right] self.lazy[node] * (r - mid) self.lazy[left] self.lazy[node] self.lazy[right] self.lazy[node] self.lazy[node] 0 def update(self, node, l, r, ql, qr, val): if ql l and r qr: self.tree[node] val * (r - l 1) self.lazy[node] val return self._push_down(node, l, r) mid (l r) // 2 if ql mid: self.update(node * 2, l, mid, ql, qr, val) if qr mid: self.update(node * 2 1, mid 1, r, ql, qr, val) self.tree[node] self.tree[node * 2] self.tree[node * 2 1] def query(self, node, l, r, ql, qr): if ql l and r qr: return self.tree[node] self._push_down(node, l, r) mid (l r) // 2 res 0 if ql mid: res self.query(node * 2, l, mid, ql, qr) if qr mid: res self.query(node * 2 1, mid 1, r, ql, qr) return res逻辑说明tree存区间和lazy存待下传的加法标记。参数上nums是初始数组node是当前节点编号l和r是当前区间ql和qr是查询区间。注意数组大小要开4 * n否则递归建树时会越界。_push_down必须在递归左右子树之前调用否则懒标记会丢失。这套模板直接套「区间加法与区间求和」改一下合并逻辑就能用于区间最值。5. 避坑与排查模板在 leetcode 和 OJ 上翻车的五个瞬间5.1 递归深度超限导致 RE现象本地跑得好好的一交 OJ 就报RecursionError或直接 RE。原因Python 默认递归深度 1000DFS 或递归版线段树在节点数超过 900 时就会炸。解决在代码开头加import sys; sys.setrecursionlimit(1000000)或者把递归改成迭代。我一般会在 OJ 模板里默认加上这行省得每次手动调。5.2 输入解析没处理多组测试用例现象leetcode 上单组输入没问题OJ 上多组测试用例只过了第一组。原因OJ 的输入可能是while True循环直到 EOF 才结束而 leetcode 只调用一次函数。解决用sys.stdin.read().split()一次性读入所有 token或者用while True: try: ... except EOFError: break。注意有些 OJ 会在每组数据后输出空行split()能自动忽略空白字符比input()逐行读更稳。5.3 整数溢出与浮点精度现象Python 理论上没有整数溢出但 OJ 的 C 标程可能用int存结果你的 Python 答案和标程对不上。原因标程溢出后结果错误而你的 Python 结果正确但 OJ 只认标程输出。解决如果发现答案和预期差一个负数先检查题目是否要求取模或者标程是否用了long long。浮点精度问题更常见比较浮点数时用abs(a - b) 1e-9不要用。5.4 并查集路径压缩写成非递归但漏了秩合并现象小数据没问题大数据 TLE。原因只做路径压缩不做按秩合并树高在极端情况下仍然是 O(log n) 到 O(n) 之间均摊复杂度退化。解决加上rank数组合并时小树挂大树。注意rank更新只在根节点上做不要在每个节点上更新。5.5 滑动窗口收缩条件写成 if 而不是 while现象答案比预期大或者窗口长度不对。原因if只收缩一次但窗口可能需要连续收缩多次才能满足条件。解决把if改成while确保窗口在满足条件时持续收缩。这个坑我在「最小覆盖子串」上踩过至少三次血泪经验就是只要涉及窗口收缩无脑用while。6. 把模板变成自己的从抄代码到改代码的进阶路径模板抄多了容易产生依赖真正上机时遇到变形题还是不会。我的做法是每套模板只记「骨架」和「三个关键参数」剩下的靠推导。比如二分只记左闭右开和mid (left right) // 2滑动窗口只记valid和while收缩并查集只记find和union的返回值含义。然后拿 leetcode 上的题做「模板变形训练」同一套滑动窗口模板分别套「最小覆盖子串」「最长无重复子串」「字母异位词」观察哪些行改了、哪些行没改。改得多了你会发现模板的边界其实就那几个区间开闭、标记时机、收缩条件。验证模板是否真正掌握我一般用「三遍法」第一遍照着模板写第二遍关掉模板默写第三遍把题目条件改掉比如把求和改成求最值再写。如果第三遍还能写出来说明这套模板已经内化了。另外建议把常用模板整理成一个templates.py文件用if __name__ __main__:写几个测试用例每次上机前跑一遍确认环境没问题。这个习惯帮我省了很多「明明本地能跑OJ 上就是 RE」的后悔药。最后说一个我自己的教训不要追求模板的「万能」没有哪套模板能覆盖所有题。线段树能解决的问题树状数组也能解决但树状数组代码短一半并查集能解决的问题DFS 染色也能解决但并查集更适合动态连通。选模板的标准不是「高级」而是「写挂的概率低」。我现在的习惯是能用数组不用树能用迭代不用递归能用内置库不用手写。希望帮到你。本文还有配套的精品资源点击获取