企业官网建设流程全解析

很多人刷算法题，喜欢按题目顺序一遍遍刷，刷完就忘，面试时看到原题都认不出来。我自己也经历过这个阶段，后来才开始按题型总结套路，发现面试考来考去就是那些高频模型。上一篇讲了链表、哈希和双指针，这篇继续往下聊，重点放在真正决定面试成败的几类题型上：排序与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[l+1:lt] < pivot gt = r + 1 # nums[gt:r+1] > 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:start+min_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，就按遍历顺序把子节点压栈（注意压栈顺序），再把自己标记为visited=True重新压栈；如果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)的贪心+二分：维护一个数组tails，tails[i]表示长度为i+1的上升子序列的最小末尾值。遍历每个数，用二分查找在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]到底代表什么，稍微搞错就会越界。更严重的是“编辑距离”这类二维DP，dp[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. 先确认输入边界：数组为空、长度为1、有负数、有重复元素、整数溢出。
2. 再确认输出要求：返回索引还是值？要求去重吗？要求返回具体路径吗？
3. 复杂度评估：如果用了排序、哈希、递归，是否超出题目的数据范围限制？
4. 代码是否能处理空指针/空字符串？
5. 是否有“更新答案”的位置放置错误？比如滑动窗口和DP题，答案更新一般放在收缩之后。
6. 是否忘记处理Python中的负数取模、整除特性？比如//是向下取整，可能影响二分查找。

我见过不少候选人，代码逻辑完全正确，但测试用例里边界条件翻车，比如二分查找的左右边界写错一个等号，或者递归没有终止条件。这些都是能提前规避的低级错误。

5.4 面试时的沟通技巧：边写边确认，避免沉默

写算法题时，沉默是大忌。即使你思路很清晰，面试官也想听到你的口述。拿到题目后，我会先说“这道题我联想到XX题型的变体，初步思路是XX，但需要确认几个边界条件”。然后开始画例子，用手动模拟一个小型用例，观察结果是否符合预期。再写代码。写的过程简短说一句关键步骤。写完不要立刻说“完成了”，而是自己用一两个用例走一遍，主动指出代码里的边界条件和时间复杂度。这样既展现了严谨性，又给面试官留下好印象。

尾巴：一些关于刷题效率的个人经验

从我刷过的几百道题来看，真正有用的不是刷题数量，而是每做完一道题后的复盘。我会问自己三个问题：这道题属于哪个题型？核心的“套路点”是什么？如果换一个背景，比如把数组换成字符串、把二叉树换成图，解法会怎么变？想清楚之后，同一个题型哪怕没刷过原题，也能在面试现场反应过来。

这篇所讲的内容，其实都是“第二遍刷题”时才会真正吸收的东西。第一遍面试刷题，大多数人只顾着看答案、抄代码，第三遍刷时又会觉得自己早就会了。第二遍刷，才是把题目按题型归类、总结套路的最好时机，所以这个系列叫“面试常考算法题(二)”。如果你刷题时也遇到过“看题有印象，但一写就卡住”的情况，建议你不要急着刷下一道，而是回到题型本身，把这个类型的核心套路再过一遍。多花这二十分钟，比多刷二十道题有用得多。