408 算法大题保底 11 分抢分模板(全科通用应试版)

IMPORTANT

408 算法大题(第 41 题,15分)核心应试铁律:

  1. 严禁交白卷! 408 采用分步踩分制:设计思想(34分)+ C/C++代码实现(78分)+ 时空复杂度分析(2~3分)。
  2. 想不到最优解,直接写暴力解/辅助数组解! 阅卷老师只会扣除 2~3 分算法最优分,逻辑跑通即可保底稳拿 10~11 分!
  3. 书写严格“三段式”:严禁把思想混在代码里,段落分明是阅卷老师送分的关键。

零、 语法扫盲:考场上必须搞懂的 C 语言“底层与套路”

很多同学背不下代码,是因为不知道代码里这些符号是**“固定公式”还是“灵活变量”**。这里先讲透两个最致命的语法点:

1. int *count = (int *)malloc(sizeof(int) * (n + 2)); 彻底拆解

  • 为什么要加 *(int *count)?
    • 在 C 语言里,普通变量 int a 只能存一个整数(比如 5)。
    • 而我们需要动态申请一整串连续的数组空间,系统在内存里分好空间后,只会把**这块空间首地址(门牌号)**交给你。
    • count 是一个指针变量,加 * 就是告诉编译器:“count 存的是这串空间的基地址,它不是普通数字,而是一个指向连续内存首地址的指针,后面你可以像用普通数组一样用 count[i]!”
  • 这是固定写法吗?需不需要死记?
    • 结论:这前半部分和中间是 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
首元节点0x200a0x300第一个真正存放数据的节点
第二个节点0x300bNULL最后一个节点,指针为空
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
  • 这两者的物理本质完全一样:都是指向节点地址的指针!
  • 但是,在 408 考场上有严格的“潜规则角色分工”,死记这一句:
    • 代表整条链表时,用 LinkList:比如函数参数 findKthFromEnd(LinkList L, int k),这里的 LinkList L 和 int k 100% 是题目题干直接给出的函数签名,你考场上直接抄题目给的这一行就行!
    • 代表跑腿移动的工作指针时,用 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 空指针)停下来!
  • 结论: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 开始算的。(首元节点是第 1 个,不是第 0 个)。
  2. 数组的下标:是从 0 开始的(a[0] 是第 1 个元素)。
  3. 循环变量(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);
}
  • 卷面复杂度踩分点:
    • 时间复杂度:(树中每一个节点仅访问一次)。
    • 空间复杂度:(递归工作栈深度取决于树高 ,最坏情况下单支树为 ,平衡时为 )。

三、 命题人常见扣分陷阱(避坑指南)

  1. 指针解引用前未判空:
    • 极易扣分点:写 p->next 之前没有检查 p != NULL。单链表题目开头永远加上:if (L == NULL || L->next == NULL) return 0;。
  2. 数组越界与正负号越界:
    • 辅助数组如果只开了 n 个,而元素取值范围包含 n,访问 count[n] 就会导致堆栈溢出,辅助数组务必开到 n + 2。
  3. 动态内存未 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 分的正反馈。

关联索引