【Python LeetCode Patterns】刷力扣，15 个学习模式总结

15 Patterns

1. 前缀和（Prefix Sum）—— 查询子数组中元素和

如果要 查询数组 nums 中从下标 i 到 j 的数组元素和，那么大量这种查询，应该怎么做呢？

核心思想：

• 构建一个长度为 len(nums)+1 的数组 prefix_sum，假设左边界 prefix_sum[0] = 0；
• 这样 prefix_sum 下标比 num 数组大 1，所以：prefix_sum[i+1] = nums[0] + nums[1] + ... + nums[i]；
• 任何区间 [l, r] 的和就可以通过：sum = prefix_sum[r+1] - prefix_sum[l] 快速得到！

• 时间复杂度：构建 prefix_sum 的复杂度是 O(n)，之后 每次查询都是 O(1)。
• 空间复杂度：可以使用 nums 数组本身构建前缀和，就不需要额外空间了。

303. 区域和检索 - 数组不可变

class NumArray:def __init__(self, nums: List[int]):# 初始化前缀和数组，长度为 len(nums) + 1，前缀和[0] = 0self.prefix_sum = [0] * (len(nums) + 1)for i in range(len(nums)):self.prefix_sum[i + 1] = self.prefix_sum[i] + nums[i]def sumRange(self, left: int, right: int) -> int:return self.prefix_sum[right + 1] - self.prefix_sum[left]  # 区间和# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)

304. 二维区域和检索 - 矩阵不可变

构建一个 前缀和矩阵（sum_matrix） 来快速 查询任意子矩形区域的总和。

class NumMatrix:def __init__(self, matrix: List[List[int]]):rows, cols = len(matrix), len(matrix[0])# 创建前缀和矩阵，注意多出一行一列，初始化为0self.prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]# 构建二维前缀和矩阵for r in range(rows):for c in range(cols):self.prefix_sum[r + 1][c + 1] = (matrix[r][c]+ self.prefix_sum[r][c + 1]+ self.prefix_sum[r + 1][c]- self.prefix_sum[r][c])def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:# 使用二维前缀和公式求子矩阵和return (self.prefix_sum[row2 + 1][col2 + 1]- self.prefix_sum[row1][col2 + 1]- self.prefix_sum[row2 + 1][col1]+ self.prefix_sum[row1][col1])# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)

2. 双指针（Two Pointers）—— 移向彼此或远离彼此

时间复杂度：

刷题参考：面试经典 150 题——双指针

3. 滑动窗口（Sliding Window）—— 找到满足特定条件的子数组或子字符串

时间复杂度： $\to$

刷题参考：面试经典 150 题——滑动窗口

4. 快慢指针（Fast and Slow Pointers）—— 快甩慢一圈时相遇

刷题参考：面试经典 150 题——快慢指针

5. 原地翻转链表（Linked List In-place Reversal）—— 不使用额外空间重新排列链表

核心思想： 使用三个指针，pre、cur 和 next。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:prev = Nonecurrent = headwhile current is not None:next = current.nextcurrent.next = prevprev = currentcurrent = nextreturn prev

6. 单调栈（Monotonic Stack）—— 查找数组中下一个更 × 的元素

栈（stack），先进后出，符合某些问题的特点，比如说函数调用栈。单调栈 实际上就是栈，只是利用了一些巧妙的逻辑，使得 每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。

单调栈用于处理一类典型的问题，比如 「下一个更大元素」，「上一个更小元素」 等。

时间复杂度： $\to$ O(n)

496. 下一个更大元素 I

class Solution:def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:n1, n2 = len(nums1), len(nums2)greater = [-1] * 10001stack = [10**4+1]for i in range(n2-1, -1, -1):while nums2[i] >= stack[-1]:stack.pop()if stack[-1] != 10**4 + 1:greater[nums2[i]] = stack[-1]stack.append(nums2[i])ans = [-1] * n1for i in range(n1):ans[i] = greater[nums1[i]]return ans

503. 下一个更大元素 II

from collections import defaultdict
class Solution:def nextGreaterElements(self, nums: List[int]) -> List[int]:n = len(nums)max_index = nums.index(max(nums))ans = [-1] * nstack = [(max_index, nums[max_index])]for i in range(max_index + 1, n):while nums[i] > stack[-1][1]:ans[stack[-1][0]] = nums[i]stack.pop()stack.append((i, nums[i]))for i in range(0, max_index+1):while nums[i] > stack[-1][1]:ans[stack[-1][0]] = nums[i]stack.pop()stack.append((i, nums[i]))return ans

7. 前 K 个元素（Top K Elements）—— 查找 K 个最 × 的元素

时间复杂度： O(n logn) $\to$ O(n log K)

8. 重叠间隔（Overlapping Intervals）—— 可能重叠的间隔或范围

9. 修改二进制搜索（Modified Binary Search）——

10. 二叉树遍历

11. 深度优先搜索

12. 广度优先搜索

13. 矩阵遍历

14. 回溯（Backtracking）

回溯算法的核心在于通过不断尝试所有可能的选择，然后在发现当前路径无法达到目标时“回退”，换一种选择继续探索。

“试错—撤销—重新尝试” 的过程就是回溯算法的精髓。

回溯算法说白了就是穷举法。不过回溯算法使用剪枝函数，剪去一些不可能到达 最终状态（即答案状态）的节点，从而减少状态空间树节点的生成。

参考：回溯总结

def backtrack(path, choices):if is_solution(path):   # 终止条件return Truefor choice in choices:    # 遍历当前状态下所有的选择if is_valid(choice, path):path.append(choice)  # 1. 做出选择，将 choice 加入路径中updated_choices = update_choices(choices, choice)if backtrack(path, updated_choices):　　　# 2. 递归调用，继续在剩余选择中搜索return Truepath.pop()  # 3. 回溯：撤销选择return False  # 所有选择均尝试过后未能得到解决方案

473. 火柴拼正方形

• 状态定义：用一个数组 sides 来表示当前四条边的长度。回溯函数的状态可以用当前正在放置的火柴棒的索引 index 以及四条边当前的累加长度来表示。

• 递归的基本思想

  • 选择过程：对每根火柴棒，我们有四个选择——将它放到正方形的四条边中的任意一条，只要该边放上后不超过目标边长。
  • 递归调用：放置火柴棒后，递归处理下一根火柴棒。如果某条路径最终使得所有火柴棒都被放置，并且每条边的长度都正好等于目标边长，那么说明找到了一种解法。

• 剪枝（回退）

  • 不符合条件时回退：如果当前某个选择导致某条边的长度超过目标边长，则直接放弃该选择（剪枝），不会继续递归下去。
  • 撤销选择：在递归返回后，将之前放置的火柴棒“撤销”，使状态回到上一步，从而尝试其他可能的放置方式。

• 终止条件：当所有火柴棒都尝试完毕（即 index == len(matchsticks)），检查四条边是否都达到目标边长。如果是，返回 True；否则返回 False。

优化技巧：

• 排序：将火柴棒按长度降序排序，可以让较大的火柴棒先被尝试，能更快发现不可能的路径，从而提前剪枝，减少不必要的递归计算。
• 重复状态避免：有时候还可以进一步利用对称性等手段避免重复计算，不过在这个问题中，降序排序已经是一个有效的剪枝策略。

class Solution:def makesquare(self, matchsticks: List[int]) -> bool:total = sum(matchsticks)if total % 4 != 0:   # 火柴长度和不是 4 的倍数return Falseside = total // 4  # 正方形边长matchsticks.sort(reverse=True)sides = [0] * 4def backtrace(idx):# 终止条件：所有火柴都已使用，检查是否都等于边长if idx == len(matchsticks):return sides[0] == sides[1] == sides[2] == sides[3] == side# 遍历所有边，可以将这根火柴放入哪个边for i in range(4):if sides[i] + matchsticks[idx] <= side:sides[i] += matchsticks[idx]  # 做选择：将当前火柴放入该边if backtrace(idx + 1):return Truesides[i] -= matchsticks[idx]  # 回溯return Falsereturn backtrace(0)   

2305. 公平分发饼干（剪枝）

类似火柴拼正方形，

class Solution:def distributeCookies(self, cookies: List[int], k: int) -> int:n = len(cookies)childs = [0] * kans = 800001def backtrace(idx):nonlocal ans# 终止条件，分发完零食了if idx == n:unfair = max(childs)ans = min(ans, unfair)return # 遍历所有选择for i in range(k):childs[i] += cookies[idx]  # 做选择：当前零食发给第 i 个孩子backtrace(idx + 1)  # 递归，继续分发下一包零食childs[i] -= cookies[idx]  # 撤销选择，回溯return backtrace(0)return ans

但是会超时，画出回溯树查看：

从上面的图可以发现，第一个零食包不管给哪个小朋友，所开启的回溯树都一样（因为本题不要求顺序），所以首个零食包只要给第一个小朋友就行了，这样的回溯树只有一个根节点（一个回溯树），否则有 $k$ 个回溯树。

一开始对数组进行排序，先发放饼干较多的包，这样可以减少平均回溯深度。

class Solution:def distributeCookies(self, cookies: List[int], k: int) -> int:n = len(cookies)cookies.sort(reverse=True)  # 从大到小排序，便于剪枝childs = [0] * kans = 800001def backtrace(idx):nonlocal ans  # ans 记录最小不公平程度，可视作全局变量# 终止条件，分发完零食了if idx == n:unfair = max(childs)ans = min(ans, unfair)return # 遍历所有选择for i in range(k):if childs[i] + cookies[idx] >= ans:  # 剪枝：比 ans 还大的不公平程度就不用看了continueif i > 0 and childs[i] == childs[i-1]:  # 剪枝：当前零食包分给哪个孩子都一样，已经分给前一个孩子了就不要再重复给当前孩子了continuechilds[i] += cookies[idx]  # 做选择：当前零食发给第 i 个孩子backtrace(idx + 1)  # 递归，继续分发下一包零食childs[i] -= cookies[idx]  # 撤销选择，回溯return backtrace(0)return ans

78. 子集

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:subset = []sub = []def backtrace(nums):subset.append(sub.copy())  # NOTE: sub.copy()# 终止条件if len(nums) == 0:return # 遍历选择for i in range(len(nums)):sub.append(nums[i])  # 做选择backtrace(nums[i+1:])  # 递归sub.pop()  # 撤销选择，回溯return backtrace(nums)return subset

15. 动态规划