算法设计题指南

从题目约束选择算法，用数组、链表、树和图的典型套路完成思想、代码与复杂度分析

# 算法设计题怎么做

读懂约束 → 选择思路 → 写出实现 → 检查边界

配套讲义：[算法设计题解题框架](/data_structure/basic/alg_design/)

---

## 算法题练什么

- 看到数据结构，能调出基本操作
- 看到约束，能筛掉不适用的方法
- 解释为什么这样做不会漏解
- 把思路变成有边界、有终止条件的代码

> 记住模板后，还要知道模板依赖什么条件。

---

## 答案通常包含三部分

1. **基本思想**：维护什么信息，按什么顺序处理
2. **算法实现**：按题目要求用 C/C++ 描述，关键处加注释
3. **复杂度**：时间、辅助空间及其依据

具体小问和分值以题目为准。

不会最优解时，先留下满足题意的可行方案，再尝试优化。

---

## 动笔之前，先圈出约束

| 检查项 | 影响什么 |
| --- | --- |
| 有序吗？值域有限吗？ | 二分、双指针、桶标记能否使用 |
| 能修改输入吗？ | 排序、原地标记、链表逆置是否允许 |
| 有头结点吗？长度已知吗？ | 指针初值、循环和空表判断 |
| 要求什么复杂度？ | 是否允许排序或辅助数组 |
| 输出什么？ | 返回值、原地修改、输出序列 |

---

## 先写可行解，再找重复工作

```text
枚举所有候选 → 找出反复计算的信息
→ 用有序性、辅助记录或状态维护消除重复
```

- 每次重新查“出现过吗” → 标记表
- 每次重新扫描右侧最值 → 后缀预处理
- 每次从链表头找位置 → 双指针同步移动

优化之后，要重新核对空间和输入修改限制。

---

## 用结构缩小思路范围

| 输入结构 | 优先考虑 |
| --- | --- |
| 数组 / 顺序表 | 排序、二分、双指针、标记、前后缀 |
| 链表 | 固定间距、快慢指针、逆置、长度对齐 |
| 二叉树 | DFS 递归、中序有序性、层序遍历 |
| 图 | 遍历、度统计、拓扑、路径与生成树 |

历年题用于积累模型；不要据此排除某类结构。

---

## 数组：排序能解决什么

把无序关系变成相邻关系或单调关系：

- 去重：比较相邻元素
- 两数配对：排序后尝试首尾双指针
- 第 k 小：排序后取下标，也可考虑选择算法

通常排序需要 O(n log n) 时间，空间取决于排序实现。

> 若需要保留原顺序、连续区间或原下标关系，先判断排序是否破坏题意。

---

## 数组：用空间记录“出现过”

[2018 年第 41 题](/study_methods/408quiz/2018/#41)：找未出现的最小正整数。

长度为 n 的数组，答案一定在 **[1, n+1]** 中。

1. 只记录 1 到 n 是否出现
2. 从 1 开始找第一个未出现的数
3. 若都出现，返回 n+1

不需要按数组中的最大值分配空间。

---

## 桶标记：先写可靠版本

```cpp
int findMissMin(const int a[], int n) {
    bool *seen = new bool[n + 1]();
    for (int i = 0; i < n; ++i)
        if (a[i] >= 1 && a[i] <= n)
            seen[a[i]] = true;
    int ans = 1;
    while (ans <= n && seen[ans]) ++ans;
    delete[] seen;
    return ans;
}
```

时间 O(n)，辅助空间 O(n)，不修改输入。

Note: 如果进一步练习 O(1) 辅助空间版本，可用原地置换：把值 v 放到 a[v-1]，交换前判断值域和目标位置是否已有 v，避免重复值造成死循环。符号标记时，0 不能通过取负数标记；不能直接把越界元素置 0 后照搬符号标记模板。

---

## 数组：前后缀预处理

如果每个位置都要重新扫描右侧，常会产生 O(n²) 时间。

例如求每个位置 **严格右侧** 的最大值：

```text
R[n-1] = 无右侧元素
R[i] = max(A[i+1], R[i+1])
```

从右向左扫描，把已经算过的信息传给下一个位置。

关键：先明确范围是 `[i,n-1]` 还是 `[i+1,n-1]`。

---

## 乘积问题：最大值还不够

固定一个数 x，若要在候选集合中选 y，使 x·y 最大：

- x > 0：选最大的 y
- x < 0：选最小的 y
- x = 0：乘积为 0

因此可能需要同时维护后缀最大值和最小值。

> 先确认候选下标范围、是否允许重复选同一位置，以及乘积是否溢出。

---

## 数组：投票算法分两遍

[2013 年第 41 题](/study_methods/408quiz/2013/#41)：找出现次数超过 n/2 的主元素。

```cpp
int candidate = 0, count = 0;
for (int i = 0; i < n; ++i) {
    if (count == 0) candidate = a[i];
    count += (a[i] == candidate) ? 1 : -1;
}
int occurrences = 0;
for (int i = 0; i < n; ++i)
    if (a[i] == candidate) ++occurrences;
// occurrences > n/2 时，candidate 才是主元素
```

异值对消保留候选；第二遍验证是否真的过半。

---

## 数组：多指针为什么移动最小值

[2020 年第 41 题](/study_methods/408quiz/2020/#41)：三个有序数组的三元组最小距离。

```text
D = |a-b| + |b-c| + |c-a|
  = 2 × (最大值 - 最小值)
```

- 固定当前最小值，增大其他值不能缩小极差
- 因此记录当前答案后，移动一个最小值对应的指针
- 任一数组耗尽即结束

每个指针只向前走，时间 O(n₁+n₂+n₃)，辅助空间 O(1)。

---

## 链表：让两个指针保持距离

找倒数第 k 个结点，假设 head 是头结点、k ≥ 1：

```c
NODE *p = head->next, *q = head->next;
for (int i = 0; i < k; ++i) {
    if (p == NULL) return NULL;
    p = p->next;
}
while (p != NULL) {
    p = p->next;
    q = q->next;
}
return q;
```

p 先走 k 步，再同步移动；时间 O(n)，辅助空间 O(1)。

---

## 链表：逆置时先保存后继

```c
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;
}
```

循环中：prev 是已逆置部分，cur 是未处理部分的起点。

> 修改 cur->next 之前，必须保存原后继。

---

## 链表：把一道题拆成三步

[2019 年第 41 题](/study_methods/408quiz/2019/#41)：重排为首、尾、次首、次尾……

```text
1 → 2 → 3 → 4 → 5
拆分：1 → 2 → 3    4 → 5
逆置：1 → 2 → 3    5 → 4
交替：1 → 5 → 2 → 4 → 3
```

找中点 → 断开两段 → 逆置后半段 → 交替合并。

检查奇偶长度、保存后继、尾结点是否指向 NULL。

---

## 链表：公共结点比较的是地址

对两个无环单链表，从各自第一个数据结点出发：

```c
NODE *p = firstA, *q = firstB;
while (p != q) {
    p = p ? p->next : firstB;
    q = q ? q->next : firstA;
}
return p;
```

换头抵消独有前缀的长度差；无交点时同到 NULL。

**值相等不代表共享结点。** 时间 O(m+n)，辅助空间 O(1)。

---

## 二叉树：先定义递归函数的语义

例如求树高，约定空树高度为 0：

```c
int height(BTNode *root) {
    if (root == NULL) return 0;
    int left = height(root->left);
    int right = height(root->right);
    return 1 + (left > right ? left : right);
}
```

函数做什么 → 空树返回什么 → 如何合并子树结果。

时间 O(n)，递归栈 O(h)；退化成链时 h 可达 n。

---

## 二叉树：根据问题选择遍历顺序

| 要求 | 可用思路 |
| --- | --- |
| 利用 BST 的有序性 | 中序遍历；重复键规则以题目定义为准 |
| 按层统计 / 输出 | 队列实现 BFS |
| 当前结点依赖子树结果 | 后序递归 |
| 路径、深度相关统计 | DFS 传递深度或路径状态 |

BFS 先判断根是否为空；辅助空间与最大层宽有关。

---

## 图：先看存储，再选算法

- 连通性 / 可达性：DFS、BFS
- 无权图最短路径：BFS
- 非负权图单源最短路径：Dijkstra
- 最小生成树：Prim、Kruskal
- 有向依赖关系：拓扑排序；AOE 网再分析关键路径

遍历整个非连通图时，要从所有未访问顶点继续启动。

---

## 图：同样遍历，复杂度可能不同

设顶点数为 V，边数为 E：

| 存储方式 | DFS / BFS 遍历整个图 |
| --- | --- |
| 邻接矩阵 | O(V²)：每个顶点扫描一整行 |
| 邻接表 | O(V+E)：扫描顶点及其邻接边 |

BFS 在 **入队时** 标记已访问，避免重复入队。

辅助空间通常为 O(V)，包括访问标记与栈 / 队列。

---

## 拓扑排序：维护“当前入度”

1. 统计每个顶点入度，将入度为 0 的顶点入队
2. 出队一个顶点，输出并累计数量
3. 删除其出边，将新变为 0 入度的邻接点入队
4. 处理数量等于 V，才说明图中无环

这里的入度是 **尚未删除的子图中的入度**。

邻接表实现时间 O(V+E)，邻接矩阵实现通常为 O(V²)。

---

## 复杂度要和代码对得上

- 多个顺序扫描相加：O(n)+O(n)=O(n)
- 嵌套循环要看总移动次数：双指针未必是 O(n²)
- 递归要算调用栈：树遍历并非默认 O(1) 空间
- 标明是否把输出空间计入，辅助数组不能漏算

例如：“三个指针各自只前进，不回退，因此总时间为 O(n₁+n₂+n₃)。”

---

## 思想说明：写出操作与理由

以倒数第 k 个结点为例：

> 设置 p、q 指向第一个数据结点，先让 p 前进 k 步；若不足 k 步则失败。随后两指针同步前进，保持 k 步间距。当 p 到达 NULL 时，q 即为倒数第 k 个结点。只遍历链表，时间 O(n)，仅使用常数个指针，辅助空间 O(1)。

不要只写“使用双指针法”，要交代初值、移动规则和结束条件。

---

## 交卷前，用小例子检查

- 空输入、单元素：是否越界或解引用 NULL？
- 全相等、重复值：是否死循环或漏掉验证？
- 全负数、含 0：最值初值和乘法规则是否正确？
- 奇偶长度、k=1、k 超长：指针位置是否正确？
- 非连通图、有向环、退化树：是否覆盖题目允许的情况？

例子帮助发现错误；正确性还要解释为什么覆盖所有合法输入。

---

## 平时怎么练

1. 独立写出可行思路，再对照参考解法
2. 记录卡在约束、思路、实现还是复杂度
3. 合上答案，重写核心代码并手推边界
4. 换一个限制：不能改数组？不能用额外空间？

讲义与模板：[算法设计题解题框架](/data_structure/basic/alg_design/)

书写配套：[408 大题书写规范](/study_methods/talk/answer_writing/)