LeetCode刷题：8种核心解题模式，从看懂题解到独立AC

从“看懂题解”到“独立 AC”之间你差的只是 8 种模式识别你有没有过这种经历看完一道 LeetCode 的题解觉得每一步都很简单代码也就 20 行逻辑无懈可击可一旦自己面对一道新题大脑就一片空白不知道应该用递归、贪心、动态规划还是建图跑最短路。这不是你不够聪明而是刷题方式出了问题。过去我也有同样的困惑。刷到第 100 题时我发现自己记得的不是“算法思想”而是“某道题的解法”。题目一做变形原来的思路立刻失效。直到后来开始按“解题模式”重新整理题目才意识到一个关键事实LeetCode 考的不是知识点而是模式识别能力。面试官不会考你做没做过这题而是看你能不能把新问题归约成已经熟悉的模型。这篇文章把算法面试中出现频率最高的 8 类题目归纳为 8 种可复用的解题模式并为每种模式提供可直接套用的代码模板以及大量来自真实刷题过程的判断方法和易错点。读完你会发现LeetCode 并不需要你背几百道题只需要你掌握几十种核心模式。真正的门槛从“看题解”变成了“给问题分类”而这一步是最可以通过刻意练习突破的。1. 这篇文章真正要解决的问题1.1 为什么刷题越刷越迷茫假设你正常刷了 150 道 LeetCode常见的状态是能看懂题解但不理解为什么想到这个解法。每次看到题目判断不出该用 BFS 还是 DFS。同样类型的题目换个问法就认不出来。代码能跑通但要么超时要么边界条件处理不对。面试紧张时连熟悉的题目手写都会卡壳。这些现象背后有一个共同原因学习单位选错了。大多数人按“题号”刷题但按题号积累的知识是离散的。你记得“第 79 题是岛屿数量”但下次遇到“被围绕的区域”时却看不出它和岛屿问题共享同一种 flood fill 模式。1.2 模式思维的价值模式思维是把刷题的最小学习单位从“单道题”切换成“一类题”。它不要求你死记硬背代码而是要求你先回答三个问题题目输入是什么形状数组、链表、树、图、字符串题目求解目标是什么查找、计数、最值、是否存在、构造方案数据规模暗示了什么能容忍 O(n^2) 还是必须 O(n log n)一旦你完成了这种分类解题就不再是无序搜索而是“套模板 调边界”的工程过程。LeetCode 大神们的核心优势不是你想象中的创造力而是他们看得够多能迅速把新题映射到旧框架里。1.3 适合阅读这篇文章的人群如果你满足以下任意一条本文的内容会对你帮助最大刚开始刷 LeetCode希望建立系统框架而不是零散记题。已经刷了 50 题以上但总觉得“量变没有引起质变”。正在准备面试需要短时间内构建高频题型的肌肉记忆。刷题训练中反复在滑动窗口、回溯、DP 上栽跟头。如果你已经能稳定写出多道 Hard 题可能不需要这篇文章的模板细节但里面关于模式分类的判断框架依然值得参考。2. 核心概念什么是“解题模式”以及为什么它有效2.1 模式不是模板而是“场景 解法”的映射在进入具体内容前要先厘清一个概念本文所说的“解题模式”不是指一段写死逻辑的代码让你无脑照抄而是指“数据结构特征 求解目标 常见解法”的组合映射。举一个例子输入是一个数组求解目标是“连续子数组满足某个条件的最大/最小长度”这个描述对应着滑动窗口的经典适用场景。如果条件具备单调性——窗口右移条件满足性单调变化——那么滑动窗口就是最优策略。这种映射关系才是模式的核心。模板只是把它固化成代码形式降低你从“思路”到“实现”的摩擦力。2.2 为什么模式比题目更重要传统刷题方式有两个低效点第一题目数量无限但模式有限。LeetCode 目前有几千道题目而据社区统计约 80% 的题目可以归入大约 20 类常见模式。与其在题海里低效重复不如先把核心模式吃透。第二面试官考察的是“迁移能力”。面试题目往往不是原题而是融合了多种基本模式的变形。如果你的脑子里保存的是“题目 A 的解法”面对变形题时很难调用出来但如果保存的是“场景 X → 解法 Y”的模式你就能够把新题拆解成“数组连续子区间问题 条件单调性 → 滑动窗口”这样的推理链。2.3 模式思维需要配合数据规模一起使用算法学习中容易陷入的误区是不考虑数据规模就直接套复杂算法。实际上数据规模本身就是最重要的题目线索之一数据规模 N可接受复杂度常见算法N ≤ 20O(2^n)回溯、状态压缩枚举N ≤ 500O(n^3)Floyd、三重循环 DPN ≤ 5000O(n^2)双重循环 DP、朴素动态规划N ≤ 10^5O(n log n)排序、二分、线段树/树状数组N ≤ 10^6O(n)双指针、滑动窗口、线性 DP、单调栈N 10^6O(1) / O(log n)哈希、位运算、数学推导如果你读题时先看数据范围就已经排除掉至少一半的错误方向。比如 N 是 10^5 的数组题基本可以放弃 O(n^2) 的暴力思路优先考虑滑动窗口、前缀和、二分查找或单调栈。3. 八种核心模式全景图先给出这 8 种模式的全景总览再逐个深入。建议你把这页当作刷题前的“第一页”先建立全局认知再进入细节。模式名称最适合解决的问题特征典型时间复杂度核心数据结构/技巧代表题型滑动窗口连续子数组/子串满足某条件的最大、最小、固定长度O(n)双指针 哈希/计数无重复字符最长子串双指针有序数组中的两数/三数之和反转数组链表环检测O(n) 或 O(n log n)对撞指针/快慢指针三数之和二分查找有序数据中的查找最大值最小化/最小值最大化O(log n)边界收缩爱吃香蕉的狒狒前缀和与差分子数组求和、区间频繁加减、二维区域和O(n) 预处理 O(1) 查询前缀和数组/哈希优化和为 K 的子数组单调栈找下一个更大/更小元素柱状图类最大面积O(n)单调递增/递减栈每日温度回溯算法全排列、子集、组合、棋盘填数等需要枚举所有方案的题O(2^n) 指数级DFS 撤销操作全排列树形 DFS/BFS二叉树/多叉树的最大深度、路径和、层序遍历O(n)递归 / 队列二叉树的层序遍历动态规划最优子结构 重叠子问题求最值或计数O(n) 或 O(n^2)状态设计与转移方程打家劫舍需要说明的是真实题目往往是多种模式的组合。例如“寻找数组中最短的连续子数组使其和 ≥ K”是滑动窗口与贪婪思想的结合“求一个数组的逆序对数量”是归并排序与分治模式的结合。先掌握单一模式再学习模式组合进阶路径会更平滑。4. 模式一滑动窗口——连续子区间的万能解法4.1 适用场景与判断方法滑动窗口解决的问题有一个非常清晰的特征需要在一个线性结构上寻找满足约束条件的连续区间。它最常见的三种变形是固定窗口长度窗口大小固定要求计算窗口内的最大值、平均值、或满足某种条件的次数。可变窗口求最大在满足某个约束条件的前提下求最长的连续区间长度。可变窗口求最小在满足某个约束条件的前提下求最短的连续区间长度。判断是否可以使用滑动窗口的关键在于右指针右移时约束条件是否具有单调性。换句话说当窗口变大时约束的满足情况只会越来越难或越来越容易而不是先满足后违反再满足这种来回震荡的情况。如果约束条件具有这种单调性就可以通过“右指针不断前进 左指针按需收缩”的方式来维护一个始终满足条件的窗口从而在线性时间内找到答案。# 模板可变窗口求最短 / 最长 # 适用范围数组/字符串上满足条件的连续子区间极值问题 def find_subarray(nums, target): n len(nums) left 0 # 左指针 window_sum 0 # 窗口维护的统计量具体是什么取决于题目 ans float(inf) # 求最小值就初始化为无穷大 for right in range(n): # 1. 右指针纳人新元素更新窗口状态 window_sum nums[right] # 2. 尝试收缩左边界直到窗口不再满足条件 # 这段逻辑是模板中变化最多的部分需要根据题目条件调整 while window_sum target: # 这里以“和 target”为例 # 3. 窗口当前是合法的更新答案 ans min(ans, right - left 1) # 4. 移动左指针并把左边元素移出窗口 window_sum - nums[left] left 1 return ans if ans ! float(inf) else -14.2 代码模板解析模板的核心只有三个动作右指针扩张每轮循环必然把 nums[right] 纳入窗口统计这与直觉一致——窗口右边界只能向右走不能回头。左指针收缩收缩的条件是“窗口不再满足题目要求”。这时必须移动左指针直到重新满足要求。答案更新时机模板里的答案更新放在收缩内部意味着“当前窗口是满足条件的最小窗口”。如果你要求的是“满足条件的最长窗口”需要在收缩后额外判断一次当前窗口是否仍然满足条件并更新答案。4.3 常见错误滑动窗口实现出错最多的地方在于左右指针的更新顺序写反导致无限循环。收缩 left 时忘记把 nums[left] 从统计量中减去导致窗口状态失真。答案初始值设置错误。求最小值时初始化为 0会导致所有答案都被更新为 0。忽略“空窗口”的情况比如数组所有元素都不满足条件此时应该返回 -1 或 0取决于题目要求。4.4 经典例题与思路以 LeetCode 3“无重复字符的最长子串”为例。这道题可以这样映射到滑动窗口模型维护一个哈希集合或数组记录当前窗口内出现过的字符。右指针不断向右扩展如果遇到重复字符就收缩左指针直到重复字符被移除。每次窗口合法时用窗口长度更新答案。class Solution: def lengthOfLongestSubstring(self, s: str) - int: char_set set() left 0 ans 0 for right in range(len(s)): # 收缩左边界直到没有重复字符 while s[right] in char_set: char_set.remove(s[left]) left 1 # 加入当前字符 char_set.add(s[right]) # 更新答案 ans max(ans, right - left 1) return ans这段代码里while循环虽然看似内层有一个循环但整体时间复杂度仍然是 O(n)因为left最多从 0 移到 n-1不会来回移动。这就是滑动窗口能在线性时间内解题的根本原因。5. 模式二双指针——有序序列与链表问题的利器5.1 两种双指针思路的区分双指针不是一个单一的算法而是两类思路的总称。它们的适用场景完全不同初学者经常混淆。对撞指针左指针指向数组开头右指针指向数组末尾两者相向移动。常用于有序数组中的两数之和、三数之和、反转数组、盛水最多容器等问题。快慢指针两个指针同向移动但速度不同。常用于链表中的环检测、找链表中间节点、链表中倒数第 k 个节点等问题。# 模板对撞指针两数之和类问题 # 使用前提数组 nums 已有序如果未排序需要先排序或改用哈希表 def two_sum_sorted(nums, target): n len(nums) left, right 0, n - 1 while left right: current_sum nums[left] nums[right] if current_sum target: return [left, right] # 返回下标 elif current_sum target: left 1 # 和太小需要更大的数左指针右移 else: right - 1 # 和太大需要更小的数右指针左移 return [] # 找不到5.2 为什么对撞指针能把 O(n^2) 降到 O(n)如果你用暴力解法寻找有序数组中和为 target 的两个数需要枚举所有下标对 (i, j)复杂度为 O(n^2)。对撞指针的聪明之处在于利用了“有序”这一性质。假设 left 指向最小值right 指向最大值如果 nums[left] nums[right] target说明最左边的数与最大的数相加都不够那么 left 右移是唯一合理的选择。如果 nums[left] nums[right] target说明最小的数与最右边的数相加都超了那么 right 左移是唯一合理的选择。实际上对撞指针在每一步都排除了大量不可能的候选组合所以总步数最多是 O(n)而不是 O(n^2)。理解这一点比背过代码更重要面试时如果你能讲清“为什么这个算法是正确的”远比能默写出代码加分。5.3 快慢指针处理链表的经典场景链表与数组不同无法通过下标直接访问中间节点。如果想知道链表是否成环最容易想到的方法是用哈希集合记录访问过的节点但空间复杂度为 O(n)。快慢指针用一个更聪明的办法把空间降为 O(1)慢指针每次走一步快指针每次走两步。如果链表中存在环快指针最终会在环中“追上”慢指针——它们相等时说明存在环。# 模板快慢指针判断链表是否有环 def has_cycle(head): slow head fast head while fast and fast.next: slow slow.next # 慢指针走一步 fast fast.next.next # 快指针走两步 if slow fast: # 快指针追上了慢指针说明有环 return True return False # 快指针走到末尾说明无环这个代码里容易踩的坑是条件判断。必须先检查fast不为空然后检查fast.next不为空否则访问fast.next.next可能抛出空指针异常。6. 模式三二分查找——不只是“从有序数组中找一个数”6.1 二分查找的两种框架很多新手以为二分查找只能用于“查找目标值”其实它是一套更通用的框架。理解以下两种变体比会背诵基础版 while 循环更有价值。找等于 target 的下标适用于数组严格有序且允许直接比较的场景。找满足条件的最小/最大位置适用于“最大值最小化”或“最小值最大化”的优化问题。第二种变体在解 LeetCode 周赛时尤其重要很多 Hard 题看起来和二分没关系但本质上是二分答案把优化问题转换成判断某个候选答案是否可行的判定问题。# 模板二分答案求满足条件的最小值 # 以 LeetCode 875 爱吃香蕉的狒狒 为例 # 珂珂每小时最多吃 k 根香蕉求能在 h 小时内吃完所有香蕉的最小速度 k def min_eating_speed(piles, h) - int: def can_finish(speed: int) - bool: # 判断用 speed 速度能否在 h 小时内吃完 hours 0 for pile in piles: hours (pile speed - 1) // speed # 向上取整 return hours h left 1 right max(piles) # 最快的速度就是一次吃完最大的一堆 while left right: mid (left right) // 2 if can_finish(mid): right mid # 这个速度可以吃完试试更小的速度 else: left mid 1 # 吃不完必须加快 return left6.2 这题的判断函数怎么写“爱吃香蕉的狒狒”这类题之所以让很多新手卡住是因为它表面上没有任何“数组里面找数字”的线索。但如果做过模式分类训练你会注意到求的是“速度 k 的最小值”而 k 的取值空间是 [1, max(piles)]。速度越快吃完所需时间越少这构成单调递减关系。单调关系就是二分答案的核心条件。这里真正重要的技巧是判断函数can_finish(speed)。它的作用是回答以 speed 速度能否在 h 小时内完成这个判断本身就是一个可以在 O(n) 时间内解决的贪心模拟。通过二分答案每次缩小一半候选区间最终时间复杂度是 O(n log max(piles))。6.3 二分查找的边界处理技巧写二分代码最容易出 bug 的地方永远是左右边界的更新如果分支 A 是left mid 1分支 B 是right mid建议使用mid left (right - left) // 2避免 mid 永远无法更新 left 的情况。如果分支 A 是left mid分支 B 是right mid - 1则必须让 mid 上取整mid (left right 1) // 2否则 left 和 right 相邻时可能死循环。如果记不住这个结论可以采用统一的写法一律用mid (left right) // 2并配合left mid 1与right mid。这种写法的左右边界收缩逻辑最不容易出错。7. 模式四前缀和与差分——区间求和的时间穿越术7.1 从“每次 O(n)”到“预处理 O(1)”如果面试官问你给定一个数组多次给出区间 [l, r]求区间内所有元素的和。你会怎么思考最直接的暴力方法是每次查询都遍历一遍 l 到 r复杂度 O(区域长度)。如果数组长度为 10^5查询次数也是 10^5就会超时。前缀和的核心思想是提前准备一个“从开头到当前位置”的累计和数组preSum[i] 表示原数组 nums[0] 到 nums[i-1] 的和。有了 preSum 后区间 [l, r] 的和可以表示为 preSum[r1] - preSum[l]。这样每次区间和查询的复杂度从 O(n) 降为 O(1)。7.2 前缀和模板与细节# 模板一维前缀和 class PrefixSum: def __init__(self, nums): n len(nums) # pre_sum[i] 表示 nums[0] 到 nums[i-1] 的和 self.pre_sum [0] * (n 1) for i in range(n): self.pre_sum[i 1] self.pre_sum[i] nums[i] def range_sum(self, left: int, right: int) - int: # 返回闭区间 [left, right] 的和 return self.pre_sum[right 1] - self.pre_sum[left]这里详细解释一下pre_sum数组长度设为 n1 的原因如果要求 nums[0] 到 nums[i] 的和那就是 pre_sum[i1]当查询区间 [0, i] 时计算式是 pre_sum[i1] - pre_sum[0]pre_sum[0] 为 0 恰好对应空前缀。这个设计避免了特判 left 0 时对 pre_sum[-1] 的访问。7.3 前缀和 哈希表的组合技巧LeetCode 560“和为 K 的子数组”是前缀和的关键练习。它不只是单纯求前缀和还引入了哈希表来优化查找题目问有多少个子数组的和等于 k。传统做法枚举所有子数组并求和O(n^2)。优化思路是子数组 [j, i] 的和等于 preSum[i1] - preSum[j]。如果要求这个值等于 k就等价于 preSum[j] preSum[i1] - k。使用字典记录历史上每个 preSum 值出现的次数就可以在遍历数组时立即知道有多少个 j 满足条件。from collections import defaultdict def subarray_sum(nums, k) - int: # 记录前缀和出现的次数 pre_sum_count defaultdict(int) # pre_sum 为 0 的情况出现过一次表示空前缀 pre_sum_count[0] 1 current_sum 0 count 0 for num in nums: current_sum num # 如果之前出现过 current_sum - k说明存在子数组和为 k count pre_sum_count[current_sum - k] # 记录当前前缀和 pre_sum_count[current_sum] 1 return count这个模板最关键的地方是pre_sum_count[0] 1这行初始化很多初学者会漏掉导致“从下标 0 开始的合法子数组”没有被统计。更精确地说当某个前缀和本身刚好等于 k 时我们需要在字典里查到前缀和 0 出现过一次如果没初始化就会漏掉计数。7.4 差分数组区间快速修改的利器与前缀和解决“多次区间求和”相对应差分数组解决的是“多次区间增减最后询问数组最终值”的问题。它的核心思想是区间 [l, r] 整体加上 val可以只修改 diff[l] val 和 diff[r1] - val最后通过一次前缀和恢复原数组。这个技巧在 LeetCode 370“区间加法”和航班预订统计等题目中很常见。如果你发现题目描述里有大量“对 [l, r] 区间执行 1 / -1”的操作就可以考虑差分数组。8. 模式五单调栈——处理下一个更大元素的标准姿势8.1 单调栈解决什么问题单调栈的应用场景通常具有这样的特征需要为数组中的每个元素找到它右边或左边第一个比它大或小的元素。暴力解法是双重循环 O(n^2)单调栈则能在 O(n) 内解决。“单调栈”这个名称的含义是维护一个栈内元素单调递增或单调递减的栈。通过入栈和出栈操作我们可以在元素出栈时确定它和当前遍历元素之间的相对关系。8.2 单调栈通用模板# 模板寻找每个元素右边第一个比它大的元素的下标 # 返回一个列表 answeranswer[i] 表示 nums[i] 右边第一个大于它的元素下标不存在则为 -1 def next_greater_element_indices(nums): n len(nums) ans [-1] * n stack [] # 单调递减栈栈中下标对应的值是递减的 for i in range(n): # 当前元素比栈顶元素大说明栈顶元素遇到了右边第一个更大的元素 while stack and nums[i] nums[stack[-1]]: top stack.pop() ans[top] i stack.append(i) return ans8.3 如何记忆单调栈的“单调方向”这是初学者最长混淆的地方到底应该用单调递增栈还是单调递减栈一个记忆方法是当你要找“右边第一个更大的数”时栈中元素从栈底到栈顶是递减的。因为一旦当前元素比栈顶大栈顶就要出栈并得到答案栈内自然维护了一个递减序列。如果你想找的是“右边第一个更小的数”栈内单调方向反过来变成单调递增栈。8.4 单调栈的经典例题思维链以 LeetCode 739“每日温度”为例。题目说给定一个数组 temperatures返回一个数组 answeranswer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果说得更直白一点就是找每个位置右边第一个比它大的元素然后计算下标差。唯一的变化是把“下一个更大元素的下标”替换成“下标差”代码主体几乎和上面的模板一致。另一个非常经典的单调栈题是 LeetCode 84“柱状图中最大的矩形”。这道题的难点在于它不是找“下一个更大元素”而是找每个柱子左右两侧第一个比它矮的位置。思路同样来自单调栈遍历高度数组维护一个单调递增栈当遇到一个比栈顶矮的柱子时以栈顶柱子高度作为矩形高度计算它能延展的宽度范围。9. 模式六回溯算法——暴力枚举的优雅写法9.1 回溯的时间复杂度与适用边界回溯算法本质上是暴力搜索每个可能的方案只不过在搜索过程中提前裁剪掉不可行的分支。它适合的问题类型包括决策类问题和方案枚举类问题比如从 n 个数中选 k 个数的所有组合。n 个不同元素的全排列。字符串的所有合法括号组合。在一个 8×8 棋盘上放置 8 个皇后使它们互不攻击。矩阵中是否存在一条路径使其等于给定的单词。应用回溯算法的前提是数据规模不大。一般来说 n ≤ 15 或 n ≤ 20 时回溯可接受如果 n 达到 30回溯的指数级复杂度基本无法通过。数据规模是判断是否使用回溯的第一准则。9.2 子集 / 组合 / 排列统一模板LeetCode 中这一类题形成一个家族家族成员的差异只体现在“选出来的方案是否考虑顺序”以及“每个元素能否重复选取”。# 模板组合从 nums 中选 k 个数不考虑顺序每个元素只能用一次 def combine(nums, k): result [] path [] def backtrack(start): # 满足条件当前路径长度达到 k if len(path) k: result.append(path[:]) # 注意这里要拷贝 path return for i in range(start, len(nums)): # 做选择 path.append(nums[i]) # 递归注意是 i1保证不回头、不重复选取当前元素 backtrack(i 1) # 撤销选择回溯最重要的操作 path.pop() backtrack(0) return result # 模板全排列考虑顺序每个元素只能用一次 def permute(nums): result [] path [] used [False] * len(nums) def backtrack(): if len(path) len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue # 选择 used[i] True path.append(nums[i]) # 递归 backtrack() # 撤销 path.pop() used[i] False backtrack() return result9.3 回溯模板的三个关键点第一个关键点是路径拷贝。在满足条件时必须使用path[:]生成新列表而不是直接把path加入 result。Python 中列表是引用类型所有回溯过程的 path 共享同一个对象如果直接加入最终列表里全是同一个被撤销到空的 path这可能是初学者最常踩的坑。第二个关键点是撤销操作。回溯的精髓是“做完决定后要恢复到决定之前的状态”。如果你选择了 append递归后必须 pop如果你改了 used 状态递归后必须还原。漏掉任何一次撤销都会导致搜索空间被错误裁剪。第三个关键点是去重逻辑。LeetCode 中很多组合、排列题会有重复元素比如“组合总和 II”和“全排列 II”需要先排序再通过判断nums[i] nums[i-1] and not used[i-1]来剪掉重复分支。这是最常被追问的进阶点。10. 模式七树的 DFS 与 BFS——递归思维的分水岭10.1 二叉树题为什么如此重要面试官喜欢考二叉树因为它是一种高度结构化、但又能很好地考察递归思维的数据结构。二叉树的题目通常不涉及复杂的数学结论却能考察你是否理解“子问题与父问题的关系”。最常见的两类树问题是深度优先遍历前序、中序、后序遍历。这类题目通常用递归实现。广度优先遍历层序遍历。这类题目通常用队列实现核心是每次处理一层。10.2 DFS 递归模板树的 DFS 模板是所有树题的基础class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right # 前序遍历模板根 - 左 - 右 def preorder(root): result [] def dfs(node): if not node: return result.append(node.val) # 处理当前根节点 dfs(node.left) # 递归左子树 dfs(node.right) # 递归右子树 dfs(root) return result递归模板看起来简单真正的难点在于你需要清楚递归函数的返回值代表什么。比如“求二叉树的最大深度”dfs 函数的返回值是“以当前节点为根的子树的最大深度”那么递归逻辑就是max(dfs(left), dfs(right)) 1。只要明确返回值语义递归代码基本不会写错。10.3 BFS 层序遍历模板层序遍历要求按层级输出节点这需要用到队列from collections import deque def level_order(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) # 当前层的节点数量 current_level [] for _ in range(level_size): node queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result这段代码最关键的是level_size len(queue)这一行。必须在循环开始前记录当前层的节点数量因为队列在遍历的过程中会不断加入下一层的节点。如果不提前保存for 循环会把下一层的节点也遍历掉导致层级混乱。BFS 模板还有一个常见扩展如果要求“之字形层序遍历”LeetCode 103只需在偶数层逆序输出即可不需要改变算法主体。11. 模式八动态规划——最难掌握但最有套路的模式11.1 动态规划不是玄学而是一个四步框架很多初学者一提到动态规划就害怕原因是他们试图一次性理解整个递推过程而忽略了动态规划本身就是一个非常机械的解题流程。做题时如果可以严格按以下四步推进大部分 DP 题都能解出来定义状态dp[i] 表示什么含义通常是“考虑前 i 个元素”情况下的最优值或方案数。初始化dp[0] 或 dp[1] 等于多少状态转移方程dp[i] 如何由更小的状态推导出来确定遍历顺序从小到大还是从大到小一维数组还是二维数组11.2 一维 DP 模板举例以 LeetCode 198“打家劫舍”为例。题目的场景是你是一个专业小偷计划偷窃沿街房屋每间房内有一定现金但如果同时偷窃相邻两间房就会触发报警求能偷到的最大金额。按照四步框架来分析状态定义dp[i] 表示偷到第 i 间房时前 i 间房子能获得的最大金额。初始化dp[0] 0表示一间房都不偷dp[1] nums[0]表示只有一间房时只能偷它。状态转移对于第 i 间房1-index 思路有两个选择不偷这一间则最大金额等于 dp[i-1]偷这一间则前一间不能偷最大金额等于 dp[i-2] nums[i-1]。转移方程是 dp[i] max(dp[i-1], dp[i-2] nums[i-1])。遍历顺序从左到右逐步计算。def rob(nums) - int: n len(nums) if n 0: return 0 if n 1: return nums[0] dp [0] * (n 1) dp[1] nums[0] # 只有一间房时偷它 for i in range(2, n 1): # nums[i-1] 是第 i 间房的金额 dp[i] max(dp[i-1], dp[i-2] nums[i-1]) return dp[n]这种一维 DP 题目模式非常固定唯一的难点就是状态定义是否合理。状态定义对了转移方程往往就顺理成章。11.3 背包问题二维 DP 的必修课如果你想进阶到更复杂的 DP0-1 背包问题是最重要的跳板。它的标准描述是有 n 个物品每个物品有重量 w[i] 和价值 v[i]在背包容量为 C 的情况下选择若干物品装入背包求能装下的最大总价值。状态定义往往是二维的dp[i][j] 表示前 i 个物品在容量为 j 的背包里能装下的最大价值。# 模板0-1 背包二维 DP 版本 def knapsack_01(weights, values, capacity): n len(weights) # dp[i][j] 表示前 i 个物品容量为 j 时的最大价值 dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): for j in range(1, capacity 1): w weights[i - 1] v values[i - 1] if j w: # 当前容量放不下第 i 个物品 dp[i][j] dp[i - 1][j] else: # 不选第 i 个物品 或 选第 i 个物品 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - w] v) return dp[n][capacity]这段代码的优点是逻辑直接每个状态都清晰可见。实际面试时如果能先写出二维版本再通过“滚动数组”优化空间会是一个很好的加分展示。注意0-1 背包与完全背包的区别只在于内层循环的方向。0-1 背包从大到小遍历容量是为了避免同一个物品被选取多次完全背包从小到大遍历容量是因为每个物品可以无限次使用。这是新手最容易混淆的细节。12. 如何把别人代码转化为自己的“模式库”12.1 从“抄题解”到“理解题解”的三步转换法看到这里你已经浏览了 8 种模式的代码模板。有人可能会说模板我看懂了可自己拿到新题时还是不知道用哪个模板。这个问题是真实的。真正把模板内化为自己的模式库需要一个主动学习过程。我的建议是三步法第一步读完题后不急着看题解先尝试用 30 秒判断题目属于哪种模式。如果判断不出来就去查看题解中“解题思路”部分并把它复制到自己的错题本中。第二步等 2 到 3 天后再重做这道题。到那时候你可能已经忘记了代码细节但记住了模式。这一步的目的就是训练你的分类能力。第三步找 3 道同类题来验证。例如你看了滑动窗口的题解可以立刻去做“无重复字符的最长子串”“最小覆盖子串”“字符串的排列”当你做完这 3 道题再回看模板理解会完全不同。12.2 如何把模板改造成自己的版本模板不是圣旨而是一个起点。当我刚开始刷题时也喜欢收集各种模板。后来慢慢发现最好的模板是自己根据出错教训改出来的。看到模板后的正确动作是在纸上手写一遍感受代码的每一个变量都代表什么。去掉所有注释自己重新默写一遍。尝试把模板应用在不同的题目上观察哪些行是永远不变的。最后形成“自己的版本”把注释改成自己能理解的表达方式。当你完成了这个过程那个模板就变成了你的“肌肉记忆”而不是一段需要重新理解的外来代码。13. 常见问题与排查思路即使理解了模式刷题中还是可能遇到各种问题。把常见的现象、原因和处理方案整理成下表可以作为排错清单使用问题现象可能原因排查方式解决方案代码在示例输入能跑通但在更大的测试用例上超时时间复杂度达不到要求暴力解法需要优化查看数据规模估算自己写法的复杂度判断是否可用双指针、滑动窗口、前缀和等降复杂度解法滑动窗口窗口内统计量与实际不符移动左指针时忘记把左边元素从统计量中扣除用单步调试打印 left、right 和窗口统计量检查收缩逻辑中所有需要扣减的计数器二分查找死循环边界更新选择错误或 mid 取整方式不对用两个元素的数组单步推演统一使用 mid 下取整 left mid 1 right mid 的写法回溯结果全为空列表满足条件时把 path 本身加入结果没有使用 path[:] 浅拷贝检查 result.append 位置改为 result.append(path[:])回溯结果有重复没有正确去重或同一个分支被重复搜索检查 used 数组是否在递归后正确还原排序后判断相邻相同元素是否在同一层尝试过树层序遍历输出漏掉层或顺序混乱没有在每轮开始时记录 level_size用队列长度 debug 输出每轮节点在 while queue 内部、for 循环之前计算 level_sizeDP 结果比预期大状态转移时重复计算或初始化边界不对小规模手工模拟 dp 表的填充过程核实 dp 数组每个位置的业务含义区间求和题目暴力超时没有使用前缀和每次查询都重新遍历统计查询次数与区间长度预计算前缀和数组查询时 O(1) 得到答案14. 最佳实践与工程化刷题建议14.1 构建自己的题目-模式映射表最有效的刷题管理等式是题目数量 复盘 能力提升题目数量却无复盘 自嗨。建议你建立一张表格每刷完一道题就记录以下字段题号题目简短描述属于哪种模式是否套模板易错点能否用不同方法解3无重复字符最长子串滑动窗口是左指针收缩条件可以如动态规划875爱吃香蕉的狒狒二分答案是向上取整写法否每周复盘一次比较同一模式内多道题的差异和共性比盲目追求 AC 数量效果更好。14.2 用复杂度思维约束代码写代码前先问自己三个问题数据范围最大是多少我的算法最坏情况下需要执行多少次操作这个执行次数是否在限制时间内可完成如果答案是“否”你必须立刻换思路而不是在暴力解法上修修补补。复杂度估算能力是一个需要刻意训练的习惯。举个例子如果 N 10^5你又写出一个双 for 循环不用提交也基本知道一定会超时。14.3 杜绝只刷题不总结的“题海陷阱”刷题过程中总结的核心不是把题目抄一遍而是记录“我为什么没想到这个解法”“题解的哪一步是重点”。如果总是直接看题解然后复制粘贴那就不会形成自己的解题直觉。这里给一个可量化的建议每做 5 道题必须写至少 1 道题的完整解题笔记内容包括题目、思路、代码、复杂度、为什么这个思路是对的。当你尝试把思路表达成文字时模棱两可的理解会被自动暴露出来。14.4 准备面试时的专项训练如果你是为了面试刷题建议按模式而不是按题号分块准备。比如一周内专注滑动窗口 双指针另一周专注 DP。面试官常问的是“你如何分析这道题”所以平时的练习中也要训练自己说出模式判断的思路“我注意到这是一个连续子数组问题并且随着窗口扩大条件单调变化所以我先考虑滑动窗口。如果滑动窗口无法解决我会考虑前缀和来降低区间和计算的开销。”这类表述才是面试官最想听到的解题思路。14.5 不要成为模板的奴隶题目和代码是死的思路是活的。如果你只背模板而不理解模板成立的前提遇到变式时反而会被模板限制住。例如滑动窗口模板要求条件具有单调性。如果题目说“窗口内不能有重复元素”滑动窗口是可行的因为窗口越长越容易有重复元素存在单调性。但如果题目说“窗口内所有数字之和恰好等于 K且元素可正可负”此时窗口扩大不满足单调性滑动窗口就不适用这时你必须立刻切换到前缀和 哈希的思路。一眼辨别出“这题能不能用某个模式”的能力才是刷题真正训练出来的核心竞争力。它比默写任何模板都重要。15. 总结模式是刷题的杠杆回顾整篇文章8 种模式覆盖了 LeetCode 中最常见的高频题型滑动窗口解决连续子数组与子串问题。双指针解决有序数组与链表问题。二分查找解决数据有序或答案单调的问题。前缀和与差分解决区间和、区间修改问题。单调栈解决“下一个更大/更小元素”的线性扫描问题。回溯算法解决数据规模较小的枚举类问题。树的 DFS/BFS 解决二叉树与图的遍历问题。动态规划解决有最优子结构的最优化问题。你会注意到这些模式之间有天然的互补关系滑动窗口和前缀和都处理子数组但前者依赖单调性后者不依赖DFS 和回溯共享递归框架但回溯带有撤销操作二分查找和单调栈都是把无序搜索压缩成有序推理。推荐的实践路径是先花两周时间每天处理一种模式第一天阅读文章中的模板并默写第二天做 3 道真题应用模板第三天复盘错题。两周后再尝试不看模板解决 LeetCode 热题 100 中的混合题训练模式切换能力。真正的算法面试准备不是刷多少道题而是掌握多少种模式以及能否在紧张的面试环境中快速、准确地把问题归入正确的模式。只要模式库建立起来LeetCode 的很多题目对你来说就不再是全新的未知难题而是一道道换皮的老朋友。