很多准备面试的朋友都来问我算法题到底怎么刷才有效率。上一期我聊了链表和栈的常见套路这期继续把面试里出镜率最高的一批题拎出来用Python逐一拆解。这次重点放在双指针、动态规划、二叉树、排序与二分查找这四类题型上覆盖了绝大多数公司技术面的算法环节。无论你是刚刷题不久的新手还是已经在冲刺大厂的老手这篇文章都值得花半小时细读一遍。我写这系列文章的原则一直没变不是把答案摆出来就完事而是把每道题背后的思维过程、边界条件、复杂度推导讲清楚。面试官真正想看的不是你会不会背题解而是你能不能举一反三把解题思路迁移到新问题上。所以下面每道题我都会拆到“为什么这么做”的层面再附上可复现代码和易错点。1. 双指针从暴力到线性的思维跃迁1.1 核心场景先说清楚什么时候该想到双指针双指针能解决的问题有一类很典型的外观特征数组是有序的或者问题要求你找出满足某种条件的两个元素。为什么要强调有序因为双指针的核心竞争力就是利用有序性让指针移动有了明确方向从而把暴力枚举的O(n²)复杂度降到O(n)。以经典的有序数组两数之和为例def two_sum(numbers, target): left, right 0, len(numbers) - 1 while left right: current numbers[left] numbers[right] if current target: return [left 1, right 1] elif current target: left 1 else: right - 1 return []这个解法的关键在于当和小于target时左指针右移能让和变大当和大于target时右指针左移能让和变小。每一步都排除了一整行或一整列的可能性所以最多遍历n个元素就完成。这就是双指针的“为什么”所在——它不是碰运气而是每一步都基于有序性做出确定性决策。同类题还有三数之和、盛最多水的容器、接雨水。记住一个判断标准如果题目涉及“找两个元素”且数组可以排序优先往双指针方向想。我在面试中遇到不少候选人明明写对了暴力解法却连“能否优化”这个问题都没主动思考这其实很吃亏。1.2 双指针的三种变体与边界条件实战双指针不止对撞指针一种形态面试中常见的是快慢指针和对撞指针。快慢指针的经典场景是数组原地去重def remove_duplicates(nums): if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 1这道题的边界条件设计值得反复琢磨为什么slow从0开始fast从1开始因为数组已排序第一个元素必然保留slow指向的是最后一个不重复元素的位置。当fast遇到新值时slow先前进再写入保证前slow1个元素都是不重复的。实测下来很多人在“返回值是slow还是slow1”上栽跟头记住slow指向的是索引长度要加一。对撞指针的另一个高频考题是判断回文字符串。核心点在于while left right的循环条件以及遇到不匹配时是否允许跳过字符。多数变形题会在“最多删除一个字符”上做文章这时需要写一个辅助函数判断子串是否回文。我建议把这类题模板化先写基础版双指针再根据题目要求增加条件分支逻辑会清晰很多。2. 动态规划面试中的“套路变现”2.1 经典题型精讲爬楼梯与打家劫舍动态规划是算法面试的分水岭。很多候选人谈DP色变其实面试常考的DP题在思维模式上有高度一致性定义状态、写转移方程、确定初始条件、确定遍历顺序。我以爬楼梯这道入门必考题为例def climb_stairs(n): if n 2: return n dp [0] * (n 1) dp[1], dp[2] 1, 2 for i in range(3, n 1): dp[i] dp[i - 1] dp[i - 2] return dp[n]为什么dp[i] dp[i-1] dp[i-2]因为到达第i阶楼梯最后一步要么跨1阶从i-1来要么跨2阶从i-2来。这就是“最后一步分析法”是DP入门最核心的思维工具。面试中遇到不熟悉的DP题先问自己最后一步有哪些可能性把可能性写出来状态转移方程基本就出来了。打家劫舍是爬楼梯的直接进阶版def rob(nums): if not nums: return 0 if len(nums) 1: return nums[0] dp [0] * len(nums) dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, len(nums)): dp[i] max(dp[i - 1], dp[i - 2] nums[i]) return dp[-1]这里的状态转移方程为什么要max因为对于第i间房子你有两个选择不偷它那么最大金额是dp[i-1]偷它那么前一间不能偷金额是dp[i-2] nums[i]。在两种策略里取最大值就是当前状态的最优解。这个“选或不选”的框架几乎贯穿所有线性DP题。2.2 状态压缩与面试中的空间优化要求很多面试官会在你写对DP之后追问一句“空间能优化吗”这不是刁难而是在考察你对状态依赖关系的理解。爬楼梯中dp[i]只依赖dp[i-1]和dp[i-2]根本不需要数组用两个变量滚动即可def climb_stairs_optimized(n): if n 2: return n prev, curr 1, 2 for _ in range(3, n 1): prev, curr curr, prev curr return curr打家劫舍同理只要保留前两个状态def rob_optimized(nums): prev, curr 0, 0 for num in nums: prev, curr curr, max(curr, prev num) return curr从O(n)空间优化到O(1)空间代码量反而更少。我个人在面试时的建议是先把数组版本写出来把逻辑讲清楚再主动做空间优化。这比一上来就写滚动变量更能展示你的思维过程。另外DP题目写完一定要手动走一遍小样例比如n3、n4确认边界条件没问题再提交。3. 二叉树算法面试的必考阵地3.1 遍历框架递归与迭代的取舍二叉树几乎是算法面试的“保留节目”十场面试至少有三四场会出现。考察点集中在遍历、路径、深度、公共祖先等方面。递归写法简洁优雅但面试官有时会要求你写迭代版本以此考察你是否真正理解遍历的底层过程。先看递归模板以前序遍历为例def preorder(root): if not root: return [] return [root.val] preorder(root.left) preorder(root.right)这个模板万金油到可以套用前中后三种遍历区别只是根节点值加入列表的时机。但递归写法的缺点是当树很深时可能会栈溢出迭代写法用显式栈可以规避这个问题def preorder_iterative(root): if not root: return [] result, stack [], [root] while stack: node stack.pop() result.append(node.val) if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result注意迭代版入栈顺序是“先右后左”因为栈是LIFO结构想要先处理左子树就必须让左子节点后入栈。这类细节不是靠背能解决的要自己动手模拟一次出栈入栈过程才能彻底明白。层序遍历BFS则是另一套模板依托队列实现from collections import deque def level_order(root): if not root: return [] result, queue [], deque([root]) while queue: level [] for _ in range(len(queue)): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result这里的for循环配合len(queue)是精髓每次循环处理当前层的全部节点循环结束后queue里正好是下一层的全部节点。很多候选人写层序遍历时会把层内数组搞乱问题几乎都出在没有固定当前层的数量。3.2 高频综合题翻转二叉树与最近公共祖先翻转二叉树因为某位知名程序员的一句话而火出圈它本身也是一道非常考察递归理解力的题def invert_tree(root): if not root: return None root.left, root.right root.right, root.left invert_tree(root.left) invert_tree(root.right) return root核心观察是对于每个节点只要交换它的左右子树再递归处理左右子树就完成了整棵树的翻转。这里不需要考虑“先交换还是后交换”因为子树内部的翻转是独立任务与当前层的交换顺序无关。这种“局部操作递归处理子问题”的结构是大量树形DP和递归题的基础。最近公共祖先LCA是另一道考察理解深度的题def lowest_common_ancestor(root, p, q): if not root or root p or root 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这道题的思考路径是在左右子树里分别找p和q如果两边都找到了说明当前节点就是最近公共祖先如果只有一边找到就把这一边往上传递。递归返回值的语义一定要定义清楚要么返回p/q节点要么返回最近公共祖先要么返回None。我见过很多候选人卡在return逻辑上其实根源是把递归的返回值语义搞混了。4. 排序与二分看似简单其实暗藏杀机4.1 手写快速排序越基础的题越能拉开差距手写快排是很多公司的“送分题”但也是“送命题”。方法人人会背边界条件却常常写错。我给出一个结构化清晰的实现def quick_sort(nums, left, right): if left right: return pivot nums[left] i, j left, right while i j: while i j and nums[j] pivot: j - 1 nums[i] nums[j] while i j and nums[i] pivot: i 1 nums[j] nums[i] nums[i] pivot quick_sort(nums, left, i - 1) quick_sort(nums, i 1, right) return nums这里选择了左端点作为pivot挖坑法在每一轮中把小于pivot的值填到左边坑位、大于pivot的值填到右边坑位最终i和j相遇的位置就是pivot的最终位置。关键要点是最后一步覆盖回去。很多候选人递归部分写对了但忘了把pivot写回相遇位置导致排序结果莫名其妙。另一个高频考察点是复杂度分析。快排的平均时间复杂度是O(n log n)最坏是O(n²)最坏情况发生在每次选到的pivot都是当前区间最小或最大值时比如对已经有序的数组用左端点做pivot。所以很多工业级排序实现会采用随机pivot或三数取中法。面试时如果能主动提到这一点会是一个明显的加分项。4.2 二分查找的边界问题一个模板应对所有变体二分查找的代码不过十行但能一遍写对的人寥寥无几。核心问题出在边界条件的判定到底是while left right还是while left rightmid到底加不加1下面这个模板我推荐直接背下来def binary_search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1为什么用left (right - left) // 2而不直接写(left right) // 2因为当left和right都很接近int上限时两者相加可能溢出。虽然面试很少真的考察溢出但写出这种写法能体现工程经验的积累。这个模板的边界逻辑是当缩小区间时mid已经被检查过了所以搜索区间必须是mid 1或mid - 1否则可能死循环。比基础版更难的是旋转排序数组中的搜索LeetCode 33def search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid if nums[left] nums[mid]: if nums[left] target nums[mid]: right mid - 1 else: left mid 1 else: if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return -1这种题的转机在于虽然整个数组不是有序的但二分后的两部分中必有一部分是有序的。只要判断target是否落在有序部分的范围内就能决定搜索方向的走向。逻辑清晰之后解法并不难真正的陷阱是在判断“target是否在有序区间内”时容易把和写混。我建议刷这类题时把所有比较条件逐一用“哨兵值”代入测试一遍。5. 常见问题与面试避坑实录5.1 算法面试中最容易翻车的几个瞬间这些年我以面试官身份点评过的候选人不少以候选人身份被点评的经历也有。综合来看算法面试翻车往往不是不会做而是几个低级问题反复出现。第一个是跟题目确认边界条件前就匆匆动手。比如输入为空数组、数组只有一个元素、目标值不在数组中这些场景必须主动向面试官确认或至少自己在代码里显式处理。第二个问题是不用手动走样例就开始写代码。面试时时间压力大但花30秒在草稿纸上跑一遍小例子能帮你规避至少一半的边界残次品。我通常建议候选人先写出[1,2,3]、[3,2,1]、[1]这样三个典型样例在脑内执行一次自己的代码路径。第三个问题是复杂度分析含糊其辞。写完代码后面试官几乎必然会问时间复杂度和空间复杂度。如果回答得犹豫甚至把O(n²)说成O(n log n)前面的印象分都会折损。正确的做法是每写完一题主动说出“时间复杂度O(n)空间复杂度O(1)因为只用到了常数个额外变量”这是最基础的自我复盘。还有一个高频问题代码写到一半发现思路不对。很多候选人会选择硬着头皮写完结果越写越乱。更聪明的做法是停下来跟面试官说“我当前的方案在某个边界上处理不了我换个思路”然后重新开始。面试官更看重的是你能否及时发现并纠正方向而非你能否一头闷到底。5.2 面试官到底在考察什么能力回到本质面试官通过算法题在考察什么我认为是三个维度而不是“会不会做这一道题”。第一个维度是问题拆解能力你能不能把一个复杂问题拆成若干个子问题复用已经掌握的模式。第二个维度是代码表达能力同样的思路有的人写得结构化清晰、变量命名语义明确有的人写得一团乱麻。第三个维度是沟通和推演能力你在解题过程中是否愿意说明思考过程是否能在提示下快速修正方向。所以刷题的时候与其闷头刷三百道不如精选每个专题的二三十道经典题把每一道题从思路到边界到复杂度都讲给“假想面试官”听。我认识不少朋友用这个方法快速建立了算法信心核心原理是表达的过程会逼迫你把模糊的理解变成严格的逻辑链条。5.3 常见问题速查表问题场景常见错误正确姿势双指针循环条件while left right 导致索引越界对撞指针用 left rightDP数组初始化忘记处理n0或n1的边界进入循环前先补齐前两个状态二叉树递归忘记空节点返回递归入口先写 if not root: return二分查找mid计算溢出或死循环用 left (right-left)//2快排收尾忘记把pivot写回相遇位置挖坑法必须最后覆盖一句排序稳定性没搞清稳定与不稳定快排不稳定归并稳定要能解释原因我在实际带人的过程中发现把错误记录成表格比反复刷题更有效。每做错一道题就更新这张表考前翻一遍能省下大量低效的重复劳动。6. 算法思维的持续提点6.1 从“会做题”到“会想题”的转变面试题目千变万化但底层的算法思想就那么几十种。当你刷到一定数量后会发现新题往往只是旧模板换了层壳。比如“最长递增子序列”和“接雨水”看起来毫无关系但一个用DP状态记录以当前元素结尾的长度一个用左右扫或单调栈维护雨水累积量思想内核都是通过定义状态记录“已走过位置的信息”。我自己在面试中非常看重候选人能否在一个不熟悉的问题上主动靠拢已知模式。比如看到求最大值就问能不能用DP看到找满足条件的最短子数组就问能不能用滑动窗口看到有序数组就问能不能用双指针或二分。这种“模式匹配”能力是算法面试的真正分水岭也是从“会做题”走向“会想题”的标志。6.2 刷题节奏与复盘方法论刷题不是拼数量而是拼质量。我建议的节奏是每个专题集中突破两周每天三道经典题每道题给自己四十分钟思考时间超时再看题解。题解不是看个答案就完事要复盘三件事为什么我没想到、题解的核心洞察是什么、这道题还能迁移到哪里。写好自己的题解笔记定期回看是收益最高的投入之一。关于Python在算法面试中的使用有一个技巧值得提一下善用语言内置的数据结构但必须知道它们的复杂度。比如deque的popleft是O(1)而list.pop(0)是O(n)。在层序遍历中使用前者是标准操作用后者则在数据量大时明显变慢。还有heapq实现堆、functools.lru_cache实现记忆化搜索都是面试中可以主动使用的利器但前提是你能解释清楚它们各自的开销。我个人这两年刷题后最大的感悟是算法题没有捷径但有方法。把每一个专题的核心套路吃透把每道题背后的“为什么”讲清楚比盲目追求题量有效得多。面试前的最后一晚与其刷新题不如把错题本和复杂度速查表翻一遍让大脑在放松中保持对高频模式的敏感度。这样进入面试场的时候你的思维是清醒的状态是从容的那些刷过的题才会在关键时刻自然涌现出来。