1. 面试算法题准备的三大误区先避开这些坑这段时间帮几个朋友做模拟面试发现一个很有意思的规律大家刷题量都不少LeetCode动辄两三百题但一到白板写题就露馅。不是不会做而是不知道面试官想听什么、想看什么。这个系列上一期聊了基础数据结构的答题框架这一期我打算聚焦几类真正高频、而且最能拉开差距的题型讲讲从解题思路到面试现场表达的完整链路。先说三个我在面试中反复看到的误区。第一个误区把算法题当成数学题来背。很多候选人准备面试时习惯把每道题的标准解背下来问他们“为什么这里用双指针不用哈希表”答不上来。面试官调整一下输入条件比如“数组变成有序的”“允许重复元素”立刻卡住。这恰恰说明算法题的考察重点从来不是答案本身而是你的分析路径。第二个误区只写代码不聊思路。我曾经面过一个候选人拿到题以后闷头写了十分钟写出来一个能跑的解法但全程没说过一句话。代码是对的但问题在于我不知道他是怎么想到的也无法判断他是不是见过原题。面试本质上是沟通算法题只是沟通的载体。正确做法是动手之前先把思路讲清楚哪怕只说一句“我先想一个暴力解再优化”都可以。第三个误区忽视边界条件和复杂度之外的东西。很多候选人能把主逻辑写对但问他“如果链表为空怎么办”“如果目标值不存在呢”才开始慌慌张张补判断。边界条件的处理往往比核心逻辑更能体现工程素养这也是从“能刷题”到“能面试”的分水岭。这篇文章会围绕几个高频题型展开链表反转、二叉树遍历、滑动窗口、动态规划。每类型我都会从一道经典题出发讲清楚分析路径、面试沟通要点、代码实现以及面试官最常追问的变形。最后再聊一些“没写在题面里”的隐藏加分项。2. 链表反转的多种写法从迭代到递归再到进阶变形链表题是面试中的“送分题”也是“送命题”。说送分是因为链表相关的操作套路相对固定说送命是因为很多人只会背一种写法换个问法就懵。反转链表是链表题里最经典的题目没有之一值得把每一种解法都吃透。2.1 反转链表本体迭代法的指针操作逻辑题目很简单反转一个单链表。很多人在LeetCode上做过这道题但让他们在面试里讲清楚迭代法的每一步反而说不利索。迭代法的核心是三个指针前驱节点 prev、当前节点 cur、后继节点 next。每一步做三件事——保存后继、反转指针、移动指针。def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]: prev None cur head while cur: next_node cur.next # 先保存后继否则断链后找不到 cur.next prev # 反转当前节点指针 prev cur # 前驱移动到当前节点 cur next_node # 当前节点移动到后继 return prev # 最后 prev 就是新链表的头面试时我会建议用一个具体例子走一遍比如1 - 2 - 3 - None。第一轮cur 是 1next_node 是 2把 1 的 next 指向 Noneprev 变成 1cur 变成 2。第二轮cur 是 2next_node 是 3把 2 的 next 指向 1prev 变成 2cur 变成 3。第三轮同理3 的 next 指向 2prev 变成 3cur 变成 None循环结束返回 prev 也就是 3。面试官通常会追问一个问题为什么最后要返回 prev而不是 cur因为循环结束条件是 cur 为 None此时 prev 正好指向原链表的最后一个节点也就是新链表的头节点。这个细节要能讲清楚。2.2 递归解法的理解方式从后往前反转递归解法的代码更短但理解门槛更高。很多人在面试中不敢用递归担心说不清楚。其实递归的核心就一句话先假设子问题已经解决了再处理当前节点和子问题的关系。def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]: if not head or not head.next: return head new_head self.reverseList(head.next) head.next.next head # 把当前节点的后继指针指向自己 head.next None # 断开当前节点原本向后的指针 return new_head拆解一下假设reverseList(head.next)已经返回了以原链表第二个节点为尾的新链表头节点 head。此时 head原头节点还在最前面它的 next 仍然指向原第二个节点。要让 head 变成新链表的尾节点就需要让 head.next 的 next 指向 head即head.next.next head再把head.next置空。面试中用递归的时候建议主动说明递归深度的问题。链表长度不确定时递归深度等于链表长度极端情况下可能栈溢出。如果你能在面试中主动提这一点并说“更稳妥的方案是用迭代”会给面试官留下考虑全面的印象。2.3 反转链表 II区间反转的边界处理LeetCode 92题反转从位置 left 到 right 的链表节点。这是反转链表最常见的变形。思路分为四步找到 left 前驱节点、反转区间内节点、连接前后两端。def reverseBetween(self, head: Optional[ListNode], left: int, right: int) - Optional[ListNode]: dummy ListNode(0, head) prev dummy # 1. 移动 prev 到 left 的前一个节点 for _ in range(left - 1): prev prev.next # 2. 记录区间起点 start prev.next cur start.next # 3. 逐个头插法反转 for _ in range(right - left): next_node cur.next cur.next prev.next prev.next cur cur next_node # 4. 把区间起点接到剩余链表的头部 start.next cur return dummy.next这段代码很多人觉得绕关键是理解头插法每一次循环都把当前节点插入到 prev 的后面区间内靠前的节点不断被“挤”到后面最终实现区间反转。这里最容易出错的是区间 start 节点反转后变成了区间的最后一个节点所以要用start.next cur把它接到后续未反转的部分上。边界情况里left 等于 1 时head 本身会变所以用一个 dummy 哑节点来统一处理这个技巧值得养成习惯。2.4 链表面试题的通用经验链表题说到底是指针操作的熟练度问题。我总结了几个经验第一画图比写代码重要。面试时可以主动在白板/纸上画链表结构把每一步指针变化标出来这个习惯能显著降低出错概率也能让面试官看到你的思路。第二dummy 节点是万能的。只要可能涉及头节点变动就加一个哑节点省去大量 if 判断。第三警惕空指针。操作cur.next.next前一定要确定cur.next不为空。很多链表题的 bug 都出在这里。第四主动讨论环。面试官问“如果链表有环怎么办”其实是在考察你有没有考虑过输入异常的情况。快慢指针判断环是最基础的解法值得牢牢掌握。3. 二叉树题目不只是递归层次遍历与最近公共祖先的实战解法二叉树题在面试中出现频率极高几乎每两场技术面就会遇到一道。但大多数人的准备停留在递归遍历层面遇到稍微需要转化的题目就不知道怎么下手。这一节挑两道高频题展开二叉树的层次遍历、二叉树的最近公共祖先。这两道题从考察维度上互补一个考广度优先的代码组织一个考递归返回值的理解。3.1 层次遍历队列实现的细节与逐层输出题目给定一个二叉树返回其按层序遍历得到的节点值。每一层的节点值按从左到右排列。层次遍历的基本数据结构是队列。关键点在于怎么知道当前层有多少个节点from collections import deque def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]: if not root: return [] res [] q deque([root]) while q: level_size len(q) level [] for _ in range(level_size): node q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level) return res核心技巧是在进入每一层之前先记录当前队列的len(q)这个值就是当前层的节点数。然后用 for 循环只处理这一层的节点新入队的子节点放到下一轮处理。这个解法的时间复杂度是 O(n)每个节点进出队一次空间复杂度是 O(w)w 是二叉树的最大宽度。最坏情况下完全二叉树的最后一层有 n/2 个节点所以空间复杂度是 O(n)。面试中常问的变形有两个。一个是“锯齿形层次遍历”LeetCode 103只要加一个层号判断偶数层把结果反转一下就行。另一个是“右视图”LeetCode 199只需要把每一层的最后一个节点加入结果即可实现上仍然用同一套框架。3.2 最近公共祖先递归返回值里藏着答案LeetCode 236题给定一个二叉树和两个节点 p、q找到它们的最近公共祖先。这道题初看没思路但想明白递归返回值的含义以后解法其实很简洁。def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: if not root or root p or root q: return root left self.lowestCommonAncestor(root.left, p, q) right self.lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right代码很短但理解是关键。我习惯这样跟候选人解释递归函数返回什么返回“以当前节点为根的子树中p 和 q 的最近公共祖先如果子树中只包含 p 或 q 之一则返回那个节点如果两者都不在则返回 None。所以对于当前节点 root先分别在左子树和右子树中查找。如果左子树和右子树各找到一个left 和 right 都不为 None说明 p 和 q 分别位于 root 的左右两侧那 root 就是最近公共祖先。如果只在一侧找到说明两个节点都在同一侧那另一侧的返回结果就是答案。这个递归逻辑很容易写成“先查左再查右”的方式但如果不理解返回值含义面试中一旦被追问就露怯。我建议大家在准备这道题时自己画一棵三层二叉树把 p 和 q 放在不同位置手动模拟递归的每一层返回结果。这个模拟过程比看十遍解法都有效。3.3 二叉树问题的高阶准备方向如果面试岗位对算法要求高二叉树部分建议再准备几个方向从前序/中序序列重建二叉树、二叉树的最近公共祖先的 BST 版本可以利用有序性质做剪枝、以及 Morris 遍历这种空间复杂度为 O(1) 的进阶解法。这些不一定会遇到但准备好的话在面试中属于明显的加分项。4. 滑动窗口题的思考路径从暴力解到O(n)的关键一步滑动窗口是面试中出现频率很高的一类题型尤其在字节、腾讯这类大厂的算法面里几乎是定番。但很多人看到题就套模板换一道题就不会了。问题出在不理解滑动窗口的本质只知道“用两个指针”。这一节我以“无重复字符的最长子串”为例从暴力解推导到滑动窗口把思考路径完整捋一遍。4.1 从问题出发为什么暴力解是O(n^2)题目给定一个字符串 s找出其中不含重复字符的最长子串的长度。最先想到的当然是暴力解枚举所有子串检查每个子串是否有重复字符。枚举子串需要 O(n^2)检查重复字符用哈希集需要 O(k)总复杂度 O(n^3)完全无法接受。优化一下在枚举子串时边遍历边检查把检查降到 O(1)复杂度还是 O(n^2)。这里的关键问题是如何把 O(n^2) 降到 O(n)关键在于发现一个性质如果从 i 到 j 的子串有重复字符那么从 i 到 j1 也有重复字符因此不需要再扩展右边界而是需要移动左边界。这个性质就是滑动窗口的数学基础——单调性。窗口右边界在扩展时碰到重复字符之前窗口内的子串都是无重复的一旦出现重复当前位置再往前没有任何扩展空间只能收缩左边界。4.2 双指针哈希表的完整实现def lengthOfLongestSubstring(self, s: str) - int: char_index {} # 记录字符最近一次出现的下标 left 0 max_len 0 for right, ch in enumerate(s): if ch in char_index and char_index[ch] left: # 如果当前字符在窗口内出现过把左边界移到上次出现位置的下一个 left char_index[ch] 1 char_index[ch] right max_len max(max_len, right - left 1) return max_len这段代码每一行都有讲究。char_index保存的是每个字符最近一次出现的下标。当遇到重复字符时需要判断该字符是否在当前窗口里判断标准是char_index[ch] left。如果重复字符出现在 left 的左边说明它已经被移出窗口了不影响当前子串。一个容易忽略的细节是每次更新 left 时为什么不显式地把窗口内其他字符从哈希表里删掉答案就是上面的判断条件。哈希表记录的是字符最近出现的位置当 left 跳过去以后那些旧的记录自然会被 left拦截不会进入窗口范围。这就是空间换时间的一个典型做法不需要额外维护一个动态集合直接将字符位置存进去就行。4.3 滑动窗口的适用条件与常见变形滑动窗口不是万能的。它的适用条件可以总结为一句话问题存在单调性窗口扩大的过程中一旦某个约束被破坏进一步扩大窗口不可能让结果更好。在这个前提下才能用收缩左边界来维持窗口有效性。常见变形整理一下题干特征思路方向代表题目最长子串/子数组且要求无重复哈希表记录位置遇重收缩无重复字符的最长子串窗口内至多 k 个不同字符哈希表计数计数为新字符时收缩至多包含 K 个不同字符的最长子串最小覆盖子串计数 窗口内匹配数量最小覆盖子串字符串排列/异位词固定窗口大小 计数比较字符串的排列面试中遇到滑动窗口的题我建议按这个顺序走先说暴力解再说单调性最后写滑动窗口。因为面试官想听的是你怎么从暴力解推导出优化方案而不是你直接默写模板。5. 动态规划的入门与进阶最长上升子序列的状态定义与优化动态规划是很多人的老大难。我的经验是动态规划的难点不在代码而在状态定义。只要状态定义清楚了递推公式和初始化都水到渠成。这一节用“最长上升子序列”来拆解这个过程从 O(n^2) 到 O(n log n)把优化的思路讲明白。5.1 状态定义dp[i] 到底应该表示什么题目给定一个整数数组 nums找到其中最长严格递增子序列的长度。子序列可以不连续。很多人的第一反应是用二维 dp 表示“以某个位置结尾、并且以某个值结尾的子序列长度”但显然复杂。正确做法是dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。这个状态定义的关键是在于“以 nums[i] 结尾”。为什么要加这个限定因为这样才能建立递推关系dp[i] 可以通过比 nums[i] 小的前面的元素推导出来。如果只定义“前 i 个元素的最长上升子序列长度”那无法知道最后一个元素的值递推就断了。def lengthOfLIS(self, nums: List[int]) - int: n len(nums) if n 0: return 0 dp [1] * n # 每个位置至少可以自己作为子序列 for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)这个解法的核心就是对每个 i遍历所有 j i如果nums[j] nums[i]说明 nums[i] 可以接在 nums[j] 的后面那么dp[i]的候选值就是dp[j] 1。取最大值即可。初始化时每个 dp[i] 至少是 1因为任何单个元素都是一个长度为 1 的递增子序列。这是动态规划里最简单的初始化但很多人会漏。时间复杂度 O(n^2)在 n 1000 时可以接受。但如果数据规模到 10^5就需要更高效的解法。5.2 进阶O(n log n) 的贪心二分优化优化的思路很巧妙需要维护一个数组 tails其中 tails[i] 表示长度为 i1 的递增子序列中最小的末尾元素值。更新规则是如果nums[i] tails[-1]直接追加最长长度加 1否则在 tails 中找到第一个大于等于 nums[i] 的元素用 nums[i] 替换它。import bisect def lengthOfLIS(self, nums: List[int]) - int: tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)这个解法很多人背得下来但说不清为什么对。我这样理解tails 数组不一定是一个真实的上升子序列但它记录了一个“潜力股”信息——对于每一个可能的长度它的最小末尾是谁。贪心的地方在于末尾元素越小后续元素能接上去的概率越大。所以每次遇到新元素都尝试把它放在能接的位置如果它比当前末尾小就更新对应长度的末尾值。为什么用 bisect_left 而不是 bisect_right因为严格递增等于的情况下不能接在后面需要用新的值替换旧值。这个细节只要在面试中能解释清楚对方就会认为你是真的理解而不是背下来的。5.3 动态规划的学习路径从状态定义到常见模型面试中动态规划的题基本集中在几个模型线性 DP最长上升子序列、最大子数组和、打家劫舍区间 DP最长回文子序列、戳气球背包问题0-1 背包、完全背包面试较少但笔试常考状态机 DP买卖股票的最佳时机全系列准备的时候先把线性 DP 吃透因为它是基础。特别是“以 i 结尾”和“前 i 个元素”这两种状态定义的区别很多题都绕不开这个选择。面试时如果遇到 DP 题可以主动说一句“我先定义状态再写递推”。这个顺序本身就是一种展示成熟问题解决能力的信号。6. 没写在题面里的加分项边界条件、复杂度分析和高阶收尾前面几节聚焦具体题型但真正让面试表现从“能做题”升级到“面试高分”的往往是题面之外的东西。这一节聊几个我在面试中非常看重的细节也建议大家平时练习时就有意识地培养。6.1 边界条件先讲再写比写完再补更专业我见过不少候选人写代码前完全不提边界条件写完发现漏了再补。虽然最终代码可能对了但体现出来的思考习惯不够职业。更专业的做法是拿到题以后在动手之前用一两句话把边界条件说清楚比如“我先考虑空输入和单个元素的情况”然后写代码时把这些判断放在入口处。常见的边界条件清单输入为空空数组、空字符串、空链表、空树数组/字符串长度是 1很多递归或贪心解法在小数据下有特殊行为输入含重复元素会不会影响有序性、去重逻辑目标值超出范围查找类问题要指定返回策略数值溢出涉及大数运算时考虑用 64 位或 Python 无限制特性这些清单不需要背但平时刷题时养成“每道题先想输入范围”的习惯面试时自然就能说出来。6.2 复杂度分析不是背结论而是会推导很多候选人被问时间复杂度时直接回答“O(n^2)”然后没有下文。稍微好一点的是说一句“因为嵌套了两层循环”但也就到此为止。其实面试官更期待听到的是“为什么是这个复杂度空间复杂度是多少能否优化”。以第 4 节的最长无重复子串为例完整的口述应该是时间上每个字符最多被 left 和 right 指针各访问一次所以是 O(n)。空间上哈希表最多存储 n 个字符的键值对所以是 O(n)。这样从指针移动次数和存储规模两个角度推导比单纯背结论好得多。如果面试官追问“能不能把空间复杂度降到 O(1)”可以直接回答对于纯 ASCII 字符集可以用一个长度为 128 或 256 的数组代替哈希表这样空间复杂度就是 O(1)。这个答案能体现出你理解数据结构的选择会影响空间的本质。6.3 面试现场的沟通节奏与收尾最后一个加分项是面试节奏的把控。我建议的节奏是前 2 分钟讲思路中间 5 到 8 分钟写代码最后 2 分钟检查边界和数据验证。讲思路时不要只讲最终解法可以说一句“我先想到的是暴力解但它的复杂度是……我们可以优化为……”。这个叙述比直接写最优解更能展示思维能力。写完后主动提出“我可以用一个简单的例子走一遍”然后自己走一个非平凡的用例。这个过程不要等面试官要求才做主动做有很强的加分效果。收尾时可以简单总结这道题的关键点比如“这题的核心是单调性所以可以用滑动窗口”。不需要长篇大论两三句话即可。这个习惯能帮助面试官快速记录你的表现也会让讨论更有深度。7. 从刷题到面试写在准备路上的几点体会坦白说我的算法基础不算好本科阶段的数据结构课也就是勉强及格的水平。真正开始有明显的提升是从我决定把“刷题”变成“思考”开始的不再追求做题的数量而是把每道题吃透尝试用不同的方法去解然后从面试官的角度去问自己“如果我是面试官我会怎么追问这道题”。比如反转链表我不仅会迭代和递归两种写法还会思考为什么迭代法的空间复杂度是 O(1) 而递归是 O(n)。再比如最长上升子序列我不仅会两种解法还会想清楚贪心binary search 的状态定义背后的逻辑。想清楚这些之后做题速度反而变慢了但面试时的信心和表达顺畅度大幅提升。如果这篇文章能给你一个具体的建议那就是准备面试算法题时把重心从“这题怎么做”转移到“我如何向面试官讲清楚思路”。多练习边说边写多给自己提“面试官可能会问什么”。当你习惯了这种表达方式笔试和面试都不再是背题而是一种自然的交流。这一系列下一期我会聊一些更进阶的主题到时候见。