早上七点二十闹钟还没响完第二遍我就起来了。今天是我408机试复试学习Day3目标很明确把前两天积累的知识点转化成能跑的代码同时把一部分精力放到熟悉机试环境上。报考目标院校的复试包含了机试环节往年的情况是给你一台机器、一套题目限时内提交代码评测机自动判分。这和初试拿着408卷子写选择题、大题完全不一样动手能力、调试速度、边界处理每一项都可能在考场上拉开差距。这篇文章我不打算写什么“复习方法论大全”就是单纯把今天这整天的学习过程、练过的题、踩过的坑以及傍晚复盘时觉得第二天需要修正的地方原原本本梳理出来。对正在准备计算机类复试、尤其是目标院校带机试环节的同学来说里面的内容可以直接当参考也可以根据自己的进度调整。1. 为什么把第3天安排成“重刷代码”模式1.1 复试机试和初试408的区别很多同学初试408能考出不错的分数但复试机试反而翻车根源就在这里408考察的是你对知识体系的理解和笔算能力卷子上出现一道算法题你可以在草稿纸上慢慢画、慢慢推。但机试环境里题目交上去之后评测机不会因为你在草稿纸上写出了正确答案就给你分它只看你的程序能不能在规定时间内跑出正确的输出。这就导致一个很现实的问题知识点“会”和代码“能通过”之间有一条巨大的鸿沟。想起我去年和某位已经上岸的学长聊的时候他说了一句话让我印象很深“初试是证明你学懂了机试是证明你会做。”第3天的主线因此很清晰不再继续堆新知识而是把已经看过的数据结构与算法一个一个亲手写成代码跑通然后总结出适合自己的代码模板。1.2 第3天的计划框架我给自己定了三个核心目标用一整天时间把数据结构重点章节的代码全部手写一遍包括线性表、栈、队列、二叉树、图以及基础的排序查找算法。至少完整写出三道模拟机试题按照考场标准限时然后自己根据评测逻辑做本地测试。把前两天积累的易错点整理成一张排查清单方便后面每天刷题前过一遍。计划看起来不复杂但做起来很耗时。代码手写和看别人写的代码完全是两码事看的时候觉得每一步都有道理轮到自己从头写常常卡在某个边界条件上。所以我上午只安排了两件事线性结构与栈队列的代码复现外加二叉树遍历的手写练习。中午休息半小时下午进入三道模拟题实战傍晚留两个小时做错题整理并规划Day4的侧重方向。2. 数据结构高频考点逐项代码过筛2.1 线性表、栈、队列的手写要点上午第一轮我从最基础的单链表开始。不要觉得这个太简单复试机试里很多题目的底层操作都是链表反转、链表中点、环形链表判断这类东西。考场上你当然可以直接用数组替代链表功能但有些题偏偏只给链表结构没得选。我手写了单链表反转这里推荐迭代写法三指针翻转pre、cur、next依次推进。别看代码短很多人一紧张就把next保存这一步漏掉导致链表断掉。核心逻辑我写在下面struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseList(ListNode* head) { ListNode* pre nullptr; ListNode* cur head; while (cur) { ListNode* next cur-next; cur-next pre; pre cur; cur next; } return pre; }写完这个我又练了判断链表是否有环的快慢指针法以及合并两个有序链表。合并这个操作面试里经常变形比如K个有序链表合并初级解法就是每次遍历K个头节点找最小复杂度O(KN)实际机试里遇到数据量大的题目最好用优先队列做优化。栈这块我重点练了括号匹配和单调栈。括号匹配是栈的经典应用也是最容易出细节问题的题比如只用栈记录左括号遇到右括号就出栈最后还要判断栈是否为空。单调栈的应用在机试里非常常见后面模拟题部分会详细展开。队列部分我主要复习了环形队列的手写实现。很多机试题目直接允许用库的queue但你要明白底层怎么运作尤其是数组实现环形队列时判断“队空”和“队满”到底该用front rear还是(rear 1) % size front想不明白就会在一些变种题里白送分。2.2 二叉树与图的遍历代码二叉树是复试机试的必考内容几乎没有跑偏的可能。我上午的主要时间就花在遍历上前序、中序、后序的递归写法很简单练完递归以后我又把非递归写法各写了一遍。非递归中序遍历需要用栈模拟递归过程根节点先入栈一路向左入栈到底然后出栈访问再转向右子树。这个写法经常作为模板题出现比如求二叉搜索树中第K小的节点本质上就是一个中序遍历的变体。我把核心代码也放出来vectorint inorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* st; TreeNode* cur root; while (cur || !st.empty()) { while (cur) { st.push(cur); cur cur-left; } cur st.top(); st.pop(); result.push_back(cur-val); cur cur-right; } return result; }除了遍历层序遍历BFS以及根据遍历序列重建二叉树是我额外花时间练的。重建二叉树这里特别容易出错光记住“前序找根中序分左右”不够必须能把递归代码完整写出来尤其是递归的边界——左子树在中序里的范围是[inLeft, rootIndex-1]当区间空就必须返回nullptr否则必崩。图的部分我复习了邻接表表示法、DFS与BFS模板以及拓扑排序。拓扑排序往往是机试中等题的核心步骤比如给定一些依赖关系让你判断是否能完成所有任务。这种题换个包装就出现了但核心还是“入度为0的节点入队列依次处理统计处理过的节点数是否等于总节点数”。2.3 排序查找的代码与复杂度边界排序算法在机试里一般不需要你手写快排直接用标准库sort就行但它有一个隐藏考点你不知道标准库sort的底层是什么复杂度是多少。大多数情况下sort是快排与插入排序的混合平均O(NlogN)但极端数据下的表现你要心里有数。我上午把归并排序手写了一遍因为有些题目需要你理解“归并”思想去解决逆序对问题而逆序对问题在复试中不算罕见。归并排序模板的要点是分治加合并合并时设置临时数组记录结果最后拷贝回原数组。写的时候最容易错的就是边界mid的取值、左右两个有序区间的指针移动条件。查找方面二分查找必须练到不需要思考就能写对。这里我分享一个自己用习惯的模板左闭右开写法int binarySearch(vectorint nums, int target) { int left 0, right nums.size(); // 左闭右开 while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } if (left 0 left nums.size() nums[left] target) { return left; } return -1; }这个模板的核心思路是右边界始终是“第一个满足条件的位置”配合二分查找目标的变种比如找第一个大于等于目标的元素、找最后一个小于等于目标的元素能省去很多判断。哈希表方面我主要复习了拉链法和开放定址法的概念以及unordered_map底层是哈希表、查找平均O(1)这个特性机试里遇到需要快速判断元素是否存在的题优先想到哈希。3. 机试真题风格模拟三道题的实际复现过程3.1 模拟题一单调栈求解“每日温度”变体下午一点半我按照机试的标准给自己限时90分钟做三道模拟题。第一道是“每日温度”的变体题目大意是给出一个数组对每个位置求出下一个更大元素出现的位置距离。这道题是典型的单调栈应用。我的思考过程是这样的维护一个从栈底到栈顶递减的栈记录元素下标。遍历数组时只要当前元素比栈顶元素大就说明栈顶元素找到了“下一个更大元素”此时弹出栈顶并计算结果。这样每个元素最多入栈一次、出栈一次整体时间复杂度O(N)。实际写代码时我一开始犯了两个错。第一个是把“下一个更大元素”和“右侧最大元素”搞混了差点用后缀最大值的思路去写。第二个是结果数组的初始化如果某个位置没有更大的元素答案应该是0但我一开始忘了给数组做初始化导致随机内存值输出。这两个都是机试中很常见的低级错误却会直接扣分。vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint ans(n, 0); stackint st; for (int i 0; i n; i) { while (!st.empty() temperatures[i] temperatures[st.top()]) { int idx st.top(); st.pop(); ans[idx] i - idx; } st.push(i); } return ans; }这道题做完以后我顺手把单调栈的另外几个常见变体在脑子里过了一遍比如矩形最大面积、接雨水、去除重复字母。不需要全部手写但是思路要能立刻反应出来不然考场上遇到相似题现场推导会非常消耗时间。3.2 模拟题二拓扑排序判断依赖关系能否完成第二道题是经典的课程表问题给定n门课程以及一组依赖关系比如学课程B之前必须先学课程A问能不能完成所有课程的学习。这个题看到“依赖”两个字第一反应就是拓扑排序。我选择了BFS的Kahn算法。大概步骤是先建邻接表记录每个节点的后继节点再统计每个节点的入度。将入度为0的节点加入队列依次弹出每弹出一个节点就把它的所有后继节点入度减1如果某个后继节点入度变为0就继续入队。最后统计成功弹出的节点数量如果等于总节点数就说明没有环可以完成否则说明存在循环依赖。这个题我对自己的要求是必须一次写对因为拓扑排序的核心代码并不长关键在于你能不能熟练地处理邻接表初始化、入度统计、队列操作这三步。我第一次写的时候邻接表用了vectorvector 但忘记resize运行报错后才想起来需要先分配好外层空间这又是一个现场容易出的低级问题。我后来总结出一个习惯拿到这种涉及图结构的题先把节点编号范围确定再确定存储方式。如果节点数是1000以内直接用二维数组或vector套vector都没问题如果超过这个范围就要考虑用哈希表映射。3.3 模拟题三动态规划的降维思路第三道题我选了最长递增子序列。这题有两种经典解法第一种是动态规划O(N^2)dp[i]表示以第i个元素结尾的最长递增子序列长度转移时遍历前面所有j如果nums[i]大于nums[j]就考虑更新dp[i]第二种是贪心加二分维护一个tails数组表示长度为len的递增子序列的最小末尾值对整个数组遍历时用二分查找找到合适位置替换。第二道解法是很多机试考官的偏爱因为它在数据范围达到十万级别时依然能跑得动而O(N^2)会直接超时。我练习时故意多花了一点时间把第二种解法彻底弄明白为什么可以替换而不是删除因为tails数组只记录了“当前递增子序列末尾的最小值”长度相同条件下末尾值越小后续扩展空间越大这是经典的贪心思路。我在本地测试时特意构造了几组边界数据空数组、单元素数组、全递减数组、全递增数组、重复元素数组。前四种都容易想到但重复元素数组很多人会忽略比如[2,2,2]的结果是1还是2正确答案是1因为题目要求严格递增等于也不行。这种细节一旦考场上没注意代码写得再漂亮也没用。4. 机试环境的坑提交前必须养成的检查习惯4.1 输入输出格式最容易在开场就丢分大部分同学备考机试时关注算法本身却忽略了平台的输入输出格式。很多机试平台要求从标准输入读取、向标准输出打印但会有“多组测试数据”这种情况。往年真题里有的题要求一句“有多组输入每行一组”有的题要求“第一行是数据组数T”这两者对应完全不同的读入写法识别错了第一题整题白给。多组数据这种格式我记得没有明确说明时通常会一直读到文件末尾所以C里可以这样写int n; while (cin n) { // 处理每一组输入 }而明确给了组数T的就要先读T然后循环T次来处理。识别方法很简单读题时先找两个关键词一个是“多组输入”另一个是“第一行输入一个整数T”。我Day3在练习模拟题的时候专门把自己以前看到过的几道题目翻出来重新确认它们的输入描述就是为了形成条件反射。还有输出格式的细节行末有没有空格、是否存在多行输出、大小写是否敏感、浮点数保留几位小数这些在评测时往往都以文本方式做精确对比。平时训练时建议直接在本地把样例输出跑出来用文本对比工具检查而不是肉眼看。4.2 时间复杂度的体感判断机试不同于初试你的程序必须真实运行所以复杂度不能只算理论值。一般常见的评测规模是1秒到3秒的时限如果按1秒来估C大约能跑1e8次简单运算Python大约是1e7到1e8之间但具体差距很大。理解这一点就能在做完题目之后快速评估自己的解法是否可能超时。我看到过不少备考者明明想到了O(N^2)的解法但数据范围是10^5也没细想就交上去了最后当然超时。判断数据范围的经验法则很简单如果N是10^5级别以上O(N^2)大概率会超时务必考虑O(NlogN)甚至O(N)如果N是1000级别O(N^2)通常安全。Day3下午我练这三道题时就强制自己写出复杂度再动手形成先估计后编码的习惯。4.3 调试手段的优先级机试调试时间很宝贵我记得大多数平台不允许随意打断点也没有非常高级的IDE调试环境所以必须养成用输出中间变量来排查的习惯。比如二分查找出问题时可以在关键位置打印left、right、mid的数值定位错误发生在哪一轮。另一个非常实用的习惯是构造小规模样例进行“手算对照”。做完一个算法后不要急着提交先构造一个只有三四个元素的输入自己在纸上手动推一遍期望输出再和程序输出对比。这个小技巧能抓住大量思路理解错误比反复打印大样例更有效率。我下午做第三道动态规划题时就这么操作在边界元素上抓到一个数组越界的隐患如果直接交上去评测机很可能报运行时错误。5. 常见问题与排查技巧实录5.1 运行错误的常见来源与定位机试里最常见的报错是运行时错误英文缩写通常是RE。个人经验里大概可以归结为以下几类数组越界、栈溢出、除零、野指针、空指针解引用。数组越界最为隐蔽比如动态规划里使用下标i-1却没有确保i1或者循环时误把写成。定位方法是把输入数据改小然后通过逐步注释代码或打印下标来缩小范围。栈溢出则通常出现在递归过深的情况。比如二叉树已经被退化成一条链递归深度达到10^5甚至更多程序直接爆栈。我在Day3复习二叉树时把递归遍历和非递归遍历都练了一遍其中一个重要原因就是防止考场上遇到退化树导致递归栈溢出。凡是数据规模可能很大的递归问题都要提前想好能否改成迭代写法。5.2 超时问题的排查思路超时这个问题会比运行时错误更让人抓狂因为程序没报错但就是一直卡着不出结果。遇到这种情况第一反应不是改算法而是先在本地用小数据测试确认程序在逻辑上能够终止。有时候是while循环的终止条件写错了程序陷入死循环有时候是存储结构没有复用导致算法实际复杂度比预想高。排查完死循环和重复计算以后再去考虑是否是数据规模导致的复杂度问题。这里我自己有一个习惯先看输入规模再看自己代码里有没有嵌套循环如果有两层循环确认外层N和内层M分别是多少如果N*M超过可接受范围尽早重构算法。不要在有明显复杂度缺陷的代码上反复调优那是浪费有限时间。5.3 面对一道完全没思路的题怎么办机试现场心理压力很大最怕遇到一道题看了十分钟仍然没有思路。我的处理策略是分优先级先把能拿的分都拿了即读完所有题后优先做自己最熟练、最好拿分的题目遇到卡壳的题先写下暴力解法作为保底哪怕只能过部分数据也比提交空代码强。暴力解法有时候也能引出优化方向。比如一个朴素的双重循环你会写出来以后自然可以发现内层的计算能否用前缀和优化或者能否用哈希表把查找从O(N)降到O(1)。Day3下午我做题期间出现过一次短暂卡壳当时的解决办法是强迫自己先写一个判断条件最直白的版本跑通了再逐步优化效果不错。6. 晚间收尾模板整理与Day4规划6.1 建立自己的代码模板库傍晚我在整理今天的收获时做了一件后面几天应该坚持的事把高频代码模板统一收集起来按主题归档。模板包括单链表反转、环形链表判断、二分查找、二叉树三种非递归遍历、层序遍历、拓扑排序、并查集模板、快速幂、常见动态规划状态转移。每个模板都备注一句话说明使用场景以及最容易出错的地方。这个模板库不是为了考场上直接抄而是为了加快回忆速度。人一天内反复写同一段代码写熟练以后考试时就算紧张肌肉记忆也能帮你写出框架。但平时如果不刻意整理隔几天再看这些代码又会变得陌生。我决定从Day4开始每天上午先默写模板库里的三到五个模板保证“手感在线”。6.2 明天计划与目标修正复盘Day3我发现时间分配有一点问题上午花在基础代码上的时间偏多导致下午模拟题的时间窗口比较紧三道题虽然完成了但第三道动态规划没有做额外的扩展训练。所以Day4我会这样调整上午直接进入高强度的模拟题训练限时120分钟做一套完整题目下午再针对暴露的薄弱点做专项补强比如图论里的最短路径与最小生成树。另外我计划Day4增加一个专项数学类技巧题包括整数拆分、最大公约数与最小公倍数、素数筛法、取模计算等。这些知识点在408初试里反复出现复试机试中也很常见甚至有时候题目本身不难但需要你掌握快速幂等基础技能才能在规定时间内完成。6.3 关于机试备考的几点个人体会经过Day3一整天的代码强化我最深的感受是复试机试准备的节奏和自己一个人闷头刷题有很大区别。初试备考你可以按照章节顺序慢慢推进但机试更像“限时射击”训练需要你在短时间内快速判断题型、匹配算法、输出代码。这种能力只能靠模拟真实考场氛围来练单独一道题一道题慢慢做效果有限。另一个体会是复盘错误比做新题更重要。今天我犯的输入格式误解、数组越界、边界条件漏判过去几天其实也出现过类似问题但都没记录下来。今天把它们写进了排查清单后面每做一个题之前先看一眼清单错误率明显下降。建议准备机试的同学也准备一份属于自己的“错误清单”记录下每次编译不通过、运行出错的真实原因这比任何参考书都更有针对性。我在实际刷题过程中还有一个小心得每天结束前用一句简短的话总结当天的核心收获。Day3这句我想写的是——“代码不是看会的是调试会了的。”准备复试的同学们加油一道题一道题啃下去考场上的手感一定不会辜负你。