1. 从五道题看大厂笔试的底层筛选逻辑每年秋招季算法笔试都是绕不过去的一道坎。我当年第一次做这类题的时候五道题只AC了一道半剩下的要么超时要么思路完全跑偏。后来复盘才发现问题不在于我刷题量不够而在于我没搞明白一件事笔试题目不是考你会不会写代码而是考你在有限时间内能不能把一个问题抽象成可计算的模型。这个认知转变之后我再做类似题目正确率明显上来了。这篇文章围绕五道典型的算法笔试题展开题目类型覆盖了数组操作、字符串处理、动态规划、贪心策略和树结构遍历这几个高频方向。我会把每道题的审题思路、暴力解法的瓶颈在哪、优化方案怎么推导、以及代码实现中容易翻车的细节全部拆开讲。适合正在准备校招笔试的同学也适合已经工作但想重新梳理算法思维的朋友。每道题我都会先讲“看到题目时脑子里应该想什么”再讲“代码怎么写”最后补一句“我当时踩了什么坑”。需要提前说明的是以下题目描述基于我对这类笔试常见题型的归纳和重构并非原题逐字复现但核心考点和难度梯度是一致的。五道题的时间分配建议是前两道各15分钟第三道20分钟第四道25分钟第五道30分钟留15分钟检查边界条件。这个节奏是我试过多次之后觉得最稳的。2. 数组区间操作从O(n²)到O(n)的思维跃迁2.1 题目场景与暴力解法的天然缺陷第一道题的场景是这样的给定一个长度为n的整数数组和一个整数k要求找出数组中所有长度为k的连续子数组的最大平均值返回这个最大平均值。看起来很简单对吧我第一反应就是两层循环外层枚举起始位置内层累加k个元素求和然后除以k取最大值。这个思路没错但时间复杂度是O(n×k)。当n是10的5次方、k是10的4次方的时候运算量直接到10的9次方级别在笔试环境下基本必超时。我当时就是死在这个思路上本地跑小数据没问题一提交就TLE。关键问题在于相邻两个窗口之间有k-1个元素是重叠的。暴力解法把这块重复计算了。想通这一点优化方向就出来了——滑动窗口。2.2 滑动窗口的核心推导与代码落地滑动窗口的本质是用一次遍历完成所有窗口的计算。具体做法是先算出第一个窗口的和然后每次向右滑动一格减去左边移出的元素加上右边移入的元素。这样每个元素只被加一次、减一次总时间复杂度降到O(n)。def find_max_average(nums, k): # 先计算第一个窗口的和 window_sum sum(nums[:k]) max_sum window_sum # 滑动窗口 for i in range(k, len(nums)): window_sum nums[i] - nums[i - k] max_sum max(max_sum, window_sum) return max_sum / k这段代码看着简单但有两个细节容易翻车。第一个是返回值类型题目要求返回浮点数如果你在计算过程中一直用整数最后除以k的时候在Python 3里没问题但在某些语言里会做整数除法结果直接截断。第二个是窗口和的初始化必须用sum(nums[:k])先算第一个窗口不能从空窗口开始滑否则第一次滑动时减去的nums[i-k]会越界。注意滑动窗口适用于“窗口大小固定”的场景。如果窗口大小不固定需要用双指针加条件判断那是另一套模板。2.3 这道题真正想筛掉什么人我后来跟做过笔试出题的朋友聊过他说这类题目的筛选目标很明确看你能不能识别出“重叠子问题”并消除冗余计算。暴力解法谁都会写但笔试的区分度就在于你能不能在3分钟内想到滑动窗口。如果你想了10分钟还在暴力解法上打转那说明你对“空间换时间”或者“增量更新”这类思想还不够敏感。我的建议是以后看到“连续子数组”“固定长度区间”这类关键词条件反射地先想滑动窗口。这个思维习惯一旦建立类似的题目基本都能秒杀。3. 字符串解码栈结构在嵌套场景下的妙用3.1 题目描述与递归思路的局限性第二道题是字符串解码。给定一个经过编码的字符串编码规则是k[encoded_string]表示方括号里的内容重复k次。比如输入3[a2[c]]输出应该是accaccacc。这道题的难点在于嵌套结构——方括号里面还有方括号而且数字可能是多位的。我一开始想用递归遇到[就进入下一层遇到]就返回。思路是对的但写起来特别容易乱尤其是处理多位数字和字符串拼接的时候。后来我换成了栈代码一下子清晰了很多。3.2 双栈方案的逐步拆解用两个栈一个存数字重复次数一个存字符串当前已经解码的部分。遍历输入字符串分四种情况处理遇到数字累加计算完整的数字因为可能是多位的比如12遇到[把当前数字压入数字栈把当前字符串压入字符串栈然后重置它们遇到]弹出数字栈顶的k和字符串栈顶的prev把当前字符串重复k次后拼接到prev后面遇到字母直接拼接到当前字符串def decode_string(s): num_stack [] str_stack [] current_num 0 current_str for ch in s: if ch.isdigit(): current_num current_num * 10 int(ch) elif ch [: num_stack.append(current_num) str_stack.append(current_str) current_num 0 current_str elif ch ]: k num_stack.pop() prev str_stack.pop() current_str prev current_str * k else: current_str ch return current_str这段代码的精髓在于current_num current_num * 10 int(ch)这一行。很多人在处理多位数的时候会写成current_num int(ch)结果遇到12[a]这种输入就变成了1和2分别处理直接出错。这个细节我在第一次做的时候也踩了调试了半天才发现。3.3 栈类题目的通用识别信号这道题给我的最大启发是只要题目涉及“嵌套”“配对”“最近相关性”优先考虑栈。括号匹配、表达式求值、嵌套结构解析全都是栈的经典应用场景。栈的本质是“后进先出”正好对应嵌套结构中“最内层最先完成”的特性。另外一个小技巧如果不想用两个栈可以用一个栈存元组(prev_str, k)效果一样代码更紧凑。但在笔试环境下双栈的可读性更好调试起来也更方便我建议优先选双栈。4. 动态规划状态定义才是真正的分水岭4.1 最长递增子序列的经典陷阱第三道题是最长递增子序列LIS。给定一个无序整数数组找出其中最长递增子序列的长度。子序列不要求连续但要求保持相对顺序。比如[10, 9, 2, 5, 3, 7, 101, 18]最长递增子序列是[2, 3, 7, 101]长度是4。这道题的DP解法是O(n²)定义dp[i]为以nums[i]结尾的最长递增子序列长度状态转移方程是dp[i] max(dp[j]) 1其中j i且nums[j] nums[i]。这个思路很标准但问题是——O(n²)在n10的5次方时会超时。4.2 贪心二分的优化路径优化到O(n log n)的核心思路是维护一个数组tails其中tails[i]表示长度为i1的递增子序列的最小结尾元素。遍历原数组时用二分查找在tails中找到第一个大于等于当前元素的位置替换它如果没找到就追加到末尾。import bisect def length_of_lis(nums): tails [] for num in nums: pos bisect.bisect_left(tails, num) if pos len(tails): tails.append(num) else: tails[pos] num return len(tails)这个算法的精妙之处在于tails数组本身是递增的因为每次替换都保持了有序性所以可以用二分查找。而tails的长度就是LIS的长度。我第一次看到这个解法的时候觉得特别反直觉——为什么替换元素不会影响结果后来想明白了替换操作是在保证“同样长度的子序列结尾更小”这个不变量而结尾越小后续能接上的元素就越多。4.3 DP题目的通用思考框架做DP题目我总结了一个三步框架步骤要回答的问题以LIS为例状态定义dp[i]表示什么以nums[i]结尾的LIS长度转移方程dp[i]怎么从之前的状态推出来dp[i] max(dp[j]) 1边界条件初始值是什么dp[i] 1每个元素自身这三步里状态定义是最关键的。状态定义错了转移方程怎么写都不对。我见过很多人做DP题的时候上来就写转移方程结果写到一半发现推不下去回头改状态定义前面的代码全废了。正确的做法是先把状态定义想清楚用自然语言描述一遍确认逻辑自洽了再动手写代码。提示如果DP的时间复杂度不够优先看状态能不能压缩再看能不能用贪心或数据结构优化转移过程。LIS的优化就是用二分查找加速了“找最大dp[j]”这一步。5. 贪心策略区间调度中的排序玄机5.1 会议室安排问题的本质第四道题是区间调度给定一组区间找出最多能选出多少个互不重叠的区间。比如[[1,3], [2,4], [3,6], [5,7]]最多能选2个[1,3]和[3,6]或者[2,4]和[5,7]。这道题的贪心策略是按区间的结束时间升序排序然后依次选择结束时间最早且与前一个不重叠的区间。为什么按结束时间排序而不是开始时间因为结束时间越早留给后面区间的空间就越大。这是一个典型的“贪心选择性质”的证明。5.2 排序策略的对比验证我当初做这道题的时候第一反应是按开始时间排序然后依次选。结果发现有些case过不了。比如[[1,10], [2,3], [4,5]]按开始时间排序后选[1,10]后面两个都没法选了答案是1。但最优解是选[2,3]和[4,5]答案是2。按结束时间排序就没这个问题[2,3]结束最早选它然后[4,5]不重叠选它[1,10]和[4,5]重叠跳过。答案正确。def max_intervals(intervals): if not intervals: return 0 # 按结束时间升序排序 intervals.sort(keylambda x: x[1]) count 1 end intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] end: count 1 end intervals[i][1] return count5.3 贪心题目的验证方法论贪心算法最大的问题是你不确定贪心策略是不是对的。我的经验是写完贪心策略后先手动构造几个反例试试。如果找不到反例再用数学归纳法或者交换论证法证明一下。笔试的时候没时间严格证明但至少要想清楚“为什么这个贪心选择不会导致全局变差”。另一个实用技巧如果贪心策略涉及排序排序的key选择往往就是解题的关键。区间调度按结束时间排活动选择按结束时间排任务调度按截止时间排——这些都不是巧合而是因为“越早结束/越早截止留给后续的空间越大”这个直觉。6. 二叉树遍历递归与非递归的取舍之道6.1 锯齿形层序遍历的题目要求第五道题是二叉树的锯齿形层序遍历第一层从左到右第二层从右到左第三层从左到右以此类推。比如一棵树返回[[3], [20, 9], [15, 7]]这样的结果。这道题的核心是层序遍历BFS在此基础上加一个方向标志位每隔一层反转一下当前层的结果。用队列实现BFS是标准做法但有几个细节需要注意。6.2 BFS实现中的队列操作细节from collections import deque def zigzag_level_order(root): if not root: return [] result [] queue deque([root]) left_to_right True while queue: level_size len(queue) level_nodes deque() for _ in range(level_size): node queue.popleft() if left_to_right: level_nodes.append(node.val) else: level_nodes.appendleft(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(list(level_nodes)) left_to_right not left_to_right return result这里的关键点是在遍历当前层之前先记录队列的长度level_size。因为遍历过程中会往队列里加下一层的节点如果不提前记录长度就没法区分当前层和下一层。这个细节我在第一次写的时候忽略了导致所有节点混在一起输出。另外用deque的appendleft来实现反向插入比先收集再反转效率更高代码也更简洁。6.3 递归与非递归的适用场景对比二叉树的遍历递归写法通常更简洁但非递归写法在某些场景下更可控。我整理了一个对比维度递归非递归栈/队列代码简洁度高中栈溢出风险树深度大时有无调试难度较低较高适用场景前中后序遍历层序遍历、需要控制遍历顺序对于层序遍历非递归是唯一选择因为递归天然是深度优先的。而对于前中后序遍历递归写法更直观但如果树很深比如退化成链表递归可能导致栈溢出这时候就得用非递归。注意笔试中如果题目没有明确要求非递归优先写递归因为不容易出错。但如果题目暗示数据规模很大或者明确要求O(1)空间那就得考虑非递归了。7. 笔试实战中的时间分配与调试技巧7.1 五道题的时间分配策略笔试最怕的不是不会做而是在会做的题上超时。我自己的时间分配是这样的第一道题数组15分钟包括读题、写代码、测试边界第二道题字符串15分钟栈的模板比较固定写起来快第三道题DP20分钟状态定义想清楚再动手第四道题贪心20分钟排序遍历代码量不大第五道题树25分钟BFS模板方向控制剩余15分钟检查所有题的边界条件尤其是空输入、单元素、极端值这个分配的前提是每道题都能在计划时间内AC。如果某道题卡住了果断跳过先做后面的。我见过太多人死磕一道题结果后面会做的题没时间写亏大了。7.2 本地调试的快速验证方法笔试平台通常只给几个样例但样例过了不代表代码没问题。我习惯在本地自己构造几组测试数据空输入[]、、None单元素[1]、a极端值全相同元素、严格递增、严格递减边界情况k等于数组长度、嵌套深度最大这些case能覆盖80%以上的边界bug。另外如果时间允许写一个暴力解法作为对照用小规模随机数据对拍能快速发现逻辑错误。7.3 代码提交前的自查清单每次提交前我会快速过一遍这个清单函数名和参数名是否和题目要求一致返回值类型是否正确int vs floatlist vs tuple有没有数组越界、空指针的风险循环的起止条件是否正确range(n)还是range(n-1)取模运算是否在每一步都做了如果题目要求有没有用Python的/做整数除法导致精度丢失这个清单看起来简单但每次都能帮我抓到一两个小问题。尤其是第6条Python 3的/返回浮点数如果题目要求返回整数得用//。8. 从笔试到面试算法能力的持续打磨笔试只是第一关后面还有面试的手撕代码环节。我的体会是笔试考的是“能不能在压力下写出正确代码”面试考的是“能不能把思路讲清楚并应对追问”。两者需要的能力有重叠但侧重点不同。准备笔试的时候我建议按题型刷题每个题型吃透3-5道经典题总结出模板和易错点。准备面试的时候则要练习“边写边讲”把自己的思考过程用语言表达出来。我当初面试的时候有一道题我写对了但面试官问我“为什么这里用二分而不是哈希”我没答上来结果那轮面试就挂了。后来我才明白面试官不仅看结果更看你的决策过程。另外算法能力的提升是一个长期过程不要指望突击一周就能搞定。我的建议是每天保持1-2道题的节奏重点放在“想清楚”而不是“刷数量”。一道题想透比十道题囫囵吞枣有价值得多。最后分享一个我个人的小习惯每次做完一道题我会用一句话总结这道题的核心考点记在笔记里。比如“LIS——状态定义二分优化”“字符串解码——双栈处理嵌套”。积累多了之后看到新题就能快速归类反应速度明显提升。这个习惯看起来笨但坚持三个月效果非常明显。