很多人刷算法题喜欢按题目顺序一遍遍刷刷完就忘面试时看到原题都认不出来。我自己也经历过这个阶段后来才开始按题型总结套路发现面试考来考去就是那些高频模型。上一篇讲了链表、哈希和双指针这篇继续往下聊重点放在真正决定面试成败的几类题型上排序与TopK、滑动窗口、二叉树遍历、动态规划。这些都是面试官最爱出的题也是最能拉开差距的地方。这篇博文不会把所有题都罗列一遍而是帮你建立解题的“条件反射”看到题目先判断属于哪种题型的变体再套用对应的套路最后结合Python的语法特性写出简洁且不超时的答案。所有代码都是可以直接运行的复杂度分析和易错点也会同步讲清楚。1. 排序与TopK问题面试里的“拦路虎”其实是纸老虎排序本身不常直接考但几乎每场面试都会以“第K大”“最小K个数”“数组中的众数”等变体出现。很多人在这种题上翻车不是因为不知道快排或堆而是没搞明白“题目改了一个条件算法该怎么换”。1.1 快排为什么是默认选项以及三路切分解决了什么快排是面试时手写频率最高的排序算法。它的平均时间复杂度O(n log n)常数小而且非常适合用来解决TopK问题。但标准快排在遇到大量重复元素时性能会退化成O(n²)。比如数组全是一万个1每次partition都只能分割出一个元素递归深度直接爆炸。解决方案是三路快排。思路很简单每次选一个pivot把数组分成小于、等于、大于三部分。等于pivot的部分不用再递归只有小于和大于的部分继续处理。在Python中实现三路快排可以用左右指针向中间扫描也可以利用列表推导把数组拆成三段再递归。后者虽然额外使用了空间但代码简洁面试时写出来也容易解释。def quick_sort_3way(nums): if len(nums) 1: return nums pivot nums[len(nums) // 2] left [x for x in nums if x pivot] mid [x for x in nums if x pivot] right [x for x in nums if x pivot] return quick_sort_3way(left) mid quick_sort_3way(right)看起来简单但面试官可能会问“这个写法空间复杂度是多少”每层递归都产生新列表空间复杂度O(n log n)。如果想达到原地排序就得用双指针扫描def partition_3way(nums, l, r): pivot nums[l] lt l # nums[l1:lt] pivot gt r 1 # nums[gt:r1] pivot i l 1 while i gt: if nums[i] pivot: lt 1 nums[i], nums[lt] nums[lt], nums[i] i 1 elif nums[i] pivot: gt - 1 nums[i], nums[gt] nums[gt], nums[i] else: i 1 nums[l], nums[lt] nums[lt], nums[l] return lt, gt这里有个很容易犯错的地方当nums[i] pivot时交换过来的nums[gt]还没被比较过所以i不能加一。只有从左边交换过来的元素才确保已经处理过。这个细节现场写错的人很多面试官一眼就能看出来你有没有真正理解快排。1.2 TopK问题的两种解法堆与快速选择TopK是排序题里最高频的考点。求“第K大”最简单的想法是排序后取索引但面试官想看的是你能否写出O(n)期望时间的快速选择或者O(n log k)的堆解法。堆解法适合处理“数据流”场景因为只需要维护大小为K的堆。Python里直接用heapq默认是小顶堆。求第K大就维护一个大小为K的小顶堆堆顶就是答案。import heapq def find_kth_largest(nums, k): heap [] for num in nums: if len(heap) k: heapq.heappush(heap, num) elif num heap[0]: heapq.heapreplace(heap, num) return heap[0]注意heapreplace是弹出堆顶再压入新元素比先heappop再heappush效率略高。面试时主动提这个细节会显得你基本功扎实。快速选择是快排的变体。利用partition后pivot的最终位置如果它正好是第n-k个索引就找到了答案如果小于n-k就在右半部分继续否则在左半部分。import random def find_kth_largest(nums, k): def partition(l, r): pivot_idx random.randint(l, r) nums[pivot_idx], nums[r] nums[r], nums[pivot_idx] pivot nums[r] i l for j in range(l, r): if nums[j] pivot: nums[i], nums[j] nums[j], nums[i] i 1 nums[i], nums[r] nums[r], nums[i] return i target len(nums) - k l, r 0, len(nums) - 1 while l r: mid partition(l, r) if mid target: return nums[mid] elif mid target: l mid 1 else: r mid - 1 return nums[l]注意这里为了求第K大partition时用了 pivot使得左边都是不小于pivot的元素。如果面试官要求“数组中有重复元素怎么办”快速选择期望时间仍是O(n)因为随机化pivot可以避免最坏情况。我建议刷题时把这两种解法都写熟练因为面试官很爱追问“如果数据量很大不能一次读入内存呢”这时候堆解法才是正解。2. 滑动窗口从暴力到最优差的不是代码而是窗口边界滑动窗口高频到什么程度几乎每三场技术面试就有一场会考。它本质上是用一个“可以伸缩的窗口”在数组或字符串上滑过把暴力枚举的O(n²)优化到O(n)。但很多初学者套模板时总是搞不清窗口什么时候收缩、收缩到什么条件导致代码越写越乱。2.1 固定窗口与可变窗口先判断是哪种再动手滑动窗口分两类。固定窗口长度不变比如“长度为K的子数组最大平均数”每次移动时左边出一个、右边进一个。这类题的核心是维护窗口内的累积值代码非常简单。可变窗口就复杂一些它的窗口左右边界会动态变化通常配合一个“约束条件”判断是否收缩。比如“无重复字符的最长子串”、“最小覆盖子串”、“长度最小的子数组”。我习惯用一套统一的模板来应对def solve(s): left 0 state defaultdict(int) # 或者用别的变量维护窗口状态 res 0 for right in range(len(s)): # 加入s[right]到窗口更新状态 state[s[right]] 1 # 当窗口不满足约束时右移left收缩 while not is_valid(state): remove s[left] from state left 1 # 更新结果 res max(res, right - left 1) return res关键点在于while收缩的条件是什么收缩时对state做了什么结果在收缩前更新还是收缩后更新这三个问题理清楚滑动窗口题基本就能稳拿。2.2 经典题“无重复字符的最长子串”的完整推演这道题被问到的频率极高。题目是给定一个字符串找出其中不含有重复字符的最长子串的长度。我见过很多人的第一反应是用哈希集合存窗口内字符遇到重复就“从左往右删直到重复字符被移除”。这个想法是对的但很多人写出来依然是错的原因在于不清楚何时更新答案。正确做法用字典记录每个字符最后出现的位置left表示窗口左边界。遍历right时如果当前字符已经在字典中就把left移到max(left, last_pos[char] 1)然后更新字典和答案。def length_of_longest_substring(s: str) - int: last_pos {} left 0 res 0 for right, ch in enumerate(s): if ch in last_pos: left max(left, last_pos[ch] 1) last_pos[ch] right res max(res, right - left 1) return res为什么left要取max而不是直接赋值因为last_pos[ch]可能是很久以前的位置如果直接赋值会把左侧一些仍在窗口内的字符错误地挤出窗口导致结果偏大。比如abba这个字符串处理到最后一个a时last_pos[a]是0但此时left已经是2如果直接把left设为1窗口就变成bba含有重复b答案就不对了。加个max就规避了这个陷阱。这道题的价值在于它展示了滑动窗口的核心是“用一个变量维护窗口的合法边界”而不是真的像队列一样逐个弹出。面试时能把max这一步的道理讲清楚基本上就过关了。2.3 可变窗口的另一个高频变体最小覆盖子串“最小覆盖子串”是滑动窗口题里很有挑战性的一题在字符串s中找到包含字符串t所有字符含重复字符的最短子串。这题考察两个点一是如何判断窗口“覆盖”了t二是如何移动窗口找最小。判断覆盖可以用一个字典need记录t中每个字符的需求量用变量cnt表示窗口中满足需求的字符种类数。当cnt len(need)时说明窗口已经覆盖了t。此时尝试收缩窗口记录更优答案。常见错误是只用字符数量来判断忽略重复字符的需求量。比如t是aa窗口必须包含两个a才算覆盖只包含一个a不算。所以每次移动右边界时只有当前字符在need中且窗口内该字符数量等于需求量时cnt才加一收缩左边界时要等窗口内该字符数量小于需求量时cnt才减一。代码写法有很多版本我提供一个自己常用的def min_window(s: str, t: str) - str: from collections import Counter need Counter(t) missing len(t) # 还缺少多少个字符 left 0 start, min_len 0, float(inf) for right, ch in enumerate(s): if need[ch] 0: missing - 1 need[ch] - 1 while missing 0: if right - left 1 min_len: min_len right - left 1 start left left_ch s[left] if need[left_ch] 0: missing 1 need[left_ch] 1 left 1 return s[start:startmin_len] if min_len ! float(inf) else 这个写法用了很精妙的技巧need初始为t的字符频数need[ch]可能变成负数表示窗口中该字符数量已经超过需求。missing表示窗口中还缺少多少个t的字符。每遇到一个字符如果need[ch] 0说明这个字符是“有用的”missing减一然后need[ch]减一。收缩时正好反过来。理解这个负数技巧就能写出非常简洁的代码。面试时如果能把“负数代表的含义”解释清楚会非常加分。3. 二叉树遍历递归转迭代是面试的常规剧目二叉树是面试数据结构题里的大头。递归遍历非常简单很多人在白板上能写出三五行代码。但面试官为了考察你“是否真正理解递归的栈行为”常常会要求你改成迭代写法。还有人会在树的序列化、最近公共祖先、层序遍历等题目上卡住。这一节把二叉树遍历的迭代套路一次性讲透。3.1 前序、中序、后序遍历的统一迭代模板很多刷题平台上的前中后序遍历迭代写法各不相同有的用两个栈有的用标志位记起来很麻烦。其实可以用一套模板搞定三种遍历在节点入栈时附带一个访问次数或状态。前序遍历是“第一次访问就输出”中序遍历是“第二次访问输出”后序遍历是“第三次访问输出”。但面试手写时我更推荐一种基于“节点栈访问标记”的显式栈模拟法。每次从栈里弹出一个元组(node, visited)如果visited为False就按遍历顺序把子节点压栈注意压栈顺序再把自己标记为visitedTrue重新压栈如果visited为True就处理节点值。这种写法符合递归的本质不容易写错。def preorder_traversal(root): res [] stack [(root, False)] while stack: node, visited stack.pop() if not node: continue if visited: res.append(node.val) else: # 前序根-左-右压栈时逆序右-左-根 if node.right: stack.append((node.right, False)) if node.left: stack.append((node.left, False)) stack.append((node, True)) return res def inorder_traversal(root): res [] stack [(root, False)] while stack: node, visited stack.pop() if not node: continue if visited: res.append(node.val) else: if node.right: stack.append((node.right, False)) stack.append((node, True)) if node.left: stack.append((node.left, False)) return res def postorder_traversal(root): res [] stack [(root, False)] while stack: node, visited stack.pop() if not node: continue if visited: res.append(node.val) else: stack.append((node, True)) if node.right: stack.append((node.right, False)) if node.left: stack.append((node.left, False)) return res注意前序遍历压栈顺序是“右、左、根”因为栈是后进先出先压右再压左左子树才会先弹出。中序是“右、根、左”后序是“根、右、左”。三个版本只改变了压栈顺序是不是很好记这个模板的缺点是有额外的布尔标志稍微牺牲了一点性能但面试时最需要的是“不容易错”。如果你追求更高效前序遍历可以用“根先输出然后右、左入栈”。中序遍历则用经典的“一直往左走”的循环。我建议至少写熟一种模板考场才不会慌。3.2 层序遍历的变体之字形遍历与视图问题层序遍历也就是BFS属于面试必考题。基础版很简单使用队列每次处理一层。但面试官往往会加戏比如要求“之字形”打印或者求二叉树的左视图、右视图。之字形遍历的常见做法是用双向队列deque奇数层从左往右偶数层从右往左。其实可以不用区分方向只要在每个节点的值加入level列表时根据层数决定是追加还是前插。Python中insert(0, val)是O(n)如果层大小很大就不够好。更优方案还是用deque的appendleft。from collections import deque def zigzag_level_order(root): if not root: return [] res [] q deque([root]) left_to_right True while q: level deque() for _ in range(len(q)): node q.popleft() if left_to_right: level.append(node.val) else: level.appendleft(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(list(level)) left_to_right not left_to_right return res这里有个值得跟面试官讨论的点为什么用deque的appendleft而不是列表的insert(0, val)因为列表的insert(0, val)会移动后面所有元素最坏O(n)。虽然n等于单层节点数大部分情况问题不大但面试官想考察你的复杂度意识主动说出来会加分。“树视图”问题是层序遍历的变体。左视图就是每层第一个节点右视图就是每层最后一个节点。代码几乎一样只需要在遍历完一层后取level[0]或level[-1]。高频考点是“二叉树的右视图”LeetCode上的原题。面试者很容易想成“一直往右走”但其实右视图不一定是右链因为如果右子树为空左子树的深层节点也会出现在右视图中。BFS按层取最后一个节点是最稳妥的做法。3.3 二叉树题目的递归后序思路最近公共祖先不是玄学递归是二叉树题目的灵魂尤其后序遍历。因为后序遍历的顺序是“左-右-根”非常适合先从子树收集信息再在根节点汇总。这类题的典型代表是“最近公共祖先”LCA。LCA的核心思路是在二叉树中找到p和q的公共祖先中深度最大的那个。用递归时函数返回什么很关键。我的写法是如果当前节点是p或q就返回当前节点如果左子树和右子树递归结果都不为空说明p和q分别位于当前节点的两侧当前节点就是LCA如果只有一侧不为空就返回那一侧的结果。def lowest_common_ancestor(root, p, q): if root in (None, p, q): return root left lowest_common_ancestor(root.left, p, q) right lowest_common_ancestor(root.right, p, q) if left and right: return root return left or right这段代码只有几行但包含了很多信息。首先root in (None, p, q)利用Python的in判断简洁地处理了空节点、当前节点等于目标节点的情况。其次后续递归先处理子树再在根节点判断就是后序遍历的思路。很多人在面试时能说出大致思路但写出来总是超时或越界多半是边界条件没处理好比如忘记判断root为空或者对“p是q的祖先”这种情况处理不当。上面这段代码对“p是q的祖先”也有效因为递归到p时直接返回上层自然会继续携带结果。4. 动态规划状态定义比转移方程更重要动态规划是算法面试的分水岭。很多人觉得它难是因为一上来就背转移方程。其实DP题的难点在于两件事一是定义出正确的状态二是确定状态之间的转移顺序。这两件事想清楚了代码往往很简单。面试时最忌讳的就是拿到题就套背包模板结果连状态含义都说不清。4.1 背包问题的一维状态压缩到底压缩了什么背包问题是DP里最经典的题型。0-1背包问题描述给定一些物品的重量和价值背包容量为C求能装入的最大价值。二维DP很好理解dp[i][j]表示前i个物品在容量j下的最大价值。转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])意思是不拿第i个物品和拿第i个物品取最大值。二维到一维的压缩是用滚动数组思想因为每次更新dp[i]只依赖dp[i-1]可以用一维数组dp[j]表示容量为j时的最大价值然后从后往前遍历容量。为什么必须从后往前因为如果从前往后dp[j-w[i]]可能已经在当前物品更新过了就成了“重复拿取”同一件物品也就是完全背包的语义。一个很小的顺序差异就改变了题目的类型。def knap01(weights, values, capacity): dp [0] * (capacity 1) for w, v in zip(weights, values): for j in range(capacity, w - 1, -1): dp[j] max(dp[j], dp[j - w] v) return dp[capacity]如果是完全背包每种物品无限件就把内层循环改为正序def knap_complete(weights, values, capacity): dp [0] * (capacity 1) for w, v in zip(weights, values): for j in range(w, capacity 1): dp[j] max(dp[j], dp[j - w] v) return dp[capacity]面试时如果遇到“能否从数组中选出若干数使和等于target”的题大概率是背包的变体。例如“分割等和子集”就是0-1背包判断是否能凑出总和的一半。这类题除了DP还要注意剪枝如果总和是奇数直接返回False。边界条件想清楚了代码不会超过十行。4.2 最长上升子序列从O(n²)到O(n log n)的思维进阶“最长上升子序列”LIS是DP题中高频且容易考进阶的题。转移方程不难dp[i]表示以nums[i]结尾的最长上升子序列长度对所有j i且nums[j] nums[i]dp[i] max(dp[i], dp[j] 1)。时间复杂度O(n²)。面试官大概率会追问“能不能更快”。答案是O(n log n)的贪心二分维护一个数组tailstails[i]表示长度为i1的上升子序列的最小末尾值。遍历每个数用二分查找在tails中找到第一个大于等于当前数的位置替换它。如果当前数比tails所有元素都大就追加到末尾。import bisect def length_of_lis(nums): tails [] for x in nums: i bisect.bisect_left(tails, x) if i len(tails): tails.append(x) else: tails[i] x return len(tails)理解这个算法的关键是明白tails并不一定是一个真实存在的合法子序列它只是维护了“长度为len时最小末尾值”的潜力。很多人在面试时纠结“替换掉末尾值会不会破坏子序列”其实不会因为我们只关心长度不关心具体序列。如果面试官要求输出具体序列就需要在更新过程中记录前驱位置通过回溯得到。不过我遇到的面试里大部分只要求长度这个优化已经足够出彩。4.3 状态定义的三个常见坑下标含义、初始化、遍历方向动态规划面试中代码本身不是最难的概念上的坑才是。第一个坑是下标含义不清。比如“斐波那契数列”dp[0]和dp[1]到底代表什么稍微搞错就会越界。更严重的是“编辑距离”这类二维DPdp[i][j]表示word1[:i]与word2[:j]的编辑距离很多人容易把空串的情况漏掉导致初始化错误。建议动笔前先在注释里写清楚“dp[i][j]代表什么”再写代码。第二个坑是dp数组的初始化。很多人习惯全填0但“求最小值”的DP需要初始化为无穷大否则min操作永远取到0。比如“零钱兑换”求最少硬币数初始化dp[0]0其他dp[i]float(inf)状态转移时dp[i] min(dp[i], dp[i-coin]1)。如果初始化成0结果全是0错得毫无察觉。第三个坑是遍历顺序。背包题中0-1背包从后往前完全背包从前往后矩阵路径类题目通常从上到下、从左到右而“编辑距离”需要按两个维度增加因为依赖左上、上方、左方的状态。这些顺序都是顺着状态转移的方向来的理解依赖关系就不会错。5. 面试现场的题型快速识别与策略前面讲了具体题型的解法但到了面试现场你面对的是陌生的题目怎么快速定位到这些套路这一节分享一些个人总结的实战经验。5.1 从题目关键词反推题型我总结了几个常见信号看到“连续子数组”“子串”“窗口”这类词最有可能是滑动窗口或前缀和。如果要求“ target的最短”或“ target的最长”基本都是滑动窗口。如果数组元素有负数滑动窗口就不适用要想到前缀和加哈希表。看到“第K大”“前K个”“出现次数最多的K个”先想堆。如果数组无序且内存足够想快速选择。如果数据是流式的或者很大不能加载优先用大小为K的堆。看到“树”“二叉树”“遍历”“最低公共祖先”先想递归再想迭代。如果要求“按层”处理就是BFS。看到“最大”“最小”“方案数”“最长公共…”“编辑距离”基本都是动态规划。如果题目中说“可以删除/插入/替换”几乎就是经典DP变体。看到“排列组合”“子集”“所有可能”通常是回溯。回溯题要注意去重和剪枝。当然这只是一个快速判断的起点不是所有题目都能一眼识破。如果发现写出的代码复杂度不对劲就要停下来重新审视题目条件。5.2 从最朴素的暴力解法开始再逐步优化面试时最怕一上来就闷头写最优解。我建议的节奏是先跟面试官说清楚暴力解法的思路和复杂度然后分析瓶颈再提出优化方案。这样做有三个好处第一哪怕最后没写出最优解面试官也能看到你的思维过程第二你有机会在交流中发现自己的思路偏差第三很多面试官喜欢通过引导让你自己优化你先铺垫反而配合得更好。比如遇到“接雨水”这道题完全可以先说暴力解对于每个柱子分别向左向右扫描找到左右最大高度取较小值减去当前高度累加。复杂度O(n²)。接着指出重复扫描是瓶颈可以用前缀最大数组和后缀最大数组优化到O(n)。最后如果面试官要求常数空间再讲双指针法。一步步递进面试官会非常欣赏。5.3 一份我常用的白板答题检查清单给正在准备面试的朋友一份清单我每次模拟面试都是按这个顺序自查先确认输入边界数组为空、长度为1、有负数、有重复元素、整数溢出。再确认输出要求返回索引还是值要求去重吗要求返回具体路径吗复杂度评估如果用了排序、哈希、递归是否超出题目的数据范围限制代码是否能处理空指针/空字符串是否有“更新答案”的位置放置错误比如滑动窗口和DP题答案更新一般放在收缩之后。是否忘记处理Python中的负数取模、整除特性比如//是向下取整可能影响二分查找。我见过不少候选人代码逻辑完全正确但测试用例里边界条件翻车比如二分查找的左右边界写错一个等号或者递归没有终止条件。这些都是能提前规避的低级错误。5.4 面试时的沟通技巧边写边确认避免沉默写算法题时沉默是大忌。即使你思路很清晰面试官也想听到你的口述。拿到题目后我会先说“这道题我联想到XX题型的变体初步思路是XX但需要确认几个边界条件”。然后开始画例子用手动模拟一个小型用例观察结果是否符合预期。再写代码。写的过程简短说一句关键步骤。写完不要立刻说“完成了”而是自己用一两个用例走一遍主动指出代码里的边界条件和时间复杂度。这样既展现了严谨性又给面试官留下好印象。尾巴一些关于刷题效率的个人经验从我刷过的几百道题来看真正有用的不是刷题数量而是每做完一道题后的复盘。我会问自己三个问题这道题属于哪个题型核心的“套路点”是什么如果换一个背景比如把数组换成字符串、把二叉树换成图解法会怎么变想清楚之后同一个题型哪怕没刷过原题也能在面试现场反应过来。这篇所讲的内容其实都是“第二遍刷题”时才会真正吸收的东西。第一遍面试刷题大多数人只顾着看答案、抄代码第三遍刷时又会觉得自己早就会了。第二遍刷才是把题目按题型归类、总结套路的最好时机所以这个系列叫“面试常考算法题(二)”。如果你刷题时也遇到过“看题有印象但一写就卡住”的情况建议你不要急着刷下一道而是回到题型本身把这个类型的核心套路再过一遍。多花这二十分钟比多刷二十道题有用得多。