我记得特别清楚那年我把王道数据结构的视频刷完基础篇的课后选择也能对个七七八八自信心满满地翻开强化篇准备拿算法题开刀。结果看到第一道题二十分钟只写出来一个LNode *p L-next;后面就卡死了。后来我才想明白基础阶段看代码和强化阶段写代码中间隔着的根本不是智商是方法。408数据结构算法题考察的从来不是你会不会背代码而是你在有限时间能不能独立设计出解法并用C语言完整写出来。这篇文章想聊的就是这件事——408王道数据结构强化阶段的算法题到底该怎么复习。无论你是刚开始强化、真题做得不顺手还是看到算法题就想跳过这篇应该都能帮上忙。1. 408算法题的分数大盘45分数据结构里真正决定差距的部分1.1 从分值结构看算法题的性价比408整张试卷150分数据结构稳定占45分。拆开来看数据结构的客观题大约11道每道2分合计22分左右剩下约23分是大题。大题里通常有一道是明晃晃的算法设计题也就是要手写代码的题目分值在10到15分之间另有一道偏应用性质比如画哈夫曼树、求最短路径、构造最小生成树这类不要求写完整代码。所以真正意义上的算法大题单题分值不算最高但它带来的心理压力和对复习方向的带动作用远超分数本身。如果你再看选择题就会发现里面有相当一部分题目是以代码片段为载体的给你一段二叉树遍历、快排或者二分查找的代码问它执行的输出是什么、功能是什么、某个条件写错会有什么后果。这些题目本质上也是算法题。把大题的15分和选择题里的代码相关题目加在一起算法相关的分数轻松超过20分。20分是个什么概念408从110提到125很多时候就差在这道算法题和选择题里那几道代码题上。更残酷的是选择题可以通过刷题技巧和背结论拿稳但算法大题考察的是底层设计能力没法临时突击只能靠强化阶段一天一天磨出来。1.2 真题的命题规律链表和二叉树为什么是常客如果你把近十年的408算法大题拉出来看会发现一个非常明显的规律链表是绝对的主角。2012年公共后缀、2013年奇偶拆分、2015年绝对值去重、2019年倒数第k个结点这些全部是链表操作题。链表为什么这么常见因为链表不连续存储、不能随机访问天然适合考察指针操作、边界判断和空间复杂度控制。面试造火箭、考试拧螺丝在408这里反过来了——它特别爱考这种代码量不大但每一行都可能有坑的题。二叉树紧随其后递归遍历、层次遍历、根据需求改写遍历过程都是高频玩法。排序和查找单独出道大题的次数不多但它们经常作为工具嵌入在算法设计里比如用快排的partition思路解决找第k小问题。另外你可以注意一个细节题目描述里经常出现设计一个时间上尽可能高效的算法尽量做到空间复杂度O(1)。这说明阅卷不只看代码对不对还会严格区分暴力解和最优解的得分档次。后面我会专门讲怎么抓这个梯度。1.3 强化阶段的核心目标从看懂走向会写基础阶段对代码的要求说穿了就是能看懂、能照着敲、能把选择题蒙对。但强化阶段必须完成一次跃迁看到一道没见过的题先设计算法再手写代码最后分析复杂度。我见过太多同学看王道视频时频频点头觉得这也不难啊结果一到自己动笔就对着空白答题卡发呆。问题出在复习逻辑没有切换。强化阶段刷算法题目标不是把答案背下来而是训练从问题到数据结构的映射能力以及把思路转译成C语言代码的执行力。我辅导学弟学妹时常打一个比方基础阶段学代码像看菜谱看完觉得什么菜都会做强化阶段是真正进厨房自己切菜、起锅、烧油不亲手炒糊几道菜永远不知道自己哪里不会。所以接下来这部分重点讲强化刷题的具体姿势。2. 强化刷题的正确姿势暴力先拿分再到一题三做2.1 先诊断拿到题写不出来到底卡在哪一步很多同学把写不出来归结为代码能力差其实细拆下来卡点大概有三种。第一种是读题之后不知道用什么数据结构。比如看到设计一个算法判断单链表是否有环第一反应不是可以快慢指针做而是这题到底要我干嘛。这种问题本质上是题型积累不够没建立起题目特征和数据结构的映射关系。要解决没有捷径只能通过大量刷题总结出看到什么问题该想哪类结构的清单。第二种是知道该用什么结构但推导不出过程。常见于树和图的题目你知道要用递归或者队列但递归函数怎么写、终止条件是什么、队列里先放什么脑袋里一团浆糊。这种情况我会建议先别管最优解试着用最笨的办法走一遍流程很多思路是在笨办法中逐渐清晰的。第三种是代码写出来了但跑不对。空指针、边界条件、循环终止条件写错这属于代码熟练度问题靠多练和错题复盘就能解决但很多人恰恰栽在这上面——明明算法思路是对的代码就是有几个小错考试的时候又没法调试只能干瞪眼。拿我自己当年的经历说刚开始练链表找中间结点第一反应是先遍历求长度再走一半后来看答案发现快慢指针一度很沮丧觉得暴力法白写了。后来才明白暴力法帮我理解了链表不能随机访问这个本质属性快慢指针正是在这个理解之上自然生长出来的。所以别急着否定笨办法先诊断自己卡在哪一环再对症下药。2.2 第一遍别看不起暴力解法强化阶段做算法题第一遍一定要允许自己写暴力解。什么叫暴力解就是不用任何高深技巧最直白地把题目要求翻译成代码。举单链表倒数第k个结点这个例子最简单的做法是第一趟遍历求出链表长度n第二趟从头走n-k步找到倒数第k个结点。这个解法不需要任何技巧但它的价值在于先保证你遇到这道题不交白卷在考场上能拿到相当一部分基础分。很多同学觉得我写暴力解太丢人了一定要想最优解这种心态在练习时会严重拖慢进度。你以为在优化实际上半小时过去了连暴力代码还没写完。强化阶段的策略恰恰相反第一遍先求能做出来不要去管优雅不优雅。暴力解不仅能拿分还能帮你确认自己理解题意没有偏差。而且从评分角度来看一道算法大题往往按点给分结构定义是否正确、主体逻辑是否成立、边界有没有照顾到。只要你写出了能跑通的暴力解基础分就到手了后面再谈优化。2.3 第二遍理解优化而不是背答案暴力解写完再去看答案或者书上的标准解这时候你的学习效率会完全不一样。因为你不是空着脑子去记答案而是带着自己的暴力代码去对比标准解的优化点到底在哪里它靠什么手段减少了时间或空间消耗比如刚才那个链表倒数第k个题目暴力解法需要两次遍历第一趟求长度第二趟找位置。标准解用两个指针p先走k步然后p和q同步走当p到达表尾时q正好指向倒数第k个结点。优化点在于它把求长度和找位置合并成了一趟扫描时间复杂度从两次遍历变成一次遍历空间复杂度仍然是O(1)。看答案时我建议你先问自己三个问题第一标准解为什么能这么写它的核心思想是什么第二如果我把p先走的步数改成k-1步代码需要怎么调整第三这个算法在什么边界情况下会出错带着问题去拆解答案印象会深得多。最忌讳的是背代码——背下来也不理解下次题目稍微变个形你照样写不出来。2.4 第三遍隔天复现练成肌肉记忆很多同学刷题的方法是把答案看懂、抄一遍然后就认为这题我会了。真相是抄答案属于被动学习记忆留存率低得可怜。真正有效的方法是隔天复现。具体操作是这样的你今天做完一道题不管是暴力还是最优解都关上答案。等到第二天拿一张白纸重新把这道题完整写一遍要求20分钟内独立写完不能看任何提示。如果卡住了说明你昨天的理解和吸收还不够需要回去重新过一遍如果能顺利写出来这道题才算真正属于你。为什么要隔天因为人在短时间内的记忆是虚假的第二天还能复现才是真正掌握了。这个方法练到最后你会发现自己看到某些题目时根本不需要思考手就直接开始写了。这就是肌肉记忆。408考场上时间紧张如果每道算法题都要现场推导一遍你很难做完后面的大题。高频题型和模板就该练到不用过脑子就能写出来的程度。这个思路是贯穿着整个强化阶段的不是说只针对某一题。3. 高频手写代码模板链表、二叉树、排序、查找各一套3.1 链表题的基础模板头插法、尾插法、快慢指针408算法题默认用C语言手写不依赖库函数。链表题最基础的三个模板头插法建立链表、尾插法建立链表、快慢指针。这三个模板几乎是所有链表题的地基。先看结构体定义和头插法逆置这个操作在真题里反复出现比如把链表逆序、把链表按某种规律重新排列都会用到。typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 头插法逆置链表原地操作 void reverse(LinkList L) { LNode *p L-next, *q; L-next NULL; while (p ! NULL) { q p-next; p-next L-next; L-next p; p q; } }理解头插法的关键每次把当前结点插入到头结点之后所以最后一个处理到的结点会变成链表的第一个有效结点从而实现逆序。快慢指针的模板也很固定// 找单链表的中间结点 LNode* findMid(LinkList L) { if (L NULL || L-next NULL) return L; LNode *slow L-next, *fast L-next; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }这个模板的核心是条件fast ! NULL fast-next ! NULL少了任何一个判断都可能出现空指针解引用。建议把这句话当成固定搭配背下来考试时不要现场推。3.2 二叉树递归三件套遍历、求值、查找二叉树题的结构体定义和递归框架先写一遍typedef struct BiTNode { int data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; // 先序、中序、后序只差一行访问位置 void order(BiTree T) { if (T NULL) return; // visit(T); order(T-lchild); // visit(T); order(T-rchild); // visit(T); }然后是二叉树最常考的高度计算几乎所有求XX的题都会用到这个递归思想int treeHeight(BiTree T) { if (T NULL) return 0; int left treeHeight(T-lchild); int right treeHeight(T-rchild); return (left right ? left : right) 1; }递归函数做题有一个通用心法只关心当前节点要做什么左右子树交给递归。求高度就是当前节点的高度等于左右子树中较高者加一其他的不用多想。这个思维一旦建立很多二叉树题都变得很像套公式。3.3 层次遍历的扩展求层数、宽度、判断完全二叉树层次遍历的模板非常重要它能衍生出很多题目求二叉树层数、求二叉树最大宽度、判断完全二叉树。408手写时建议直接用数组模拟队列不要依赖C的queue头文件。#define MaxSize 100 int countLevel(BiTree T) { if (T NULL) return 0; BiTree q[MaxSize]; int front 0, rear 0; q[rear] T; int level 0; while (front rear) { int size rear - front; // 当前层节点数 level; while (size--) { BiTree p q[front]; if (p-lchild) q[rear] p-lchild; if (p-rchild) q[rear] p-rchild; } } return level; }这个模板里size rear - front是处理按层输出的关键每次循环前先记录当前层有多少个节点然后只处理这一层。如果你要求最大宽度只需要在每一层记录size的最大值如果你要判断完全二叉树只需要在层次遍历过程中遇到第一个缺少孩子的节点后检查之后是否全是叶子。一个模板可以解决一整类问题。3.4 快速排序与二分查找的手写模板排序和查找的代码模板我不建议死背但快速排序的挖坑填数版本特别适合考场手写因为它逻辑清晰、不容易错。void quickSort(int A[], int low, int high) { if (low high) { int pivot A[low]; int i low, j high; while (i j) { while (i j A[j] pivot) j--; if (i j) A[i] A[j]; while (i j A[i] pivot) i; if (i j) A[j--] A[i]; } A[i] pivot; quickSort(A, low, i - 1); quickSort(A, i 1, high); } }注意两个细节A[j] pivot和A[i] pivot必须用等号否则数组里有大量重复元素时会陷入死循环每一轮挖坑填数后A[i]的位置就是pivot的最终位置。二分查找模板int binarySearch(int A[], int n, int key) { int low 0, high n - 1; while (low high) { int mid low (high - low) / 2; if (A[mid] key) return mid; else if (A[mid] key) low mid 1; else high mid - 1; } return -1; }循环条件low high和更新规则low mid 1、high mid - 1必须配套使用很多人写二分查找翻车就是这里没记牢。3.5 手写代码时容易被忽略的答题外貌代码模板固然重要但考场上有一些和算法本身无关的细节同样影响得分。首先如果题目没有给你结构体定义你要先自己写出来这本身就是分数其次核心步骤建议加一行注释比如// 快指针先走k步让阅卷老师知道你每一步在干什么最后所有算法题都别忘了写时间和空间复杂度分析哪怕只写一行时间O(n)空间O(1)也能让阅卷人看到你的复杂度意识。这些细节在平时练习时就要养成习惯别等上了考场再临时注意。4. 高频题型逐个过链表操作、二叉树递归、排序应用、图的遍历4.1 链表快慢指针和头结点是两大武器链表题翻来覆去就那几种变化中间结点、倒数第k个结点、环检测、公共后缀、奇偶拆分、绝对值去重。它们的解法高度依赖两个武器头结点和快慢指针。带头结点的链表有一个巨大优势——头结点永远不变所以不需要返回新的头指针所有操作都可以原地进行。比如奇偶拆分题目要求把链表中序号为奇数的结点和偶数序号的结点分别拆成两条链表做法就是同时维护两个尾指针遍历原链表时用编号奇偶决定接到哪条链表上。这种题的关键在于画图。我建议你也养成一个习惯链表题一定先画三个结点的示意图手动模拟一遍指针变化再写代码不要凭空脑补。画图能让你避免至少八成指针错误。4.2 二叉树递归与非递归的取舍二叉树题在408中多半围绕递归展开因为递归代码短、思路清晰阅卷老师也容易看懂。求高度、求结点数、求叶子节点数、判断平衡树、翻转二叉树这些都可以用递归模板快速解决。把递归框架记牢剩下的就是往里面填不同的业务逻辑。但有些题目会考察非递归最典型的就是非递归中序遍历。选择题里可能会出现一段栈模拟中序遍历的代码让你判断输出顺序或者栈的变化过程所以非递归中序也需要掌握至少能看懂、能默写。void inOrder(BiTree T) { BiTree stack[MaxSize]; int top -1; BiTree p T; while (p ! NULL || top ! -1) { while (p ! NULL) { stack[top] p; p p-lchild; } if (top ! -1) { p stack[top--]; visit(p); p p-rchild; } } }这个模板背后的逻辑是一直往左走并入栈走到空之后出栈访问节点然后转向右子树。你不需要现场推导背下来能写就行。4.3 排序死记不如会推排序算法在408算法大题里很少让你裸写快速排序或归并排序但会以应用题的形式出现。比如设计一个算法找出无序数组中第k大的元素最优解就是利用快速排序的partition函数每趟划分后枢轴元素的位置就是它最终的位置如果枢轴位置正好是k就找到了答案。所以强化阶段刷排序重点不是把堆排序、希尔排序、归并排序的代码全部背下来而是做到三件事第一快速排序的partition函数能独立写出来第二能分析各种排序的时间复杂度、空间复杂度、稳定性第三能用归并排序的合并过程去解决求逆序对数量这类题目。选择题里排序考得很细比如问某趟排序后的序列长什么样这时候需要你真正理解排序过程而不是背结论。4.4 图论邻接表和DFS/BFS务必过关图在408算法大题里出现的频率不算高但你不能完全放弃因为选择题爱考而且万一哪年突然考一道图的算法设计你不会写就会很被动。强化阶段图这块我建议只抓三个点邻接表存储结构的定义、DFS递归写法、BFS用队列的写法。#define MaxVertexNum 100 typedef struct ArcNode { int adjvex; struct ArcNode *next; } ArcNode; typedef struct VNode { char data; ArcNode *first; } VNode, AdjList[MaxVertexNum]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; int visited[MaxVertexNum]; void DFS(ALGraph G, int v) { visit(v); visited[v] 1; for (ArcNode *p G.vertices[v].first; p ! NULL; p p-next) { int w p-adjvex; if (!visited[w]) DFS(G, w); } }图的最短路径、最小生成树408更愿意出成手算题而不是代码题所以你不要把时间花在背Dijkstra或者Prim的完整代码上知道算法过程和手算步骤就够了。5. 考场上的算法题答法思路、代码、复杂度一个都不能少5.1 15分钟的时间分配想清楚再下笔408考试总共180分钟题量很大。一道算法大题我建议从读题到写完控制在15分钟左右。前3分钟想思路不要急着写代码想清楚数据结构定义和核心算法流程后用10分钟写代码和注释最后2分钟检查边界条件顺带把复杂度分析写上。如果你超过20分钟还卡在核心逻辑上就果断先写暴力解哪怕多花一点时间把能拿的分先拿到。很多同学以为写出最优解才是胜利实际上在考场上把暴力解完整写对已经能拿到一半以上的分数。5.2 阅卷视角思路分、代码分、复杂度分从哪里来408算法题的评分虽然各年份细节不同但大方向是分成几个部分。首先是思路分阅卷老师会看你有没有用文字描述算法思想。很多同学喜欢整个答题区域只写一段代码这容易丢掉思路分。你不需要写长篇大论两三行话点出核心思想就够了比如采用双指针法令快指针先走k步然后快慢指针同步移动。其次是代码分包括结构体定义是否完整、核心逻辑是否正确、边界条件有没有考虑。最后是复杂度分用一句话写清时间复杂度和空间复杂度。平时练习时不妨按照这个标准给自己的答案打分这样能清楚看到自己的薄弱点。5.3 一道典型题的全流程作答示范用查找单链表倒数第k个结点这道题完整演示一下考场上应该怎么作答。已知一个带头结点的单链表L设计一个尽可能高效的算法输出链表中倒数第k个位置结点的数据值。若k非法则返回0。思路描述设置两个指针p和q初始都指向第一个有效结点。让p先走k步此时p和q相距k个结点。之后p和q同步向后移动当p到达表尾为空时q正好指向倒数第k个结点。算法步骤判断k是否小于等于0或链表为空若是则返回0。令p和q都指向L-next。p走k步如果中途遇到空结点说明k大于链表长度返回0。p和q同步移动直到p为空。返回q-data。代码实现int findKth(LinkList L, int k) { if (k 0 || L-next NULL) return 0; LNode *p L-next; LNode *q L-next; // 快指针先走k步 for (int i 0; i k; i) { if (p NULL) return 0; p p-next; } // 快慢指针同步移动 while (p ! NULL) { p p-next; q q-next; } return q-data; }复杂度分析时间复杂度O(n)空间复杂度O(1)。这个格式就是考场上最稳妥的答题格式。平时练习时对照这个标准看自己差在哪一块。5.4 平时模拟纸笔手写限时作答很多同学平时习惯在IDE里写代码写完还能编译调试但考场是纸笔作答没有编译器没有代码补全没有报错提示。所以强化阶段刷算法题一定要有意识地切换到纸笔模式。我建议每周至少三次拿白纸和笔给自己定20分钟倒计时像考试一样完整写一道算法题包括思路、代码、复杂度分析。写完再翻书对照。这个过程一开始会很痛苦你会发现自己在IDE里能写对的小细节纸笔的时候全在出错但练上两周就会明显改善。6. 强化阶段最容易踩的五个坑6.1 死磕最优解连暴力分都没拿第一个坑就是做题时非要一步到位想最优解。曾经带过一个学弟做一道判断单链表是否有环的题非要在半小时内想出一个比快慢指针还好的办法最后答案没做出来还浪费了大量时间。强化阶段的第一原则先写完暴力解再谈优化。暴力解不仅能拿分还能帮你理清思路。你以为你在追求完美其实是在逃避先写出来这个基本功。6.2 只看不写考场上大脑空白第二个坑是只看书、只背题、不动手。很多同学在强化阶段把王道书上的算法题从头到尾看了一遍觉得自己都懂了。到了考场看到类似的题大脑一片空白连结构体定义都写得磕磕绊绊。原因很简单看代码和写代码是两种完全不同的认知过程。看代码是识别信息写代码是提取信息后者要难得多。所以无论你多忙每天至少手写一道算法题保持手感和记忆。6.3 依赖C标准库考场环境根本不给用第三个坑是平时刷力扣刷多了习惯了vector、queue、stack、sort这些现成容器一到408考场就傻眼了。408明确要求用C语言完成手写你不能写queueint q必须自己定义数组模拟队列你不能直接调用sort必须自己写快排。从强化阶段开始就要有意识地把所有代码转换成C语言的手写版本。结构体自己定义队列用数组模拟栈用数组模拟临时容器一律不用标准库。这样到了考场才不需要临时切换。6.4 不写思路不写注释回头自己都看不懂第四个坑是平时练习只写代码不写思路不写注释。考场上不会做的时候思路文字能帮你拿分回头看错题时注释能帮你快速回忆当时的思路。更重要的是如果你平时就练习把思路落到文字上考试时也更容易形成先想清楚再动手的习惯。我记得有次翻自己一个多月前做的题只有一堆代码而没有任何注释完全想不起来当时为什么这么写那种感觉真的很绝望。6.5 盲目刷新题不复盘错题最后一个坑是刷题只求数量每天刷一堆新题但错过的题从来不去管。算法题复习的效率很大程度取决于错题复盘的质量。我建议准备一个错题清单不是抄整道题而是只记录三个信息题目类型、我卡在哪个环节、正确的思路是什么。比如链表求公共结点——忘记先让长链表走差值步——利用同步移动抵消长度差。到了复习后期不看题集只看这份清单就能快速定位自己的知识盲区。写到这里我想起去年帮一个学妹冲刺408她前期最大的问题就是算法题看懂了不手写我强制要求她每天给我发一张手写代码的照片坚持了一个多月后她从看到题就慌变成看到题会先写暴力再想优化。她说了一句话我一直记得原来算法题考的不是智商是熟练度。如果你现在正被408数据结构算法题折磨这句话也送给你。别想太多拿起笔从今天这道题开始写。