《面试常考算法题(二)》已经来了。上一期聊了几个基础方向评论区不少人说“思路能懂但一到面试现场就卡住”。我特别理解这种感觉所以这一期我换了个讲法不只给你题目和解法更让你看到拿到一道题之后大脑应该怎么一步步运转。今天挑的这四道题基本是近三年中小厂到中大厂笔试面试里出现频率最高的几个类型每一道都能讲出很多门道。先说明一下这系列文章默认你用 Python 写算法。不是 Python 就一定比 Java、C 好而是 Python 的表达足够接近伪代码可以让你把注意力放在思路推导上而不是陷入指针、内存这些实现细节里。尤其对于面试场景你要让面试官一眼看懂你在做什么Python 天然的简洁优势非常明显。1. 先聊聊算法面试到底在考什么面试官让你写算法题真的只是想看你会不会背题吗当然不是。我面过不少人也被人面过慢慢摸清了这道环节的真实意图一考逻辑思维的清晰度二考代码落地能力三考沟通和应变能力。很多同学有一个误区觉得只要刷题数量上去了面试就没问题。于是照着题单从第一题刷到第五百题一道题看五分钟没思路就直接翻题解。这种刷法的效率低到什么程度呢低到你刷完一百道之后遇到一道从没见过的变形题依然毫无头绪。真正有效的准备方式是抓“解题套路”。算法题看起来千变万化但剥开外壳内核就那么几十种枚举、递归、分治、二分、双指针、滑动窗口、回溯、动态规划、贪心、图论、并查集、字典树、堆、单调栈……你把每一个套路的适用场景和思维路径吃透再遇到新题的时候本质上是“往已知模型上套”的过程。1.1 面试官真正想看的能力模型在真实面试流程里算法题通常不是孤立的。面试官会先让你说思路再让你动手写最后让你跑几个测试用例。如果你只闷头写代码不解释面试官其实很难判断你是真的懂了还是背的。我自己的体会是算法面试要呈现的是以下三条线第一条线是思路推导。你要能说清楚“为什么想到用这种算法”“暴力解是什么样”“哪些条件让我决定做优化”。哪怕最后没写出来思路清晰的人往往也比闷头写对的人分数高。第二条线是代码实现。写到什么程度算好第一不能有明显语法错误第二边界条件要处理干净第三代码风格要整洁。全篇给变量起名成 a、b、c 的这种就算AC了面试官也会皱眉头。第三条线是验证能力。写完代码之后主动举测试例子跑一遍自己的逻辑尤其是空输入、单元素、全相同元素这些边界场景。这种习惯非常加分。1.2 为什么建议用 Python 刷题有些人总觉得 C 刷题显得“更硬核”但我的观点是面试的时间就这么点你的精力应该花在呈现解题思路上而不是花在手动管理内存和迭代器上。Python 的语言特性天然适合算法表达主要有这几点优势。第一点Python 的列表、字典、集合等内置结构非常接近算法抽象层。比如“判断元素是否出现过”你不需要像 C 那样纠结于 unordered_set 还是 set直接 set 搞定时间复杂度的讨论也清晰得多。第二点Python 支持多重赋值、切片、列表推导式很多代码可以写得很短且可读性高。比如交换两个变量就一行a, b b, a这在写排序算法的时候尤其舒服。第三点是当你讲思路的时候Python 代码几乎可以直接贴在思路后面中间没有“翻译”的损耗。面试官看着你写的代码再听你的讲解他听到的是算法逻辑本身而不是“C 里这个 vector 怎么初始化”之类的实现噪音。不过有一点要提醒用 Python 不代表可以不关心复杂度。Python 本身就是一门较慢的语言你的算法如果复杂度不理想面试官很容易看出来所以复杂度分析反而是重点加分项。2. 高频题一滑动窗口套路拿下“无重复字符的最长子串”这道题是 LeetCode 第 3 题属于经典中的经典。如果说有哪道题值得你背到肌肉记忆那这道题一定排前三。真题版本有个变形是“找最长不含重复字符的子串的长度”本质上完全一样。题目给你一个字符串比如s abcabcbb要你找出其中不含有重复字符的最长子串的长度。所谓子串就是连续的一段字符。abc是子串acb不是因为不连续。2.1 从暴力解开始找感觉拿到这道题不要一上来就想着写最优解先想暴力解。暴力解的方式是枚举每个左端点 i然后从 i 开始向右扩把字符逐个加入集合直到遇到重复字符停止记录当前最长长度。def length_of_longest_substring(s: str) - int: n len(s) ans 0 for i in range(n): seen set() for j in range(i, n): if s[j] in seen: break seen.add(s[j]) ans max(ans, j - i 1) return ans这个暴力解的时间复杂度是 O(n²)在字符串长度稍长时就会超时。但它告诉了我们一个关键信息这个问题的本质是“维护一个无重复字符的滑动窗口”而且窗口是向右单调移动的。2.2 滑动窗口的思维转变暴力解效率低的根本原因在于每次左端点 i 移动时我们都重新从 i 开始扩展右端点之前已经扫描过的字符信息被丢掉了。聪明一点的做法是左指针和右指针都只向右移动不回头。右指针负责探索新字符左指针负责在发现重复时收缩窗口。整个过程就像一条贪吃蛇头往前探索尾在后面跟进。具体思路是这样的。我们维护一个 set用来记录当前窗口内有哪些字符。右指针逐步向右移动每遇到一个新字符就检查它是否在 set 里如果不在说明可以扩展窗口把这个字符加入 set更新答案。如果在说明当前窗口已经不能继续扩展了需要移动左指针把左指针指向的字符从 set 中移除直到把那个重复的字符移出窗口为止。代码实现看起来是这个样子def length_of_longest_substring(s: str) - int: n len(s) left 0 seen set() ans 0 for right in range(n): while s[right] in seen: seen.remove(s[left]) left 1 seen.add(s[right]) ans max(ans, right - left 1) return ans这里最精髓的地方在于while s[right] in seen。重复的元素可能不只有一个比如窗口里是a, b, c, b你只删一个左边界不一定能删掉重复的b所以要循环地删直到把那个与s[right]相同的字符从集合里挪出去。2.3 一个容易踩的坑别用 remove 而忽略重复值这里要注意一个细节set.remove()在元素不存在时会抛异常。上面代码里因为有while条件保证元素必然存在所以安全。但如果你对字符串处理的经验不足容易在其他题目里写出不安全的 remove 调用。另外严格来说这个写法的时间复杂度是 O(n)因为左右指针都只遍历了字符串一次内层 while 循环总共执行的次数也以 n 为上限。空间复杂度 O(min(m, n))m 是字符集大小。2.4 滑动窗口的通用套路总结这道题只是滑动窗口的入门题。只要你吃透了它的“维护窗口内性质 右扩左缩”的框架后面很多题都能直接套最小覆盖子串、字符串排列、替换后的最长重复字符……核心动作都是一样的区别只在于窗口内维护的信息是什么、何时收缩窗口。面试官接下来极大概率会让你变形比如让你返回最长子串的起始位置或者要求不借助 set 而用字典记录字符最后出现的位置。你都可以在原解法上改。用字典的版本可以做到左指针直接跳到重复字符的下一位这是进阶优化但对理解要求更高。先用 set 把框架吃透能把这道题的每一步讲清楚比背一个更“高级”但讲不明白的写法要好得多。3. 动态规划入门到熟练三分钟理清“打家劫舍”动态规划是算法面试里最容易让人恐惧的模块。但说实话面试常考的动态规划题没有你想象的那么难大部分都集中在几种典型模型上一维 DP、二维 DP、背包问题变种、区间 DP。今天选的“打家劫舍”就是最典型的一维 DP 题LeetCode 第 198 题。题目本身是个小故事转换来的你是一个猎人要偷一排房屋里的财物每间房屋有不同数量的宝物但是不能偷相邻的两间屋子否则会触发警报。请问一次最多能偷多少。3.1 怎么判断这道题要用动态规划拿到任何一道题第一步都是判断题型。看到“不能相邻”“最大价值”这类词你就要有“这可能是动态规划”的直觉。判断标准也很简单问题的决策会影响之后的决策且子问题之间有重叠。具体到打家劫舍你在决定要不要偷第 i 间房屋时需要考虑前面偷到了哪间。如果偷了第 i-1 间那第 i 间就不能偷如果没偷第 i-1 间就可以偷。这是一个有后效性的决策问题天然符合 DP 的特征。3.2 状态定义和转移方程推导动态规划的难点在于定义状态。这里可以定义dp[i]表示“偷窃到第 i 间房屋时能够获得的最大金额”。那么对第 i 间房屋你有且仅有两个选择选择偷它那么第 i-1 间不能偷收益是dp[i-2] nums[i]。选择不偷它那么收益就是前 i-1 间的最大值即dp[i-1]。两者取最大就得到状态转移方程dp[i] max(dp[i-1], dp[i-2] nums[i])基础条件就两个只有一间房时答案就是nums[0]有两间房时答案是max(nums[0], nums[1])。def rob(nums: list[int]) - int: n len(nums) if n 0: return 0 if n 1: return nums[0] dp [0] * n dp[0] nums[0] dp[1] max(nums[0], nums[1]) for i in range(2, n): dp[i] max(dp[i - 1], dp[i - 2] nums[i]) return dp[-1]3.3 空间优化从 O(n) 到 O(1) 的思维跨越很多人在这一步就停了觉得能 AC 就行。但如果你真的在面试面试官一定会追问一句“还能优化吗”。动态规划数组不是必须的因为dp[i]只依赖dp[i-1]和dp[i-2]也就是说你只需要保存前两个状态不需要保留整个数组。def rob(nums: list[int]) - int: prev2 0 prev1 0 for num in nums: cur max(prev1, prev2 num) prev2, prev1 prev1, cur return prev1这段代码一开始看可能有点绕。实际上prev1表示“截止到上一间的最大收益”prev2表示“截止到上上间的最大收益”。每遍历一个新值就计算当前最大收益然后更新这两个变量。这样空间复杂度从 O(n) 降低到 O(1)。3.4 面试追问的多种变形这个题目在面试里出现的概率极高而且面试官通常不会只让你写基础版。最常见的变形是“房屋围成一圈”也就是首尾不能同时偷。解法也很清晰把环形拆成两个线性问题一个不含第一间房一个不含最后一间房分别用打家劫舍的解法取最大值。def rob_cycle(nums: list[int]) - int: if len(nums) 1: return nums[0] return max(rob(nums[:-1]), rob(nums[1:]))就这么几行。把一个大问题拆成两个已经解决过的子问题这种思维其实比背代码重要得多。面试官就是想看到你有这种“把陌生问题转化成熟悉问题”的能力。4. 一题吃透回溯算法全排列里藏着递归的精髓回溯算法是面试里的另一座大山而“全排列”是回溯算法最经典、最基础的代表题目。LeetCode 第 46 题题目简洁给你一个不含重复数字的数组 nums返回它的所有全排列。比如nums [1, 2, 3]输出是[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]。4.1 回溯的直觉从哪里来请你想象一下你要手工列出[1, 2, 3]的全排列你会怎么做大概率是先固定第一个位置是 1然后对剩下的[2, 3]做全排列再把第一个位置换成 2对剩下的[1, 3]做全排列。这个“固定一个递归处理剩下的”过程就是回溯算法的骨架。回溯的本质就是深度优先搜索DFS在解空间树上的遍历。每走一步就做出一个选择如果发现此路不通或者已经走完就回退到上一步撤销选择再尝试其他分支。4.2 回溯题的标准模板回溯题有一个万能的模板大体上是这样的def backtrack(路径, 选择列表): if 满足结束条件: 将路径加入结果集 return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择套到全排列上代码写出来是这样def permute(nums: list[int]) - list[list[int]]: res [] used [False] * len(nums) path [] def backtrack(): if len(path) len(nums): res.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] True path.append(nums[i]) backtrack() used[i] False path.pop() backtrack() return res这里有几个值得反复咀嚼的点首先是res.append(path[:])为什么这里必须用path[:]而不是直接res.append(path)因为path是一个列表对象你后续不断地 append 和 pop 修改的是同一个对象。如果直接把path放进去最后结果集里存的其实都是同一个列表的引用等回溯结束所有的元素都会变成同一个状态导致结果全是空列表。这个问题我见过无数新手踩坑。4.3 剪枝是什么什么时候需要剪枝回溯算法最让人头痛的问题是复杂度。全排列的复杂度是 O(n * n!)因为排列总数为 n!每个结果需要复制 n 个元素。在 LeetCode 上题目规模通常不大所以直接回溯没问题。但如果你遇到的题目是数组里有重复数字要求返回不重复的全排列那你就得在回溯的过程中加一个“剪枝”操作。剪枝的意思是提前终止一些注定会重复的分支。以 LeetCode 第 47 题全排列 II为例核心就是先排序然后在 for 循环里判断如果当前元素和上一个元素相同且上一个元素还没被使用过就跳过当前的枚举。if i 0 and nums[i] nums[i - 1] and not used[i - 1]: continue这一步逻辑初看可能费解。你要明白它背后的原理同一层递归中如果前一个相同的数字没有被用过说明这个相同的值已经在前面被当作分支尝试过了当前分支会产生和之前一模一样的结果所以直接跳过。剪枝是回溯题里的核心优化手段也是区分“会套模板”和“真懂了回溯”的关键分水岭。面试官很喜欢在基础回溯题后面追加“如果有重复元素怎么办”这个问题本质上就是在考察你对剪枝的理解。4.4 回溯与状态重置最后再强调一下“撤销选择”为什么重要。在回溯里used[i] False和path.pop()这两行代码缺一不可。它们的意义是把状态恢复到进入该分支之前让其他分支在相同的起点上继续探索。我见过不少面试者逻辑上清楚要做什么但写代码时少写了状态恢复结果递归返回后used数组全变成了True后面的分支全部被跳过了。只要你记住“回溯 递归 状态恢复”这个公式这类问题就绝对不会犯低级错误。5. 面试里的“算法思维”养成法别急着刷题先学会拆题很多读者问过我说热词里现在都在讲“python算法思维题”到底什么才叫算法思维跟普通刷题有什么区别我的理解是思维题更强调你面对一个从未见过的问题时如何把它分解成已知模型而不是凭记忆背答案。面试中大多数算法题不是你刷过的原题而是原题的变体。你要练的就是“看出原题”的能力。5.1 拿到一道新题的思维路径模板我在准备面试的时候给自己总结了一套解题步骤遇到任何算法题都按这个顺序走第一步画例子。不管题目描述得多抽象先自己造一个具体的输入把答案手工推演出来。这个过程会逼你理解题目到底在问什么而不是急着写代码。第二步想暴力解。别觉得暴力解丢人暴力解最大的价值是帮你找到问题的“朴素逻辑”。面试时先把暴力解说清楚再提出优化方向这个思考路径本身就有分。第三步判断题型。这一步的关键词匹配法很管用。看到“最值”想 DP 和贪心看到“连续子数组”想前缀和、滑动窗口看到“所有组合/排列”想回溯看到“第 K 大”想堆或快速选择看到“有序数组搜索”想二分。这个匹配表不绝对但对大多数面试题都适用。第四步估算复杂度。在开始写代码之前心里先算一下暴力解的复杂度和优化后所能达到的目标复杂度。这两个数字能帮你判断优化方向是否合理。第五步写代码、跑样例。写完后不要立刻说“好了”主动用手里的简单例子跑一遍逻辑再想一想边界条件。5.2 如何用最短的时间刷出最大的效果关于刷题数量和频率我的观点是与其一天刷十道新题不如一天吃透两道题并且一周后回来重写一遍。记忆是会衰减的重写一次远比新做一道题更能巩固套路。关于“看题解”这件事也要有原则。我自己的原则是一道题如果想了三十分钟还没有任何成型的思路那就直接看题解但看完题解后必须合上答案自己再独立写一遍。如果第二天能默写出来这道题才算真正属于你了。再推荐一个练习方法找一个面试搭子互相给对方讲题。别小看这个办法讲题是最能暴露知识漏洞的方式。你可能觉得自己懂了但真解释的时候才发现很多细节根本说不清楚那你在面试现场也会一样卡住。5.3 计算复杂度时 Python 特有的坑还有一个很重要但很多人忽略的点在 Python 里算复杂度要考虑内置操作的时间代价。比如判断一个元素是否在列表里复杂度是 O(n)但判断是否在 set 或 dict 里复杂度是 O(1)。又比如list.pop(0)是 O(n) 的操作因为它要搬移所有元素而list.pop()是 O(1) 的。用collections.deque才能保证两端操作都是 O(1)。这些细节直接决定你的解法到底能不能过测试。我见过不少同学把列表当队列用结果在数据量大时超时还一脸困惑。这些基础的复杂度知识是 Python 刷算法题必须跨过的一层门槛。6. 常见问题与实战排查技巧平时在我的交流群里总有同学在面试后跑来复盘说“我明明刷了不少题怎么现场还是写不出来”。我帮大家总结出了几个高频问题也附上了对应的排查方向。第一个问题是思路停留在大脑里没落笔。有些人习惯在脑内跑代码觉得逻辑清晰了就直接写。但代码实际写出来往往会发现 index 不对、边界没处理、循环条件写反。解决建议是一定要养成在纸上画例子的习惯哪怕只是简单地写几个箭头和标记都比干想靠谱。第二个问题是边界条件考虑不全。空数组、只有一个元素、所有元素相同、元素已经有序这些是算法题最常见的边界情况。每次写完代码先主动跑这几个用例不要等面试官问。第三个问题是时间压力下心态崩了。这无法靠刷题解决只能靠多模拟面试来解决。自己给自己定 20 分钟倒计时用面试白板方式练习。我个人的经验是一旦你能在模拟面试中平静地讲出思路、写出实现、跑通测试真实面试时的紧张感会大幅降低。第四个问题是基础 API 不熟。Python 的排序sorted、堆heapq、双端队列deque、计数器Counter、默认字典defaultdict这些是刷题高频工具。不熟悉它们的话面试时连基础功能都要现场查文档效率极低。建议把每个常用集合类的方法过一遍能做到不看文档直接写。这里有一个很讨巧的小技巧你可以在面试前把collections、heapq、bisect等常用模块的常用方法默写一遍确认自己对它们足够熟悉这样面试时就不会因为 API 卡壳。第五个问题是只写代码不讲思路。很多性格内向的同学容易犯这个毛病。面试官其实非常想听到你内心的思考过程即使想法不完整也没关系可以先说“我想先试试枚举”再说“但这样复杂度是 O(n²)我希望能优化到 O(n log n)”面试官会顺着你的思路给提示。反过来如果你一直沉默面试官想帮你都找不到入口。7. 做题之后的复盘方法让每一道题都变成一类题最后分享一个我一直在用的复盘方法每做完一道题不要急着做下一道花几分钟在题目旁边记三行笔记。第一行写这题属于哪个题型第二行写最优解的核心思路是什么第三行写自己踩了哪个坑或者哪个地方想了很久才想通。这样一个星期后打开题目列表你看到的就不是一个接一个的标题而是一张你自己的知识图谱。用打家劫舍举个例子你可以记下题型是线性 DP核心是“选或不选”的状态决策我踩的坑是忘记单独处理 n0 和 n1 的情况。用全排列举例题型是回溯核心是递归状态恢复我踩的坑是忘记path[:]复制导致结果全空。这些笔记会在你面试之前提供非常高效的复习路径。我自己刷题的习惯是每晚固定花半小时周一三五做新题二四日重做旧题周末把这一周的笔记通读一遍。坚持三个月效果远好于那种“周末一坐一下午刷五十道”的集中式冲刺。算法思维的养成本身就靠日拱一卒不要指望临时抱佛脚能解决问题。这一期选的四道题滑动窗口、一维 DP、回溯、思维模型如果你能真正吃透基本可以覆盖面试中将近三分之一的常见题型。下一期我打算重点讲讲二叉树的递归套路和链表题的指针操作这两个方向在面试里的出场率也相当高。如果你有自己特别怕的题型也可以评论区告诉我我来安排。