最近帮一个学弟看某厂的算法笔试卷他考完一脸懵地问我题目我都能看懂但就是不知道从哪里下手感觉平时刷题白刷了。我把那张卷子从头到尾过了一遍发现一个挺扎心的事实程序员算法笔试卷这个场景和很多人理解的刷题根本不是一回事。笔试不是考你会不会背某个模板而是在短时间内考察你拆解问题、建模、选型、边界处理和复杂度判断的综合能力。如果你也正在准备这类笔试或者已经在面试流程里被算法题折磨过这篇文章应该能帮你省下不少试错成本。我会从面试官出题的视角、高频题型的拆解方法、动态规划和贪心的那些看似正确实则翻车的陷阱到手撕代码时的实际细节完整复盘一遍。我尽量把筛选标准、准备思路和避坑经验都讲透让它不仅是又一份题解而是能落地到下一次笔试里的方法论。1. 面试官出一套算法笔试卷时心里到底在想什么1.1 算法题不是考试的计算题它在筛选一种建模能力很多程序员准备算法笔试会把精力放在背题上看到二叉树就递归看到子序列就想DP看到字符串匹配就套KMP模板。但你别忘了面试官出题的时候从来不是为了让你默写模板。他真正想看到的是你拿到一个从没见过的、甚至有点绕的问题时能不能把它转化成一个自己熟悉的问题模型然后用严谨的代码把它表达出来。举个例子。我用过一道题原题是一排房子每个房子里有不同数量的金币但不能偷相邻的两家问最多能偷多少。很多候选人第一反应是贪心每次都取当前能取的最大值。然后很自信地写完了。但跑两个测试用例就露馅了因为这道题其实是个典型的动态规划dp[i] max(dp[i-1], dp[i-2] nums[i])。所以面试官真正考察的是你能不能看穿问题本质——并不是题目本身多难而是你有没有建立模型识别的习惯。我当时出的每一套笔试卷题目数量通常控制在5到6道难度从热身到压轴逐步递进。不会出现一道题卡死全场的情况但一定有一道题是用来区分中等水平和高水平的。这道题往往不是考你某个冷门算法而是把常见算法包装在一个新的场景里。这就回到了建模能力这个核心。1.2 笔试难度梯度是怎么设计的一套合格的程序员算法笔试卷通常分为三个梯队第一梯队是热身题考察基础数据结构操作比如数组去重、链表反转、字符串翻转。这类题的正确率要求很高基本是送分题用来筛掉完全没准备的候选人。第二梯队是核心题开始考察算法思想比如二分查找的变种、排序算法的手写、常见DP模型背包、LIS、编辑距离。这里能看出候选人有没有系统学过算法。第三梯队是压轴题往往结合了多个知识点比如TopK问题 外部排序 堆/快排变种或图的遍历 状态压缩DP。这类题的完整通过率通常不高但它起到的是加分作用不是一票否决作用。知道这个梯度有什么用非常有用。它决定了你的答题策略如果第一梯队都写不利索就别死磕第三梯队先把能拿的分稳稳拿到。很多人笔试挂掉不是压轴题没做出来而是前两梯队的小题因为边界条件、复杂度细节丢掉了一堆分。1.3 那些看起来超纲的考点其实有迹可循热词里出现了粒子群算法模拟退火音频重采样Rete算法PID控制这类看起来和笔试没关系的东西有些同学一看就慌这也要考我的判断是这类偏门算法出现在正式笔试中的概率很低除非你投的是特定方向的岗位比如音视频、机器学习、规则引擎。但它们出现在面试聊资或技术深挖环节的概率不低——面试官可能不问你怎么实现粒子群但会让你讲讲启发式搜索和精确搜索的取舍。所以我的建议是把核心经典算法排序、搜索、动态规划、图论基础、字符串匹配吃透做到可以手写、可以讲清复杂度、可以分析边界。至于粒子群、模拟退火这类你只需要知道它们解决什么问题、和经典算法相比优劣在哪就足够应付大多数场面了。2. 高频笔试题型拆解数组、字符串、链表与树2.1 KMP的next数组背模板之前先搞懂那三行回退热词里恰好有在KMP算法中对于模式串pabacaba其next数组这是真题里很常见的考法。很多候选人能把KMP的匹配过程背出来但一问next数组怎么求就卡壳或者干脆把next的含义都搞混了。先说人话KMP本质上是在做一件事——匹配失败时模式串别傻乎乎地从头再来而是跳到已经匹配过的、最长的相同前后缀位置。next数组存的就是当第i位匹配失败时模式串应该跳到哪一位。这个跳到哪一位的数学含义是模式串p[0...i-1]中最长的相等前缀和后缀的长度。以p abacaba为例我带你手算一遍next[0]约定为-1或者说0取决于写法。next[1]看a没有真前后缀为0。next[2]看ab前缀a后缀b不相等为0。next[3]看aba前缀a 后缀a长度1再看前缀ab 后缀ba不相等所以为1。next[4]看abac最长相等前后缀是0。next[5]看abaca前缀a 后缀a长度1前缀abvs 后缀ca不行abavsaca不行。所以为1。next[6]看abacab前缀ab 后缀ab长度2其他都不行所以为2。很多网上的模板会直接给你代码但最靠谱的记忆方式是理解那个j的回溯while (j ! -1 p[i] ! p[j]) j next[j];这句话的意思是——新来的字符匹配不上就利用已经算好的部分匹配信息把前缀指针往前退直到能匹配或退无可退。理解了这条回退链求next数组才不会出错。我在实际笔试里见过一个高频陷阱题目定义next[i]为模式串前i个字符组成子串的最长相等前后缀长度和图论里某些教科书用的失配时跳转位置差了一位。你落笔之前一定要看清楚题目定义否则一个for循环下来整个数组全错。2.2 排序算法的考察不只是背一个快排排序算法在笔试卷上出现的频率高到什么程度高到我几乎可以断言你投10家公司至少有7家会问排序。但考察方式并不只是手写快速排序更多的是给你一个近乎有序的数组让你选排序方案并说明原因。这时候插入排序可能比快排更优。让你分析归并排序的空间复杂度为什么是O(n)以及可以怎么优化原地归并虽然难但思路可以谈。让你写堆排序但要求不用递归。这题能挂掉不少人因为堆排序的调整逻辑虽然简单但写起来细节很多。我自己的建议是手写快排、归并、堆排、插入、选择、冒泡目标是在白板或编辑器里一遍写对。不要小看这件事很多候选人平时在IDE里写了无数遍但笔试环境没有自动补全、没有调试器、甚至没有编译运行就写不出来了。这是纯手感的差距只能靠默写训练来补。另外要清楚排序算法的稳定性稳定的有插入、冒泡、归并不稳定的有选择、快排、堆排。这个知识点在按多个字段排序的场景题里会冒出来比如先按分数从高到低再按ID从小到大如果你用了不稳定的排序第二层的顺序可能被打乱。2.3 链表与树的题目指针操作和递归状态的验证链表和二叉树是手写代码的高频区因为它们考的是指针操作和递归思维这两个能力恰恰是很多程序员日常业务开发里很少用的。但它们的解法和代码量都不大很适合笔试环境。链表题我最推荐先画图再写码。比如反转链表你光靠脑子想很容易绕晕但画一个三个节点的链表把每一步的next指向标出来代码就顺理成章了。另一个常见陷阱是链表的环用快慢指针判断是否有环不难但很多人忘了快指针走一步、慢指针走一步的写法在空链表和单节点链表上会空指针异常这种边界细节就是我前面说的白丢分点。二叉树方面前序、中序、后序、层序遍历是基础但笔试里更常考的是它们的变种比如最近公共祖先、二叉树的最大路径和、根据层序遍历结果重建二叉树。这些题目想考察的核心是你能不能把递归函数的返回值定义想清楚。我见过很多候选人写递归但说不清楚这个函数到底返回什么这就是伪理解。我自己的习惯是写递归前先用一行注释写出函数定义然后保证所有分支都围绕这个定义展开这样可以避免大量的逻辑混乱。3. 动态规划与贪心两类最容易被看穿的伪解法3.1 从爬楼梯到编辑距离DP状态定义是第一步也是最后一步动态规划是算法笔试的绝对核心几乎每套卷子里都会出现。热词里的贪心算法动态规划是最常被混淆的一对我先给一个直白的判断标准如果你能证明每一步的局部最优选择不会影响未来选择的空间那才可以用贪心否则大概率需要DP。很多人学DP最大的问题是看到题目觉得有点像DP然后就开始瞎写转移方程。我的经验是DP题的成败在状态定义而不在递推公式。状态定义不对递推公式写得再漂亮也是空中楼阁。举个经典例子编辑距离。dp[i][j]被定义为字符串A的前i个字符转换成字符串B的前j个字符所需的最小操作数。为什么偏偏是前i个和前j个因为这是一种规模描述把大问题拆成小问题小问题必须由两个子串的前缀规模来界定。一旦定义好转移就顺理成章dp[i][j]可以从dp[i-1][j]删、dp[i][j-1]插、dp[i-1][j-1]替换或不操作三个方向推导。如果没有先想清楚状态定义直接去凑公式很容易漏掉某个操作。还有一类DP题热词里的打家劫舍就是代表——它考的不是会写转移方程而是你能不能把一维问题扩展成二维、三维状态。每个房子偷不偷这种0/1决策天然适合DP。我在笔试里见过一个变种房子围成一圈首尾不能同时偷。解法是把原问题拆成两个子问题偷第一家不偷最后一家、不偷第一家偷最后一家。没有这个思路硬写状态会非常痛苦。3.2 贪心算法为什么想当然容易错贪心算法在笔试里出现的频率也很高但它的正确性常常经不起推敲。我见过一个很典型的错误示范题目是给一堆活动区间选尽量多的不重叠活动。很多候选人会说我每次选结束时间最早的。然后直接写循环。这确实是对的但很少有人能说清为什么对——因为结束越早给后面留下的时间越多这个交换论证逻辑其实是可以被严格证明的。但换一道题就不行了。比如找零钱有1、5、11面额的硬币凑出15元的最少硬币数。贪心的做法是每次选不大于剩余金额的最大面额于是选11、1、1、1、1共5枚。但最优解其实是555共3枚。这就是典型的贪心反例大面额虽然单次赚得多但它会压缩后续选择空间。这类题必须用DPdp[i] min(dp[i-1], dp[i-5], dp[i-11]) 1。所以我在复盘笔试时养成了一个习惯任何贪心解法写完后花一分钟构造一两个反例。构造反例的方法是想想局部最优会不会锁死全局最优。如果构造不出来再默认贪心是对的。3.3 一个经典反例帮你看清贪心和DP的分界线再来一个更经典的对比数字三角形问题——给你一个三角形数字塔从顶部出发每次可以走到左下方或右下方问经过路径上数字和的最大值。如果你用贪心每一步都选较大的那个子节点很可能会错过底部更大的数。比如顶部是5左子是99右子是100你选了100但99下面全是1100下面全是1而99左上角其实是0这就略过了99下方可能存在的巨大数值。这是贪心失效的典型场景。DP的解法是从底部往上推dp[i][j] triangle[i][j] max(dp[i1][j], dp[i1][j1])。你看状态定义是从(i,j)出发到底部的最大路径和然后从底部逐层向上计算时间复杂度O(n²)空间复杂度还可以优化到O(n)。本质上数字三角形考察的是你愿不愿意为全局最优放弃局部最优的思维模式。面试官出这道题其实是想听到你分析为什么贪心不行、DP才行的过程而不是直接甩一个转移方程。4. 手撕代码时的实战细节输入输出、边界条件与复杂度陷阱4.1 笔试环境下的输入输出那些没见过的坑很多第一次参加在线笔试的程序员会挂在输入输出上。比如牛客网和LeetCode的模式完全不同LeetCode已经帮你写好了函数签名而牛客或公司自研OJ要你自己处理标准输入、拼接输出格式。每年都有候选人因为不熟悉这种模式把大量时间浪费在读入上。我整理几个常见的坑先提前排掉读整行字符串如果输入包含一行带空格的字符串用cin s会只读到空格就停需要用getline或nextLine。多组测试用例很多题会以多组输入每组占一行的形式出现。我见过不少人在每行处理完后忘了刷新输出导致答案挤在一起。输出格式要求每两个数字之间以空格分隔、行尾无多余空格。这个细节非常恼人但也很容易写好用循环判断不是最后一个元素就输出空格或者先把结果存进数组最后join。输入结束标志有的题是读到EOF结束很多人不会写while(cin n)这个循环条件。这些坑本身不难难的是在笔试的高压环境下还要分心去处理。我自己的做法是考前专门练3-5道牛客网的输入输出练习题把各种读入模式跑一遍形成肌肉记忆。4.2 边界条件不是小心就好而是要有检查清单边界条件是算法笔试中最可惜的丢分点。一个候选人写了极漂亮的算法思路结果因为空数组访问越界、i1操作越界、整数溢出被判错才是最亏的事。边界问题不能靠小心解决要有一套固定的检查流程。我给自己总结的检查清单如下每次写完代码后逐项过一遍数组/字符串为空时代码行为对不对数组/字符串只有一个元素时行为对不对循环里有没有i-1或i1访问什么时候可能越界输入数值有没有可能等于Integer.MAX_VALUE或Long.MAX_VALUE加减乘除会不会溢出递归的终止条件是覆盖了规模最小的情况还是只覆盖了空双指针或快慢指针是否会因为快指针先走到头而提前退出使用哈希表时第一个元素和最后一个元素有没有走同一套逻辑这套清单看起来普通但每次笔试都能救我几次。比如二分查找的边界很多人用while(left right)还是while(left right)全凭记忆我建议直接在草稿纸上写一个长度为2和长度为1的小数组把过程走一遍比死记模板可靠得多。4.3 复杂度评估面试官最在意的三个问题手写完代码面试官大概率会追问三个问题时间复杂度是多少别只说O(n²)要说明哪一层循环导致了n²。空间复杂度是多少如果用了递归要算上递归调用栈的深度如果用哈希表要说明哈希表存储的元素数量和输入规模的关系。能否优化时间/空间怎么取舍这一问是真正的高分区。比如你写了一个哈希表解法空间O(n)面试官会问你能否在原数组上操作把空间降到O(1)。再比如你写了递归他会问会不会导致栈溢出怎么改成迭代很多候选人栽在低级的复杂度判断上比如把for循环里套一个Arrays.sort说成O(n)但实际上排序的复杂度是O(n log n)。再比如你在循环内不断拼接字符串Java里String是不可变的每次拼接都是O(len)的新建操作整体可能从O(n)变成O(n²)。这种细节面试官一眼就能看出来但写代码的人常常不自知。我个人建议每道题写完顺手在代码注释里写上复杂度既方便自己复核也给面试官一个我想清楚了的信号。更重要的是要能说出可不可以更优以及这个更优方案在什么条件下不成立——比如快排最坏O(n²)但可以随机化基准来规避这本身就是很好的加分点。5. 一套可复用的刷题与复盘方法从会做题到能讲题5.1 一套按题型大类而非题目来源的分类法很多人刷题是今天在题库里随便挑一道做完就完事这种方法效率很低。我更推荐先按题型建框架再往框架里填题。笔试中最常见的题型大类我列了一个清单数组与字符串双指针、滑动窗口、前缀和、哈希表、区间合并、字符串匹配KMP等。链表反转、环检测、合并有序链表、找中点、删除倒数第N个节点。栈与队列单调栈下一个更大元素、用栈模拟队列、表达式求值。树递归遍历、层序遍历、BST相关、最近公共祖先、树的序列化。堆与优先队列TopK问题、合并K个有序链表、数据流中位数、堆排序。图DFS、BFS、拓扑排序、最短路径Dijkstra、Floyd、并查集。动态规划线性DP、背包DP、区间DP、状态压缩DP、树形DP。贪心区间调度、加油站、跳跃游戏、分发饼干。排序与查找手写排序、二分查找变种、有序数组中的搜索。数学与位运算质因数分解、快速幂、异或性质、求平方根、格雷码。你按这个清单去分配刷题时间比今天随机刷一道难题、明天又随机刷一道简单题要有效得多。我见过一种很常见的备考误区大量刷难题但基础题型的熟练度不够。真要上了笔试难题不一定考但基础题一定会考。这个清单就是让你先确保基础再往高处走。5.2 复盘模板每道题都值得回答的六个问题刷题不复盘等于白刷。但复盘不是把题解看一遍就算完而是要用自己的话把逻辑讲清楚。我给自己定了一个六问复盘模板也分享给你这道题考察的是哪个/哪几个知识点我第一眼看到它时想到了什么思路这个思路为什么对/为什么不对最优解的状态定义或算法选择是什么我为什么没想到边界条件有哪些哪些边界是我第一次写的时候漏掉的如果改变一个条件比如数据规模变大、数组变为有序、一维变二维解法会怎么变这道题和我以前做的哪道题是换皮不换芯的第3问和第6问最有价值。第3问能帮你发现自己思维盲区第6问能帮你建立题型迁移能力。比如第k小元素可以用堆做也可以用快排的partition做还可以在特定条件下用桶排序——这三者都指向同一个问题如何在部分有序中找到位置理解了这一层你遇到数据流中位数就不会慌。5.3 怎么用讲解来检验自己是否真的会了我在准备笔试的最后阶段会做一件事把每道做过的题假装自己是在给一个刚入门的朋友讲题。不是念答案而是从题目场景讲起讲到为什么想到这个解法再讲到边界和复杂度。如果发现自己讲着讲着卡住了就说明这道题并没有真正内化。这个方法特别适合找假熟悉感。很多人读完题解觉得我看懂了但实际上只是我看懂了别人的思路到了笔试场上根本用不出来。讲解的过程能逼你把每一个步骤的为什么都补上为什么这里用栈而不是队列为什么这个边界是而不是讲不清楚的地方就是你的漏洞所在。我还发现把题目和热词里那些版本答案联系起来讲效果特别好。比如热词里数据结构排序算法贪心算法dijkstra算法这些词如果你能把每个词背后对应的问题、解法、复杂度、适用条件和反例都讲一遍那你准备的程度已经超过大多数候选人了。毕竟面试官问的不是你会不会背排序而是你懂不懂排序。懂不懂一讲就知道。另外我强烈建议在正式笔试前做一次完整模拟限定时间、不开IDE辅助、全程手敲、做完整套题。这种模拟能帮你提前暴露所有环境适应问题——输入输出格式、时间分配策略、心态管理等。我见过很多基础不错的候选人就是因为在正式考试里被某个输入格式卡了十分钟导致后面大题没时间做。花一次模拟的代价可以避免这样的惨剧。最后再分享一个我自己的习惯每次收到笔试卷我会先花三分钟把全部题目扫一遍按绝对能拿分、可能要花点时间、可能做不出来分成三档然后按先易后难的顺序答题。别小看这个策略它能让你在有限时间内拿满所有该拿的分。算法笔试从来不是谁做出最难的那道题谁赢而是谁在有限时间内拿到最高的总分谁赢。这也是我从出题人视角转成做题人视角后最想提醒你的一件事。
最近帮一个学弟看某厂的算法笔试卷他考完一脸懵地问我题目我都能看懂但就是不知道从哪里下手感觉平时刷题白刷了。我把那张卷子从头到尾过了一遍发现一个挺扎心的事实程序员算法笔试卷这个场景和很多人理解的刷题根本不是一回事。笔试不是考你会不会背某个模板而是在短时间内考察你拆解问题、建模、选型、边界处理和复杂度判断的综合能力。如果你也正在准备这类笔试或者已经在面试流程里被算法题折磨过这篇文章应该能帮你省下不少试错成本。我会从面试官出题的视角、高频题型的拆解方法、动态规划和贪心的那些看似正确实则翻车的陷阱到手撕代码时的实际细节完整复盘一遍。我尽量把筛选标准、准备思路和避坑经验都讲透让它不仅是又一份题解而是能落地到下一次笔试里的方法论。1. 面试官出一套算法笔试卷时心里到底在想什么1.1 算法题不是考试的计算题它在筛选一种建模能力很多程序员准备算法笔试会把精力放在背题上看到二叉树就递归看到子序列就想DP看到字符串匹配就套KMP模板。但你别忘了面试官出题的时候从来不是为了让你默写模板。他真正想看到的是你拿到一个从没见过的、甚至有点绕的问题时能不能把它转化成一个自己熟悉的问题模型然后用严谨的代码把它表达出来。举个例子。我用过一道题原题是一排房子每个房子里有不同数量的金币但不能偷相邻的两家问最多能偷多少。很多候选人第一反应是贪心每次都取当前能取的最大值。然后很自信地写完了。但跑两个测试用例就露馅了因为这道题其实是个典型的动态规划dp[i] max(dp[i-1], dp[i-2] nums[i])。所以面试官真正考察的是你能不能看穿问题本质——并不是题目本身多难而是你有没有建立模型识别的习惯。我当时出的每一套笔试卷题目数量通常控制在5到6道难度从热身到压轴逐步递进。不会出现一道题卡死全场的情况但一定有一道题是用来区分中等水平和高水平的。这道题往往不是考你某个冷门算法而是把常见算法包装在一个新的场景里。这就回到了建模能力这个核心。1.2 笔试难度梯度是怎么设计的一套合格的程序员算法笔试卷通常分为三个梯队第一梯队是热身题考察基础数据结构操作比如数组去重、链表反转、字符串翻转。这类题的正确率要求很高基本是送分题用来筛掉完全没准备的候选人。第二梯队是核心题开始考察算法思想比如二分查找的变种、排序算法的手写、常见DP模型背包、LIS、编辑距离。这里能看出候选人有没有系统学过算法。第三梯队是压轴题往往结合了多个知识点比如TopK问题 外部排序 堆/快排变种或图的遍历 状态压缩DP。这类题的完整通过率通常不高但它起到的是加分作用不是一票否决作用。知道这个梯度有什么用非常有用。它决定了你的答题策略如果第一梯队都写不利索就别死磕第三梯队先把能拿的分稳稳拿到。很多人笔试挂掉不是压轴题没做出来而是前两梯队的小题因为边界条件、复杂度细节丢掉了一堆分。1.3 那些看起来超纲的考点其实有迹可循热词里出现了粒子群算法模拟退火音频重采样Rete算法PID控制这类看起来和笔试没关系的东西有些同学一看就慌这也要考我的判断是这类偏门算法出现在正式笔试中的概率很低除非你投的是特定方向的岗位比如音视频、机器学习、规则引擎。但它们出现在面试聊资或技术深挖环节的概率不低——面试官可能不问你怎么实现粒子群但会让你讲讲启发式搜索和精确搜索的取舍。所以我的建议是把核心经典算法排序、搜索、动态规划、图论基础、字符串匹配吃透做到可以手写、可以讲清复杂度、可以分析边界。至于粒子群、模拟退火这类你只需要知道它们解决什么问题、和经典算法相比优劣在哪就足够应付大多数场面了。2. 高频笔试题型拆解数组、字符串、链表与树2.1 KMP的next数组背模板之前先搞懂那三行回退热词里恰好有在KMP算法中对于模式串pabacaba其next数组这是真题里很常见的考法。很多候选人能把KMP的匹配过程背出来但一问next数组怎么求就卡壳或者干脆把next的含义都搞混了。先说人话KMP本质上是在做一件事——匹配失败时模式串别傻乎乎地从头再来而是跳到已经匹配过的、最长的相同前后缀位置。next数组存的就是当第i位匹配失败时模式串应该跳到哪一位。这个跳到哪一位的数学含义是模式串p[0...i-1]中最长的相等前缀和后缀的长度。以p abacaba为例我带你手算一遍next[0]约定为-1或者说0取决于写法。next[1]看a没有真前后缀为0。next[2]看ab前缀a后缀b不相等为0。next[3]看aba前缀a 后缀a长度1再看前缀ab 后缀ba不相等所以为1。next[4]看abac最长相等前后缀是0。next[5]看abaca前缀a 后缀a长度1前缀abvs 后缀ca不行abavsaca不行。所以为1。next[6]看abacab前缀ab 后缀ab长度2其他都不行所以为2。很多网上的模板会直接给你代码但最靠谱的记忆方式是理解那个j的回溯while (j ! -1 p[i] ! p[j]) j next[j];这句话的意思是——新来的字符匹配不上就利用已经算好的部分匹配信息把前缀指针往前退直到能匹配或退无可退。理解了这条回退链求next数组才不会出错。我在实际笔试里见过一个高频陷阱题目定义next[i]为模式串前i个字符组成子串的最长相等前后缀长度和图论里某些教科书用的失配时跳转位置差了一位。你落笔之前一定要看清楚题目定义否则一个for循环下来整个数组全错。2.2 排序算法的考察不只是背一个快排排序算法在笔试卷上出现的频率高到什么程度高到我几乎可以断言你投10家公司至少有7家会问排序。但考察方式并不只是手写快速排序更多的是给你一个近乎有序的数组让你选排序方案并说明原因。这时候插入排序可能比快排更优。让你分析归并排序的空间复杂度为什么是O(n)以及可以怎么优化原地归并虽然难但思路可以谈。让你写堆排序但要求不用递归。这题能挂掉不少人因为堆排序的调整逻辑虽然简单但写起来细节很多。我自己的建议是手写快排、归并、堆排、插入、选择、冒泡目标是在白板或编辑器里一遍写对。不要小看这件事很多候选人平时在IDE里写了无数遍但笔试环境没有自动补全、没有调试器、甚至没有编译运行就写不出来了。这是纯手感的差距只能靠默写训练来补。另外要清楚排序算法的稳定性稳定的有插入、冒泡、归并不稳定的有选择、快排、堆排。这个知识点在按多个字段排序的场景题里会冒出来比如先按分数从高到低再按ID从小到大如果你用了不稳定的排序第二层的顺序可能被打乱。2.3 链表与树的题目指针操作和递归状态的验证链表和二叉树是手写代码的高频区因为它们考的是指针操作和递归思维这两个能力恰恰是很多程序员日常业务开发里很少用的。但它们的解法和代码量都不大很适合笔试环境。链表题我最推荐先画图再写码。比如反转链表你光靠脑子想很容易绕晕但画一个三个节点的链表把每一步的next指向标出来代码就顺理成章了。另一个常见陷阱是链表的环用快慢指针判断是否有环不难但很多人忘了快指针走一步、慢指针走一步的写法在空链表和单节点链表上会空指针异常这种边界细节就是我前面说的白丢分点。二叉树方面前序、中序、后序、层序遍历是基础但笔试里更常考的是它们的变种比如最近公共祖先、二叉树的最大路径和、根据层序遍历结果重建二叉树。这些题目想考察的核心是你能不能把递归函数的返回值定义想清楚。我见过很多候选人写递归但说不清楚这个函数到底返回什么这就是伪理解。我自己的习惯是写递归前先用一行注释写出函数定义然后保证所有分支都围绕这个定义展开这样可以避免大量的逻辑混乱。3. 动态规划与贪心两类最容易被看穿的伪解法3.1 从爬楼梯到编辑距离DP状态定义是第一步也是最后一步动态规划是算法笔试的绝对核心几乎每套卷子里都会出现。热词里的贪心算法动态规划是最常被混淆的一对我先给一个直白的判断标准如果你能证明每一步的局部最优选择不会影响未来选择的空间那才可以用贪心否则大概率需要DP。很多人学DP最大的问题是看到题目觉得有点像DP然后就开始瞎写转移方程。我的经验是DP题的成败在状态定义而不在递推公式。状态定义不对递推公式写得再漂亮也是空中楼阁。举个经典例子编辑距离。dp[i][j]被定义为字符串A的前i个字符转换成字符串B的前j个字符所需的最小操作数。为什么偏偏是前i个和前j个因为这是一种规模描述把大问题拆成小问题小问题必须由两个子串的前缀规模来界定。一旦定义好转移就顺理成章dp[i][j]可以从dp[i-1][j]删、dp[i][j-1]插、dp[i-1][j-1]替换或不操作三个方向推导。如果没有先想清楚状态定义直接去凑公式很容易漏掉某个操作。还有一类DP题热词里的打家劫舍就是代表——它考的不是会写转移方程而是你能不能把一维问题扩展成二维、三维状态。每个房子偷不偷这种0/1决策天然适合DP。我在笔试里见过一个变种房子围成一圈首尾不能同时偷。解法是把原问题拆成两个子问题偷第一家不偷最后一家、不偷第一家偷最后一家。没有这个思路硬写状态会非常痛苦。3.2 贪心算法为什么想当然容易错贪心算法在笔试里出现的频率也很高但它的正确性常常经不起推敲。我见过一个很典型的错误示范题目是给一堆活动区间选尽量多的不重叠活动。很多候选人会说我每次选结束时间最早的。然后直接写循环。这确实是对的但很少有人能说清为什么对——因为结束越早给后面留下的时间越多这个交换论证逻辑其实是可以被严格证明的。但换一道题就不行了。比如找零钱有1、5、11面额的硬币凑出15元的最少硬币数。贪心的做法是每次选不大于剩余金额的最大面额于是选11、1、1、1、1共5枚。但最优解其实是555共3枚。这就是典型的贪心反例大面额虽然单次赚得多但它会压缩后续选择空间。这类题必须用DPdp[i] min(dp[i-1], dp[i-5], dp[i-11]) 1。所以我在复盘笔试时养成了一个习惯任何贪心解法写完后花一分钟构造一两个反例。构造反例的方法是想想局部最优会不会锁死全局最优。如果构造不出来再默认贪心是对的。3.3 一个经典反例帮你看清贪心和DP的分界线再来一个更经典的对比数字三角形问题——给你一个三角形数字塔从顶部出发每次可以走到左下方或右下方问经过路径上数字和的最大值。如果你用贪心每一步都选较大的那个子节点很可能会错过底部更大的数。比如顶部是5左子是99右子是100你选了100但99下面全是1100下面全是1而99左上角其实是0这就略过了99下方可能存在的巨大数值。这是贪心失效的典型场景。DP的解法是从底部往上推dp[i][j] triangle[i][j] max(dp[i1][j], dp[i1][j1])。你看状态定义是从(i,j)出发到底部的最大路径和然后从底部逐层向上计算时间复杂度O(n²)空间复杂度还可以优化到O(n)。本质上数字三角形考察的是你愿不愿意为全局最优放弃局部最优的思维模式。面试官出这道题其实是想听到你分析为什么贪心不行、DP才行的过程而不是直接甩一个转移方程。4. 手撕代码时的实战细节输入输出、边界条件与复杂度陷阱4.1 笔试环境下的输入输出那些没见过的坑很多第一次参加在线笔试的程序员会挂在输入输出上。比如牛客网和LeetCode的模式完全不同LeetCode已经帮你写好了函数签名而牛客或公司自研OJ要你自己处理标准输入、拼接输出格式。每年都有候选人因为不熟悉这种模式把大量时间浪费在读入上。我整理几个常见的坑先提前排掉读整行字符串如果输入包含一行带空格的字符串用cin s会只读到空格就停需要用getline或nextLine。多组测试用例很多题会以多组输入每组占一行的形式出现。我见过不少人在每行处理完后忘了刷新输出导致答案挤在一起。输出格式要求每两个数字之间以空格分隔、行尾无多余空格。这个细节非常恼人但也很容易写好用循环判断不是最后一个元素就输出空格或者先把结果存进数组最后join。输入结束标志有的题是读到EOF结束很多人不会写while(cin n)这个循环条件。这些坑本身不难难的是在笔试的高压环境下还要分心去处理。我自己的做法是考前专门练3-5道牛客网的输入输出练习题把各种读入模式跑一遍形成肌肉记忆。4.2 边界条件不是小心就好而是要有检查清单边界条件是算法笔试中最可惜的丢分点。一个候选人写了极漂亮的算法思路结果因为空数组访问越界、i1操作越界、整数溢出被判错才是最亏的事。边界问题不能靠小心解决要有一套固定的检查流程。我给自己总结的检查清单如下每次写完代码后逐项过一遍数组/字符串为空时代码行为对不对数组/字符串只有一个元素时行为对不对循环里有没有i-1或i1访问什么时候可能越界输入数值有没有可能等于Integer.MAX_VALUE或Long.MAX_VALUE加减乘除会不会溢出递归的终止条件是覆盖了规模最小的情况还是只覆盖了空双指针或快慢指针是否会因为快指针先走到头而提前退出使用哈希表时第一个元素和最后一个元素有没有走同一套逻辑这套清单看起来普通但每次笔试都能救我几次。比如二分查找的边界很多人用while(left right)还是while(left right)全凭记忆我建议直接在草稿纸上写一个长度为2和长度为1的小数组把过程走一遍比死记模板可靠得多。4.3 复杂度评估面试官最在意的三个问题手写完代码面试官大概率会追问三个问题时间复杂度是多少别只说O(n²)要说明哪一层循环导致了n²。空间复杂度是多少如果用了递归要算上递归调用栈的深度如果用哈希表要说明哈希表存储的元素数量和输入规模的关系。能否优化时间/空间怎么取舍这一问是真正的高分区。比如你写了一个哈希表解法空间O(n)面试官会问你能否在原数组上操作把空间降到O(1)。再比如你写了递归他会问会不会导致栈溢出怎么改成迭代很多候选人栽在低级的复杂度判断上比如把for循环里套一个Arrays.sort说成O(n)但实际上排序的复杂度是O(n log n)。再比如你在循环内不断拼接字符串Java里String是不可变的每次拼接都是O(len)的新建操作整体可能从O(n)变成O(n²)。这种细节面试官一眼就能看出来但写代码的人常常不自知。我个人建议每道题写完顺手在代码注释里写上复杂度既方便自己复核也给面试官一个我想清楚了的信号。更重要的是要能说出可不可以更优以及这个更优方案在什么条件下不成立——比如快排最坏O(n²)但可以随机化基准来规避这本身就是很好的加分点。5. 一套可复用的刷题与复盘方法从会做题到能讲题5.1 一套按题型大类而非题目来源的分类法很多人刷题是今天在题库里随便挑一道做完就完事这种方法效率很低。我更推荐先按题型建框架再往框架里填题。笔试中最常见的题型大类我列了一个清单数组与字符串双指针、滑动窗口、前缀和、哈希表、区间合并、字符串匹配KMP等。链表反转、环检测、合并有序链表、找中点、删除倒数第N个节点。栈与队列单调栈下一个更大元素、用栈模拟队列、表达式求值。树递归遍历、层序遍历、BST相关、最近公共祖先、树的序列化。堆与优先队列TopK问题、合并K个有序链表、数据流中位数、堆排序。图DFS、BFS、拓扑排序、最短路径Dijkstra、Floyd、并查集。动态规划线性DP、背包DP、区间DP、状态压缩DP、树形DP。贪心区间调度、加油站、跳跃游戏、分发饼干。排序与查找手写排序、二分查找变种、有序数组中的搜索。数学与位运算质因数分解、快速幂、异或性质、求平方根、格雷码。你按这个清单去分配刷题时间比今天随机刷一道难题、明天又随机刷一道简单题要有效得多。我见过一种很常见的备考误区大量刷难题但基础题型的熟练度不够。真要上了笔试难题不一定考但基础题一定会考。这个清单就是让你先确保基础再往高处走。5.2 复盘模板每道题都值得回答的六个问题刷题不复盘等于白刷。但复盘不是把题解看一遍就算完而是要用自己的话把逻辑讲清楚。我给自己定了一个六问复盘模板也分享给你这道题考察的是哪个/哪几个知识点我第一眼看到它时想到了什么思路这个思路为什么对/为什么不对最优解的状态定义或算法选择是什么我为什么没想到边界条件有哪些哪些边界是我第一次写的时候漏掉的如果改变一个条件比如数据规模变大、数组变为有序、一维变二维解法会怎么变这道题和我以前做的哪道题是换皮不换芯的第3问和第6问最有价值。第3问能帮你发现自己思维盲区第6问能帮你建立题型迁移能力。比如第k小元素可以用堆做也可以用快排的partition做还可以在特定条件下用桶排序——这三者都指向同一个问题如何在部分有序中找到位置理解了这一层你遇到数据流中位数就不会慌。5.3 怎么用讲解来检验自己是否真的会了我在准备笔试的最后阶段会做一件事把每道做过的题假装自己是在给一个刚入门的朋友讲题。不是念答案而是从题目场景讲起讲到为什么想到这个解法再讲到边界和复杂度。如果发现自己讲着讲着卡住了就说明这道题并没有真正内化。这个方法特别适合找假熟悉感。很多人读完题解觉得我看懂了但实际上只是我看懂了别人的思路到了笔试场上根本用不出来。讲解的过程能逼你把每一个步骤的为什么都补上为什么这里用栈而不是队列为什么这个边界是而不是讲不清楚的地方就是你的漏洞所在。我还发现把题目和热词里那些版本答案联系起来讲效果特别好。比如热词里数据结构排序算法贪心算法dijkstra算法这些词如果你能把每个词背后对应的问题、解法、复杂度、适用条件和反例都讲一遍那你准备的程度已经超过大多数候选人了。毕竟面试官问的不是你会不会背排序而是你懂不懂排序。懂不懂一讲就知道。另外我强烈建议在正式笔试前做一次完整模拟限定时间、不开IDE辅助、全程手敲、做完整套题。这种模拟能帮你提前暴露所有环境适应问题——输入输出格式、时间分配策略、心态管理等。我见过很多基础不错的候选人就是因为在正式考试里被某个输入格式卡了十分钟导致后面大题没时间做。花一次模拟的代价可以避免这样的惨剧。最后再分享一个我自己的习惯每次收到笔试卷我会先花三分钟把全部题目扫一遍按绝对能拿分、可能要花点时间、可能做不出来分成三档然后按先易后难的顺序答题。别小看这个策略它能让你在有限时间内拿满所有该拿的分。算法笔试从来不是谁做出最难的那道题谁赢而是谁在有限时间内拿到最高的总分谁赢。这也是我从出题人视角转成做题人视角后最想提醒你的一件事。
