刷题党必备：用Python实现《代码随想录》12大算法模板（含二叉树/回溯/DP）

Python算法实战12大核心模板精解与LeetCode百题斩在技术面试中算法能力往往是区分普通开发者与顶尖工程师的关键指标。无论是硅谷科技巨头还是国内一线互联网公司算法题已成为筛选候选人的标配环节。本文将系统性地介绍12类高频算法模板结合Python实现与LeetCode经典题目帮助读者构建完整的算法知识体系。1. 数组与双指针技巧数组是最基础的数据结构但其中蕴含的技巧却极为丰富。双指针法是处理数组问题的利器能够将许多O(n²)复杂度的问题优化到O(n)。二分查找模板LeetCode 704def binary_search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 # 避免溢出 if nums[mid] target: left mid 1 elif nums[mid] target: right mid - 1 else: return mid return -1关键点循环条件left right确保区间有效性mid计算方式防止整数溢出滑动窗口模板LeetCode 209def min_subarray_len(target, nums): left total 0 min_len float(inf) for right in range(len(nums)): total nums[right] while total target: min_len min(min_len, right-left1) total - nums[left] left 1 return min_len if min_len ! float(inf) else 0常见变种问题有序数组平方LeetCode 977移除元素LeetCode 27水果成篮LeetCode 9042. 链表操作精要链表问题常考验指针操作的精准性以下是必须掌握的几种模式虚拟头节点技巧def remove_elements(head, val): dummy ListNode(nexthead) # 创建虚拟节点 curr dummy while curr.next: if curr.next.val val: curr.next curr.next.next else: curr curr.next return dummy.next # 返回真正的头节点快慢指针应用场景快指针速度慢指针速度典型问题找中点每次2步每次1步链表归并排序检测环每次2步每次1步环形链表II倒数第N个先走N步然后同步删除倒数节点链表反转模板def reverse_list(head): prev, curr None, head while curr: next_node curr.next # 临时保存 curr.next prev # 反转指向 prev curr # 移动指针 curr next_node return prev # 新头节点3. 二叉树遍历体系二叉树算法本质上是遍历框架的变种掌握以下三种遍历方式是基础递归遍历模板def traverse(root): if not root: return # 前序位置 traverse(root.left) # 中序位置 traverse(root.right) # 后序位置迭代遍历实现# 前序遍历栈实现 def preorder(root): stack, res [root], [] while stack: node stack.pop() if node: res.append(node.val) stack.append(node.right) # 先右后左 stack.append(node.left) return res层序遍历模板def level_order(root): from collections import deque if not root: return [] queue deque([root]) res [] while queue: level [] for _ in range(len(queue)): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return res二叉树问题解题框架是否可以通过遍历得到答案→ 使用遍历框架是否可以定义递归子问题→ 使用分解问题思路是否需要额外信息传递→ 使用回溯思想4. 回溯算法框架回溯算法本质是决策树的遍历过程需要明确三个要素路径已经做出的选择选择列表当前可以做的选择结束条件到达决策树底层的条件全排列模板LeetCode 46def permute(nums): res [] used [False] * len(nums) def backtrack(path): if len(path) len(nums): res.append(path.copy()) return for i in range(len(nums)): if not used[i]: used[i] True path.append(nums[i]) backtrack(path) path.pop() used[i] False backtrack([]) return res组合总和模板LeetCode 39def combination_sum(candidates, target): res [] def backtrack(start, path, remain): if remain 0: res.append(path.copy()) return if remain 0: return for i in range(start, len(candidates)): path.append(candidates[i]) backtrack(i, path, remain-candidates[i]) # 可重复使用 path.pop() backtrack(0, [], target) return res剪枝优化技巧排序数组提前终止循环使用start参数避免重复组合记忆化减少重复计算5. 动态规划核心框架DP问题的共同特征重叠子问题最优子结构状态转移方程解题四步法定义dp数组含义确定初始条件建立状态转移方程考虑空间优化经典问题实现斐波那契数列LeetCode 509def fib(n): if n 2: return n dp [0] * (n1) dp[1] 1 for i in range(2, n1): dp[i] dp[i-1] dp[i-2] return dp[n]零钱兑换LeetCode 322def coin_change(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for coin in coins: for i in range(coin, amount1): dp[i] min(dp[i], dp[i-coin]1) return dp[amount] if dp[amount] ! float(inf) else -1股票买卖问题LeetCode 121def max_profit(prices): min_price float(inf) max_profit 0 for price in prices: min_price min(min_price, price) max_profit max(max_profit, price - min_price) return max_profit6. 图论算法模板图的表示方法对比方式优点缺点适用场景邻接矩阵查询快空间O(V²)稠密图邻接表空间省查询较慢稀疏图边列表简单查询效率低特定算法DFS遍历模板def dfs(graph, start): visited set() stack [start] while stack: node stack.pop() if node not in visited: visited.add(node) for neighbor in graph[node]: if neighbor not in visited: stack.append(neighbor) return visitedBFS遍历模板from collections import deque def bfs(graph, start): visited set([start]) queue deque([start]) while queue: node queue.popleft() for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return visited拓扑排序LeetCode 207def can_finish(num_courses, prerequisites): from collections import defaultdict, deque graph defaultdict(list) in_degree [0] * num_courses for dest, src in prerequisites: graph[src].append(dest) in_degree[dest] 1 queue deque([i for i in range(num_courses) if in_degree[i] 0]) count 0 while queue: node queue.popleft() count 1 for neighbor in graph[node]: in_degree[neighbor] - 1 if in_degree[neighbor] 0: queue.append(neighbor) return count num_courses7. 高级数据结构应用并查集模板class UnionFind: def __init__(self, size): self.parent list(range(size)) self.rank [0] * size 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): x_root self.find(x) y_root self.find(y) if x_root y_root: return # 按秩合并 if self.rank[x_root] self.rank[y_root]: self.parent[x_root] y_root else: self.parent[y_root] x_root if self.rank[x_root] self.rank[y_root]: self.rank[x_root] 1前缀树实现LeetCode 208class TrieNode: def __init__(self): self.children {} self.is_end False class Trie: def __init__(self): self.root TrieNode() def insert(self, word): node self.root for ch in word: if ch not in node.children: node.children[ch] TrieNode() node node.children[ch] node.is_end True def search(self, word): node self.root for ch in word: if ch not in node.children: return False node node.children[ch] return node.is_end def startsWith(self, prefix): node self.root for ch in prefix: if ch not in node.children: return False node node.children[ch] return True8. 贪心算法实践贪心算法适用场景问题具有最优子结构无后效性能够证明局部最优导致全局最优区间调度问题LeetCode 435def erase_overlap_intervals(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) # 按结束时间排序 count 1 end intervals[0][1] for interval in intervals[1:]: if interval[0] end: # 不重叠 count 1 end interval[1] return len(intervals) - count分糖果问题LeetCode 135def candy(ratings): n len(ratings) candies [1] * n # 从左到右 for i in range(1, n): if ratings[i] ratings[i-1]: candies[i] candies[i-1] 1 # 从右到左 for i in range(n-2, -1, -1): if ratings[i] ratings[i1]: candies[i] max(candies[i], candies[i1]1) return sum(candies)9. 单调栈技巧单调栈适用于求解下一个更大元素类问题维护栈内元素的单调性。每日温度LeetCode 739def daily_temperatures(temperatures): stack [] res [0] * len(temperatures) for i, temp in enumerate(temperatures): while stack and temp temperatures[stack[-1]]: prev stack.pop() res[prev] i - prev stack.append(i) return res柱状图中最大矩形LeetCode 84def largest_rectangle_area(heights): heights [0] heights [0] # 添加哨兵 stack [0] max_area 0 for i in range(1, len(heights)): while heights[i] heights[stack[-1]]: h heights[stack.pop()] w i - stack[-1] - 1 max_area max(max_area, h * w) stack.append(i) return max_area10. 位运算妙用常用位运算技巧n (n-1)消除二进制最后一位1a ^ a 0异或性质~0 n构造n位1的掩码位操作示例# 判断2的幂次LeetCode 231 def is_power_of_two(n): return n 0 and n (n-1) 0 # 汉明重量LeetCode 191 def hamming_weight(n): count 0 while n: n n - 1 count 1 return count # 只出现一次的数字LeetCode 136 def single_number(nums): res 0 for num in nums: res ^ num return res11. 数学思维应用质数判断优化def is_prime(n): if n 2: return False for i in range(2, int(n**0.5)1): if n % i 0: return False return True最大公约数欧几里得算法def gcd(a, b): while b: a, b b, a % b return a快速幂算法LeetCode 50def my_pow(x, n): if n 0: x 1 / x n -n res 1 while n: if n 1: res * x x * x n 1 return res12. 设计类问题模式LRU缓存LeetCode 146from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cache OrderedDict() self.capacity capacity def get(self, key): if key not in self.cache: return -1 self.cache.move_to_end(key) return self.cache[key] def put(self, key, value): if key in self.cache: self.cache.move_to_end(key) self.cache[key] value if len(self.cache) self.capacity: self.cache.popitem(lastFalse)最小栈LeetCode 155class MinStack: def __init__(self): self.stack [] self.min_stack [] def push(self, val): self.stack.append(val) if not self.min_stack or val self.min_stack[-1]: self.min_stack.append(val) def pop(self): if self.stack.pop() self.min_stack[-1]: self.min_stack.pop() def top(self): return self.stack[-1] def getMin(self): return self.min_stack[-1]算法学习路线建议分阶段突破初级阶段掌握基本数据结构操作中级阶段熟练应用经典算法模板高级阶段灵活组合多种解题技巧刻意练习方法同类题目集中训练如一周专攻动态规划每道题至少尝试三种解法定期复习错题本面试准备策略优先掌握Hot 100和剑指Offer题目模拟真实面试环境练习总结自己的解题模板库算法能力的提升没有捷径但科学的方法可以事半功倍。建议每天保持2-3道高质量题目的练习量坚持3个月会有显著提升。在实际编码时要注意变量命名规范和边界条件处理这些细节往往决定面试成败。