绪论

• 1: 数据结构基本概念
• 2: 算法基本概念
• 3: 算法设计题解题框架

1 - 数据结构基本概念

数据结构

数据结构（Data Structure）是 存储、组织和管理数据的方式，它不仅决定了数据的存储形式，也影响数据访问和操作的效率。

分类

mindmap
  root((数据结构<br/>Data Structure))
    线性结构
      数组 Array
        连续内存
        随机访问快
        插入删除慢
      链表 Linked List
        节点指针连接
        插入删除快
        访问慢
      栈 Stack
        后进先出 LIFO
        函数调用
        表达式求值
      队列 Queue
        先进先出 FIFO
        任务调度
      双端队列 Deque
        两端可操作
    树形结构
      二叉树<br/>Binary Tree
      二叉搜索树<br/>BST
      堆 Heap
        优先队列实现
      平衡树
        AVL树
        红黑树
    图结构
      有向图
      无向图
      存储方式
        邻接矩阵
        邻接表
      应用场景
        路径搜索
        社交网络建模
    散列表<br/>Hash Table
      哈希函数
      快速查找
      应用
        字典
        缓存

考试中涉及的数据结构可以分为以下几种：

1. 线性结构（元素之间有顺序关系）
   • 数组（Array）：连续内存，随机访问快，插入删除慢
   • 链表（Linked List）：节点通过指针连接，插入删除快，访问慢
   • 栈（Stack）：后进先出（LIFO），用于函数调用、表达式求值
   • 队列（Queue）：先进先出（FIFO），用于任务调度
   • 双端队列（Deque）：两端都可以操作
2. 树形结构（元素之间有层级关系）
   • 二叉树（Binary Tree）
   • 二叉搜索树（BST）
   • 堆（Heap）：优先队列实现
   • 平衡树（AVL、红黑树）
3. 图结构（元素之间有网络关系）
   • 有向图 / 无向图
   • 邻接矩阵 / 邻接表存储
   • 常用于路径搜索、社交网络建模
4. 散列表（Hash Table）
   • 通过哈希函数实现快速查找
   • 常用于字典、缓存

算法

算法（Algorithm）是 解决问题的一系列步骤或方法，用来操作数据结构，实现具体功能。

数据结构和算法的关系

• 数据结构提供“容器”
• 算法提供“操作方法”
• 好的数据结构可以让算法更高效
• 算法的设计也依赖数据结构特性

💡 举例：

• 用数组实现栈 → 可以快速访问栈顶
• 用链表实现队列 → 插入删除都很快
• 用堆实现优先队列 → 可以快速找最大/最小值
• 用图 + BFS → 可以找最短路径

2 - 算法基本概念

算法概念

算法 (Algorithm) 是一个明确规定了操作步骤的有限指令集，用于计算函数、处理数据、解决一个特定问题或执行某个任务。

算法 的基本属性：

1. 明确性：每一步骤必须有明确且不含糊的定义。
2. 有输入和输出：算法 应有 0 个或更多的 输入 和 1 个或更多的 输出。输入 是在 算法 开始之前提供的，而 输出 是在 算法 结束时产生的。
3. 有限性：如果 算法 在执行完有限步骤后终止，那么它就是 有限的。换句话说，一个 算法 必须总是在执行有限次操作后结束。
4. 可行性：算法 中的每一步都应该是简单且基本的，这样它们可以在有限的时间内完成并由计算机执行。
5. 独立性：算法 的指令应该有普适性，也就是说，它们不应依赖于任何特定的编程语言或模型。相反，算法 应该足够通用，可以在任何编程环境中实现。

复杂度分析

时间复杂度

时间复杂度（Time Complexity）是计算机科学中衡量一个 算法运行效率 的重要指标。它主要描述了当输入规模（通常记为 $n$ ）不断增大时，算法执行所需的 基本操作次数 的增长趋势。

在算法的时间复杂度分析中， 基本操作次数 指的是一个算法中执行时间固定的 最小操作单元。你可以把它理解为计算机执行一次最基础、最原始的指令所花费的时间。

这些基本操作通常包括：

• 算术运算：例如，加、减、乘、除、取模等。
• 比较运算：例如，小于、大于、等于等。
• 赋值操作：将一个值赋给一个变量。
• 逻辑运算：例如，与、或、非等。

计算方法

设输入规模为 $n$ ，算法执行所需的 基本操作次数 记为 $T(n)$ 。 为了衡量算法效率，我们关心 $T(n)$ 随 $n$ 增大的增长趋势，而不是精确的操作次数。

时间复杂度就是 $T(n)$ 的 渐近上界，常用 大 $O$ 符号 表示为：

其中 $f(n)$ 是能反映 $T(n)$ 增长速度的函数。 换句话说，时间复杂度刻画的是 当 $n$ 趋于无穷大时，算法执行时间随输入规模增长的量级。

常见时间复杂度

常见的 时间复杂度（按增长速度排序）有：

• $O(1)$ ：常数时间。无论 输入 数据有多大，算法 都在恒定的时间内完成。
• $O(\log n)$ ：对数时间。例如：二分搜索。
• $O(n)$ ：线性时间。例如：简单的搜索 算法。
• $O(n\log n)$ ：线性对数时间。例如：高效的排序 算法，如归并排序。
• $O(n^2)$ 、 $O(n^3)$ …：多项式时间。例如：冒泡排序、插入排序和选择排序是 $O(n^2)$ 。
• $O(2^n)$ ：指数时间。例如：计算斐波那契数列的递归实现。
• $O(n!)$ ：阶乘时间。例如：旅行商问题的暴力解决方法。

空间复杂度

空间复杂度（Space Complexity）是衡量 算法执行过程中所需存储空间 随输入数据量增长而变化的指标。它不仅包括算法中用来存放 输入数据 的空间，还包括 辅助变量、递归调用栈 等临时空间。与时间复杂度类似，我们关注的是 增长趋势，通常只关注最高阶的量级，用大 $O$ 符号表示。

组成

1. 固定部分
   • 包括常量、程序代码本身、简单变量、常量数组等。
   • 这一部分的空间大小与输入数据规模无关，通常记为 $O(1)$ 。
2. 可变部分
   • 随着输入数据量的变化而变化的空间，主要包括：
     • 输入数据本身（如数组、链表）
     • 辅助空间（如临时数组、栈、队列等）
     • 递归调用栈（递归深度对空间占用有直接影响）

常见空间复杂度

常见的 空间复杂度（按增长速度排序）有：

3 - 算法设计题解题框架

答题格式规范

算法设计题通常分三个子问：

1. 给出算法的基本设计思想（约 4 分）
2. 用 C/C++ 描述算法，关键处给注释（约 7~9 分）
3. 说明时间复杂度和空间复杂度（约 2 分）

💡 答题技巧：即使写不出完整代码，只要 设计思想正确 且 伪代码逻辑合理，通常可以拿到一半以上分数。

复杂度写法模板：

时间复杂度：O(n)    // 说明为何是此量级（扫描了几遍 / 循环嵌套层数）
空间复杂度：O(1)    // 仅使用常数个辅助变量

历年考题数据结构分布

规律总结：

• 41 题：近年偏向 图 和 顺序表/数组，偶发链表、二叉树。
• 42 题：近年偏向 图（生成树、拓扑、路径） 和 排序/查找，也有树题。
• 数组、链表、树、图 四类结构轮流出现，不会连续两年考同一类。

解题思路选择框架

拿到题目，先判断数据结构类型，再套对应套路：

输入是数组/顺序表？
  ├─ 有序数组 → 优先考虑双指针 / 二分查找
  ├─ 无序数组 → 排序兜底 / 桶标记 / 后缀预处理
  └─ 需要 O(n) 且不能用额外空间 → 原地标记 / 投票算法

输入是链表？
  ├─ 找中间 / 倒数 k → 快慢双指针
  ├─ 需要逆序访问 → 原地逆置后再处理
  └─ 共享结构 → 从尾部对齐，找公共结点

输入是二叉树？
  ├─ 遍历相关 → 中序（BST 有序性）/ 层序（BFS）
  └─ 路径/统计 → 递归 DFS，注意返回值设计

输入是图？
  ├─ 连通性 / 路径 → BFS / DFS
  ├─ 最短路径 → Dijkstra（不能用贪心的局部最优证明）
  ├─ 最小生成树 → Prim / Kruskal
  └─ 依赖关系 → 拓扑排序 / AOE 关键路径

数组题套路

兜底方案：排序法

对于数组类题目，如果想不到 O(n) 方法，先排序再处理 几乎总能把复杂度降到 O(n log n)，并且逻辑简单：

• 对有序数组，双指针夹逼效果极好
• 查找、去重、区间问题在有序状态下可以二分

// 模板：排序 + 双指针
qsort(a, n, sizeof(int), cmp);
int left = 0, right = n - 1;
while (left < right) {
    // 根据题意移动指针
    if (condition) left++;
    else right--;
}

⚠️ 排序会破坏原始顺序，如果题目要求 不改变顺序 则不能用此法。

桶标记（原地哈希）

适用：数组元素取值范围已知（如 0 ≤ a[i] < n），需要 O(n) 时间 O(1) 空间判断某值是否出现。

思路：将 a[i] 映射到下标，用符号（正负号）或额外标记位记录"出现"状态。

经典题：2018年41题——数组中未出现的最小正整数

int findMissMin(int a[], int n) {
    // 第一遍：把 [1,n] 范围外的元素置 0（不关心）
    for (int i = 0; i < n; i++)
        if (a[i] <= 0 || a[i] > n) a[i] = 0;
    // 第二遍：用下标 a[i]-1 处的符号标记 a[i] 出现过
    for (int i = 0; i < n; i++) {
        int v = abs(a[i]);
        if (v >= 1 && v <= n && a[v-1] > 0)
            a[v-1] = -a[v-1];
        // v==0 说明原来就是"不关心"值，跳过
    }
    // 第三遍：第一个正数位置就是答案
    for (int i = 0; i < n; i++)
        if (a[i] > 0) return i + 1;
    return n + 1;
}

后缀/前缀预处理

适用：需要对每个元素计算"它右边/左边的最值/乘积"，一次预处理可把 O(n²) 降到 O(n)。

经典题：2025年41题——子数组乘积最大值

void calMulMax(int A[], int res[], int n) {
    int maxVal = INT_MIN, minVal = INT_MAX;
    // 从右向左维护后缀最大值和最小值
    for (int i = n - 1; i >= 0; i--) {
        if (A[i] > maxVal) maxVal = A[i];
        if (A[i] < minVal) minVal = A[i];
        // 正数乘以最大值，负数乘以最小值
        res[i] = (A[i] >= 0) ? A[i] * maxVal : A[i] * minVal;
    }
}

投票算法

适用：在 O(n) 时间、O(1) 空间内找出 出现次数超过半数 的"主元素"。

经典题：2013年41题——主元素

int majority(int a[], int n) {
    int num = a[0], cnt = 1;
    // 第一遍：筛选候选元素（对消法）
    for (int i = 1; i < n; i++) {
        if (a[i] == num) cnt++;
        else if (--cnt == 0) { num = a[i]; cnt = 1; }
    }
    // 第二遍：验证候选元素是否真的超过半数
    int m = 0;
    for (int i = 0; i < n; i++) if (a[i] == num) m++;
    return (m > n / 2) ? num : -1;
}

多指针夹逼

适用：多个有序数组/集合，需要找最优组合（最小距离、最小差值等）。

经典题：2020年41题——三元组最小距离

// 三指针分别指向三个升序数组头部
// 每次移动三者中最小值对应的指针
// 因为移动最大值只会让距离更大
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2 && k < n3) {
    int D = calc_D(S1[i], S2[j], S3[k]);
    ans = min(ans, D);
    int minVal = min(S1[i], min(S2[j], S3[k]));
    if (S1[i] == minVal) i++;
    else if (S2[j] == minVal) j++;
    else k++;
}

链表题套路

快慢双指针

用途：找中间结点、倒数第 k 个结点。

// 找中间结点（慢指针到中间时快指针到末尾）
NODE *slow = head->next, *fast = head->next;
while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
}
// slow 此时指向中间结点

// 找倒数第 k 个（快指针先走 k 步）
NODE *p = head->next, *q = head->next;
for (int i = 0; i < k; i++) {
    if (p == NULL) return 0;  // k 超出链表长度
    p = p->next;
}
while (p != NULL) { p = p->next; q = q->next; }
// q 即为倒数第 k 个结点

原地逆置

用途：链表后半段逆置后可从两端同步处理，避免 O(n) 的随机访问。

// 将 start 及之后的链表原地逆置，返回新头
NODE *reverse(NODE *start) {
    NODE *prev = NULL, *cur = start;
    while (cur != NULL) {
        NODE *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;  // 新头
}

经典组合：快慢指针找中点 + 逆置后半段 + 双指针归并（2019年41题）

找公共结点（Y 形链表）

两链表分别从头走到尾再换头，相遇点即公共结点（路径等长）。

NODE *p = headA, *q = headB;
while (p != q) {
    p = (p != NULL) ? p->next : headB;
    q = (q != NULL) ? q->next : headA;
}
return p;  // NULL（无公共结点）或公共结点

二叉树题套路

递归三要素

写递归前先明确：

1. 函数语义：这个函数返回/做什么？
2. 递归终止条件：root == NULL 时返回什么？
3. 递归关系：如何用子问题的结果合并得到当前问题的答案？

中序遍历利用 BST 有序性

BST 的中序遍历是递增序列，可用于：

• 找第 k 小元素
• 找与目标值差最小的结点（2026年41题）
• 判断是否为合法 BST

// 中序遍历框架
void inorder(BTNode *root) {
    if (!root) return;
    inorder(root->left);
    visit(root);       // 处理当前结点
    inorder(root->right);
}

层序遍历（BFS）

适用：按层处理、顺序存储二叉树的恢复（2022年41题）。

// 用队列实现层序遍历
Queue Q; enqueue(Q, root);
while (!isEmpty(Q)) {
    BTNode *node = dequeue(Q);
    visit(node);
    if (node->left)  enqueue(Q, node->left);
    if (node->right) enqueue(Q, node->right);
}

图题套路

DFS / BFS 框架

// DFS（邻接矩阵）
int visited[MAXV] = {0};
void DFS(MGraph G, int v) {
    visited[v] = 1;
    visit(v);
    for (int w = 0; w < G.numVertices; w++)
        if (G.Edge[v][w] && !visited[w])
            DFS(G, w);
}

// BFS（邻接矩阵）
void BFS(MGraph G, int v) {
    int visited[MAXV] = {0};
    Queue Q; enqueue(Q, v); visited[v] = 1;
    while (!isEmpty(Q)) {
        int u = dequeue(Q); visit(u);
        for (int w = 0; w < G.numVertices; w++)
            if (G.Edge[u][w] && !visited[w]) {
                visited[w] = 1; enqueue(Q, w);
            }
    }
}

拓扑排序

适用：判断有向图是否有环、给出工程先后顺序（2024年41题）。

// 基于入度数组的拓扑排序
int indegree[MAXV] = {0};
// 初始化入度...
Queue Q;
for (int v = 0; v < n; v++)
    if (indegree[v] == 0) enqueue(Q, v);
int count = 0;
while (!isEmpty(Q)) {
    int u = dequeue(Q); count++;
    for each neighbor w of u:
        if (--indegree[w] == 0) enqueue(Q, w);
}
return (count == n);  // true 说明无环

度的统计

适用：欧拉路径/回路判断（2021年41题）。

// 邻接矩阵中，第 v 行非零元素个数即为 v 的度
int degree(MGraph G, int v) {
    int d = 0;
    for (int w = 0; w < G.numVertices; w++)
        d += (G.Edge[v][w] != 0);
    return d;
}

常见暴力法及其优化方向

💡 评分规则惯例：O(n) 空间换 O(n) 时间通常比 O(n²) 多得 1~2 分；O(1) 空间的最优解满分。

答题语言规范

设计思想描述模板（以数组题为例）：

算法分两步： ① 先对数组进行一次预处理（说明做了什么），时间复杂度 O(…)； ② 再用双指针/桶标记/…（说明核心操作），时间复杂度 O(…)。 整体时间复杂度 O(…)，空间复杂度 O(…)。

代码注释要点：

// 关键变量含义要注释，e.g.
int cnt = 1;   // 候选主元素的"计数器"，cnt>0 时 num 为候选

// 循环不变量要注释，e.g.
// 循环结束后，a[0..i-1] 中所有正整数已被标记

// 非显然的下标计算要注释，e.g.
a[v-1] = -a[v-1];  // 用 v-1 位置的符号记录"v 出现过"