408 算法大题保底 11 分抢分模板(全科通用应试版)
IMPORTANT
408 算法大题(第 41 题,15分)核心应试铁律:
- 严禁交白卷! 408 采用分步踩分制:设计思想(3
4分)+ C/C++代码实现(78分)+ 时空复杂度分析(2~3分)。- 想不到最优解,直接写暴力解/辅助数组解! 阅卷老师只会扣除 2~3 分算法最优分,逻辑跑通即可保底稳拿 10~11 分!
- 书写严格“三段式”:严禁把思想混在代码里,段落分明是阅卷老师送分的关键。
零、 语法扫盲:考场上必须搞懂的 C 语言“底层与套路”
很多同学背不下代码,是因为不知道代码里这些符号是**“固定公式”还是“灵活变量”**。这里先讲透两个最致命的语法点:
1. int *count = (int *)malloc(sizeof(int) * (n + 2)); 彻底拆解
- 为什么要加
*(int *count)?- 在 C 语言里,普通变量
int a只能存一个整数(比如5)。 - 而我们需要动态申请一整串连续的数组空间,系统在内存里分好空间后,只会把**这块空间首地址(门牌号)**交给你。
count是一个指针变量,加*就是告诉编译器:“count存的是这串空间的基地址,它不是普通数字,而是一个指向连续内存首地址的指针,后面你可以像用普通数组一样用count[i]!”
- 在 C 语言里,普通变量
- 这是固定写法吗?需不需要死记?
- 结论:这前半部分和中间是 100% 死记硬背的固定句式!
- 万能背诵公式:
- 唯一变的地方:只有
(n + 2)这个大小!- 如果元素最大值是 ,开到 是为了安全防越界(因为 C 数组下标从 0 开始,你要用到下标 ,长度至少是 ;开到 彻底杜绝手抖越界)。
2. 链表结构与指针完全解惑(说死、说透,绝不含糊)
408 真题中链表的标准定义如下:
typedef struct LNode {
int data; // 存放节点数据
struct LNode *next; // 存放下一个节点的地址(指针)
} LNode, *LinkList;| 节点类型 | 地址 (示意) | 数据域 (data) | 指针域 (next) | 说明 |
|---|---|---|---|---|
头节点 (由 L 指向) | 0x100 | (无效/空) | 0x200 | 哨兵,不存数据,L->next 的值就是 0x200 |
| 首元节点 | 0x200 | a | 0x300 | 第一个真正存放数据的节点 |
| 第二个节点 | 0x300 | b | NULL | 最后一个节点,指针为空 |
flowchart LR 节点定义 L["<b>L (头节点)</b><br/>------------<br/>data: 无效<br/>next"]:::head N1["<b>首元节点</b><br/>------------<br/>data: a<br/>next"]:::data N2["<b>第二个数据节点</b><br/>------------<br/>data: b<br/>next"]:::data NULL((NULL)):::null %% 连线 L -- "L->next" --> N1 N1 -- "next" --> N2 N2 -- "next" --> NULL
① LNode 和 *LinkList 到底怎么用?直接“说死”!
- 这两者的物理本质完全一样:都是指向节点地址的指针!
- 但是,在 408 考场上有严格的“潜规则角色分工”,死记这一句:
- 代表整条链表时,用
LinkList:比如函数参数findKthFromEnd(LinkList L, int k),这里的LinkList L和int k100% 是题目题干直接给出的函数签名,你考场上直接抄题目给的这一行就行! - 代表跑腿移动的工作指针时,用
LNode *p:只要是在函数内部定义用来走路、查数的指针,全部写成LNode *p = L->next;。(🔴L表示头节点,L->next 是首元节点,注:头节点不带data,只有next),(首元节点是第一个真正存放数据的节点)
- 代表整条链表时,用
- 一句话口诀:“头表用 LinkList,跑腿用 LNode *”!
② p->data 和 (*p).data 是怎么回事?为什么是 p 而不是 *p?
- 在 C 语言中:
因为 ==🔴p 这个变量本身,里面装的就是“下一个节点的地址==”。
p = p->next; 的意思就是:把下一个节点的地址(p->next),重新装进 p 里面。 左右两边都是地址,完美匹配。
而 ==🔴*p 代表的是“整个节点==”。你不能把“一个节点的地址”塞给“一个完整的节点”(完整节点有data和next即地址),这不符合语法。所以遍历只能用 p
p是一张纸条,上面写着节点的内存地址(门牌号)。*p是顺着纸条找过去,拿到这一整间实体屋子(结构体本身)。- 如果拿到了实体屋子
(*p),要取里面的数据,必须用英文句号点出来:(*p).data。 - 但是写
(*p).data太麻烦了! 还要打括号,C 语言专门发明了一个箭头语法->作为语法糖: - 一句话死记:
- 如果变量是指针(手里拿的是地址),直接用箭头指向成员:
p->data、p->next; - 绝不需要写成什么
*p->data(这是错的,会因为运算符优先级导致报错)!
- 如果变量是指针(手里拿的是地址),直接用箭头指向成员:
③ p = p->next; 是什么意思?是把下一个节点提到这个节点来吗?
- 不是!节点本身纹丝不动,本质是“把 p 指向的下一个节点的地址,现在赋给 p 自己”,让指针沿着链表往前跨一步!
- 底层赋值彻底拆解:
- 等号右边
p->next:取出当前节点所存的“下一个节点的内存地址”; - 等号左边
p =:把这个新地址装进指针变量p; - 结果:指针
p顺着箭头方向往前挪动了一格,现在它正正好好指向了下一个节点!
- 等号右边
- 生动场景对应:
- 链表方向是:
头节点 -> 第1个节点 -> 第2个节点 -> ... -> NULL。 p就像队伍里的一个安检员。当前站在第 1 个节点。- 执行一次
p = p->next;,安检员就顺着队伍向前迈进一步,站在第 2 个节点前! - 所以
while(p != NULL) { length++; p = p->next; }就是:安检员顺着队伍一步一步往前走,走一步计数器length加 1,一直走到队伍尽头(踩到 NULL 空指针)停下来!
- 链表方向是:
④ 函数签名 int findKthFromEnd(LinkList L, int k) 里的参数哪来的?考场要我自己想吗?
- 结论:100% 是题目题干直接给出的!考场直接原样照抄!
- 408 统考真题最后永远有一句话:“请设计一个算法……函数原型为
int findKthFromEnd(LinkList L, int k)”。 - 阅卷要求严格匹配官方接口名和参数名:
LinkList L:题目把整条链表的头指针交给你;int k:题目给出的输入数据(比如找倒数第 个)。
- 考场答题时,直接抄下题目这行函数头,敲上大括号
{ ... }往里填代码即可!
一、 考场答题标准三段式模板
无论题目难度如何,试卷上永远整齐列出以下三段:
(1) 算法的基本设计思想:
[用 3~5 句话写清:核心逻辑、辅助空间大小、遍历轮数]
(2) 算法的 C/C++ 核心代码实现:
[规范函数签名与主体,变量命名规范,必须包含必要边界判断]
(3) 算法的时间与空间复杂度分析:
时间复杂度为 O(...),空间复杂度为 O(...)。二、 408 历年最高频三大题型“保底代码模板”
模板 1:【顺序表 / 数组类】—— “空间换时间”全局辅助标记数组法
- 适用真题:2011(中位数)、2013(主元素)、2018(未出现的最小正整数)、2020(三元组最小距离)。
- 秒杀思维:只要数据范围有限或数组长度为 ,直接开辟一个全 0 辅助数组
count,遍历一次原数组打标记,再遍历一次辅助数组得答案。彻底免除复杂二分和快排分割!
// 适用场景:查找未出现的最小正整数 / 频次统计类(以 2018 年真题为例)
int findMissingOrFrequent(int A[], int n) {
// 1. 动态分配辅助数组(固定句式:给长度 n 开辟 n+2 大小)
int *count = (int *)malloc(sizeof(int) * (n + 2));
// 初始化清零:数组下标覆盖 0 到 n+1
for (int i = 0; i <= n + 1; i++) {
count[i] = 0;
}
// 2. 遍历原数组,记录元素出现情况(空间换时间)
for (int i = 0; i < n; i++) {
// 【核心疑问 1】:为什么必须是 A[i] > 0 && A[i] <= n?
// 原因有两个:
// ① 题目求的是“正整数”,负数和 0 根本不影响结果,直接忽略;
// ② 防止数组下标越界!如果 A[i] 是 9999999 或负数,直接执行 count[A[i]] 就会产生“段错误 (Segment Fault)”直接爆零。
// 同时,长度为 n 的数组,未出现的最小正整数理论最大值只能是 n+1,超出 n 的数直接丢弃即可。
if (A[i] > 0 && A[i] <= n) {
count[A[i]] = 1; // 标记该正整数已经出现过
}
}
// 3. 扫描辅助数组,寻找目标答案
// 【核心疑问 2】:为什么 int ans = n + 1?
// 因为最坏情况是:原数组包含了 1, 2, ..., n 所有连续正整数。
// 那么未出现的最小正整数恰好就是 n + 1!默认设为 n + 1,如果中间没找到空缺,它就是正确答案。
int ans = n + 1;
// 【核心疑问 3】:为什么 i 从 1 开始,而不是从 0 开始?
// 因为题目找的是“正整数”!正整数是从 1 开始的(1, 2, 3...),0 不是正整数,count[0] 没有业务意义,所以从 1 扫到 n。
for (int i = 1; i <= n; i++) {
if (count[i] == 0) { // 第一次遇到标记为 0 的下标,就是第一个缺席的正整数
ans = i;
break; // 找到最小的,立即终止跳出循环
}
}
// 4. 释放动态内存并返回
free(count);
return ans;
}- 卷面复杂度踩分点:
- 时间复杂度:(遍历原数组与辅助数组各一次,为线性阶)。
- 空间复杂度:(使用了大小为 的辅助数组空间)。
模板 2:【单链表类】—— “两趟扫描折返”与“三指针就地逆置”
- 适用真题:2009(倒数第 k 个)、2012(共享后缀首节点)、2015(绝对值去重)、2019(链表折叠交叉重排)。
武器 A:数长度折返法(解决所有找倒数、找中点、找前驱问题)
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;
int findKthFromEnd(LinkList L, int k) {
// 【核心疑问 4】:为什么第一行要写 if (L == NULL || L->next == NULL || k <= 0) return 0;?
// 这是阅卷老师的最爱(防御性编程踩分点):
// ① L == NULL:万一题目给的是空指针,后面去读 L->next 会直接内存崩溃;
// ② L->next == NULL:408 默认带头节点,L->next 为空说明链表是空表(没有有效数据节点);
// ③ k <= 0:倒数位置非法(不可能找倒数第 0 个或负数个节点)。
// 一行拦截全部非法输入,稳稳拿住边界分!
if (L == NULL || L->next == NULL || k <= 0) return 0;
// 第一趟遍历:统计链表有效节点总长度 length
int length = 0;
LNode *p = L->next; // 避开无数据的头节点,从第一个有效节点开始扫( p 指向【首元节点】(第一个数据节点),不是头节点)
while (p != NULL) {
length++;
p = p->next;
}
// 边界拦截:要求找倒数第 10 个,但整条链表一共才 5 个节点,直接查无此人返回 0
if (k > length) return 0;
// 第二趟遍历:倒数第 k 个等于正数第 length - k + 1 个(k从1开始)
// 【为什么步进 length - k 次?】
// 因为 p 重新从 L->next 出发时,已经稳稳站在第 1 个节点上了!
// 要到达第 (length - k + 1) 个节点,只需要向前再走:(length - k + 1) - 1 = length - k 步!
p = L->next;
(这里重新赋值是因为因为它在上面while循环一直走到 p == NULL 才停止,所以此时的p已经变成了NULL(它掉下悬崖了)。)
( 此时 p 已经是 NULL 了,没法接着往后走,因为后面没东西了!p = L->next; 【重置】:必须把 p 重新拉回到起跑线(首元节点))
for (int i = 0; i < length - k; i++) {
p = p->next; // 每走一步,指针向前推进一个节点
}
// 输出并返回成功标记 1(严格契合 2009 题干要求)
printf("%d\n", p->data);
return 1;
}注: 在 408 数据结构里,明确记住:“节点的序号”和“循环的变量(如 i、j)”是两码事,千万别混为一谈!
- 节点的序号(第几个):绝对是从 1 开始算的。(首元节点是第 1 个,不是第 0 个)。
- 数组的下标:是从 0 开始的(
a[0]是第 1 个元素)。 - 循环变量(i):从几开始,完全取决于你想“走几步”。
为什么是 for (int i = 0; i < length - k; i++)?
这里的 i 从 0 开始,不是因为节点从 0 开始编号,而是因为**“移动的步数”是从 0 开始计的**:
i = 0时:走第 1 步i = 1时:走第 2 步- …
i = length - k - 1时:走第 length - k 步
你看,i 从 0 开始,循环到 length - k - 1,刚好执行了 length - k 次,也就是走了 length - k 步。
灵魂拷问:为什么在首元节点上,走 length - k 步,就能到倒数第 k 个?
假设链表一共 5 个节点(length = 5),我们要找倒数第 2 个(k = 2)。
倒数是从1开始而不是0;
正数算一下:倒数第 2 个,其实就是正数第 4 个(5 - 2 + 1 = 4)。(因为数组下标从1开始)
初始状态: p = L->next;
此时 p 已经站在了第 1 个节点上了!它一步都没走!
接下来我们要走到第 4 个节点,还需要走几步?
- 从 第1个 走到 第2个:1步
- 从 第2个 走到 第3个:2步
- 从 第3个 走到 第4个:3步
所以,我们要走 3步。
公式:目标位置 - 1 = 4 - 1 = 3。
代入字母:(length - k + 1) - 1 = length - k。
此时 length - k = 5 - 2 = 3。所以 for (int i = 0; i < 3; i++),刚好循环 3 次,走 3 步,停在正数第 4 个节点上,也就是倒数第 2 个。完美!
补充:如果题目是从头节点(L)开始呢?
假设 p = L;(此时 p 站在头节点上,头节点不算有效数据)。
要找正数第 4 个节点,p 需要走几步?
从 头节点 走到 首元节点(第1个) 是 1 步;走到 第4个节点 就是 4步。
如果是这种情况,循环就可以写成:
// 走 4 步
for (int i = 0; i < length - k + 1; i++) {
p = p->next;
}💡 总结口诀
-
找第几个节点:序号永远从 1 开始。
-
指针走几步:看它起跑线在哪。站在首元节点,走到第
n个,只需走n-1步;站在头节点,走到第n个,就要走n步。 -
for 循环的
i:你把它当成“计步器”就行,从 0 开始计,计到< 目标步数,就能走完。
武器 B:三指针原地反转链表(408 必备基本功)
// 将以 L->next 开始的单链表就地逆置
void reverseLinkedList(LinkList L) {
if (L == NULL || L->next == NULL) return; // 容错:空表或无有效节点直接返回
LNode *p = L->next; // p 指向当前要掉头的节点
LNode *pre = NULL; // pre 指向逆置后的前驱节点(原表头逆置后变成表尾,尾节点的 next 是 NULL,所以初始化为 NULL)
LNode *next = NULL; // next 用来临时保存后继,防止断链找不到路
// 四步核心动作循环(背这 4 句流水线):
while (p != NULL) {
next = p->next; // 1. 暂存后继:先把后面的路存起来,否则掉头后找不到后继
p->next = pre; // 2. 指针掉头:让当前节点的 next 指向前驱 pre
pre = p; // 3. 窗口前移:pre 挪到当前节点
p = next; // 4. 窗口前移:p 挪到暂存的下一个节点
}
L->next = pre; // 关键收尾:循环结束时 p 为 NULL,pre 停在原链表最后一个节点(即新链表首节点),头结点重新挂接!
}- 卷面复杂度踩分点:
- 时间复杂度:。
- 空间复杂度:(仅使用固定常数个辅助工作指针)。
模板 3:【二叉树类】—— “前序/后序递归遍历万能模板”
- 适用真题:2014(二叉树带权路径长度 WPL)、2017(中序表达式输出)、2022(判断是否为二叉排序树)。
- 秒杀思维:二叉树大题只要能写递归,代码极短(5~10 行),逻辑天生优美,极易拿满 15 分!
typedef struct BiTNode {
int weight; // 节点权值或数据
struct BiTNode *left, *right;
} BiTNode, *BiTree;
// 深度优先遍历万能函数(以计算 WPL 为例)
int calcWPL(BiTree root, int depth) {
if (root == NULL) return 0;
// 递归基(叶子节点):完成题目特定条件结算
if (root->left == NULL && root->right == NULL) {
return root->weight * depth;
}
// 递归下推:累加左子树与右子树
return calcWPL(root->left, depth + 1) + calcWPL(root->right, depth + 1);
}
// 供题目调用的顶层接口函数
int getTreeWPL(BiTree root) {
// 【关键细节辨析】:什么时候传 0?什么时候传 1?
// 题目如果明确说:“根节点的深度为 0”,或者“根节点到自身的路径长度为 0”,传 0:calcWPL(root, 0);
// 题目如果说:“根节点所在的层数为 1”,或者“根节点深度为 1”,传 1:calcWPL(root, 1);
// 看清题干第一句话!两者的区别只在初始层数参数,函数本体完全一模一样!
return calcWPL(root, 0);
}- 卷面复杂度踩分点:
- 时间复杂度:(树中每一个节点仅访问一次)。
- 空间复杂度:(递归工作栈深度取决于树高 ,最坏情况下单支树为 ,平衡时为 )。
三、 命题人常见扣分陷阱(避坑指南)
- 指针解引用前未判空:
- 极易扣分点:写
p->next之前没有检查p != NULL。单链表题目开头永远加上:if (L == NULL || L->next == NULL) return 0;。
- 极易扣分点:写
- 数组越界与正负号越界:
- 辅助数组如果只开了
n个,而元素取值范围包含n,访问count[n]就会导致堆栈溢出,辅助数组务必开到n + 2。
- 辅助数组如果只开了
- 动态内存未
free:- 凡是在函数内部调用了
malloc()分配辅助空间的,在 return 之前务必写一行free(...),体现科班扎实的编码素养。
- 凡是在函数内部调用了
情况 A:替换 -> 的底层写法(你看书时可能会看到)
-
你想拿数据:
p->data就完全等价于(*p).data。 -
你想拿下一个地址:
p->next完全等价于(*p).next。
注意括号! 因为
.的优先级比*高,所以必须加括号写成(*p).data,如果不加*p.data就会报错。嫌麻烦,所以发明了->
四、 克服畏难心理与牢固记忆法(3 个高分应试记忆法)
1. 破除心魔:人工纸面阅卷不是 OJ 机试!
- OJ 机试逻辑:非最优解或未 AC 全部用例直接给 0 分(极易挫伤积极性产生畏难情绪)。
- 408 考研卷面逻辑:人工纸面分步踩分!助教按点给分:
- 算法思想写清楚了 拿 3~4 分;
- 代码逻辑跑通、语法规范 拿 5~6 分;
- 时空复杂度分析正确 拿 2~3 分。
- 结论:写出暴力解保底稳拿 10~11 分!考场上写出暴力解是绝对的赢家,唯有交白卷才是真正的炮灰。
2. “三词动作流”记忆法(记骨架动作,不背死代码)
- 数组题:开辅助数组 扫原表打标记 扫新表找答案。
- 链表就地逆置:存后继 掉头 双指针步进(
next=p->next,p->next=pre,pre=p,p=next)。 - 二叉树递归:判空返回 判叶子结算 左右递归累加。
3. 脱离电脑盲默 + 专注 18 套真题
- 草稿纸手写盲默:考场用黑水笔作答,平时每天花 10 分钟在 A4 废纸上盲默上面三个模板的代码骨架,连续默写 3 天即形成手指肌肉记忆。
- 彻底封印外部题库:不刷任何 LeetCode / 算法竞赛题,只刷 18 套真题的第 41 题,强制用最笨的暴力法写出完整三段论,快速建立稳拿 11 分的正反馈。