题解编写指南 —— 综述

zerotrac 🌸

5829

2020.05.05

2021.08.27

发布于未知归属地

C++学习分享

迈出第一步

在说明「如何编写一份高质量的力扣题解」之前，我们先来想一想，一篇题解应该包含哪些部分：

前言：题解的一些相关背景；
方法一、方法二、方法三等：不同的解题方法。每一种方法会包括：
- 思路及算法：对如何解决问题进行详细地阐述；
- 代码：给出相关的代码；
- 时空复杂度分析：对算法的复杂度进行分析。
结语：作者的一些思考，与本题类似的一些题目等。

大部分高质量的题解都是按照这个流程编写的。

格式要求

大标题

前面提到的「前言」「方法一」「方法二」「结语」都属于大标题。我们使用四级标题 #### 表示大标题。

对于「前言」和「结语」这两个大标题，可以使用其它的表述方法，例如「说明」「写在前面」「总结」「写在最后」等等；
对于「方法一」这一类大标题，最好不要使用其它的表述方法。一般来说，我们会使用「方法一：xxxx」作为大标题，其中的 xxxx 就是作者需要讲解的方法。
- 例子：「方法一：深度优先搜索」

前言

如果没有想说的前言，这一部分可以不写。

方法 x

如果有多个方法，建议从易到难、循序渐进地介绍：
- 例子：「方法一：排序 + 遍历」「方法二：哈希表」
不建议把会超时的方法单独作为一个「方法 x」。如果该方法是题解中不可或缺的一部分（例如推导出正确方法过程中的一步），可以考虑将超时的方法浓缩成一段话，或者作为一个小标题（下文中会介绍小标题）写进正确的方法中：
- 例子：我们可以用递归 + 回溯的方法，搜索出所有可能的路径，并找出最优的答案。然而这样会超出时间限制。考虑到这种方法的瓶颈在于大量的重复搜索，我们可以 ...，这样就能用动态规划的方法解决本题了。

结语

如果没有想说的结语，这一部分可以不写。

小标题

前面提到的「思路及算法」「代码」「时空复杂度分析」都属于小标题。我们使用加粗环境 ** ** 表示小标题。

对于「思路及算法」这个小标题，如果作者希望在其与「方法 x」的大标题之前再增加一个小标题，例如对「方法 x」特定的「预备知识」等等，那么「思路及算法」必须被保留，作用是与「预备知识」在内容上进行区分；如果这两者之间没有其它的小标题，那么「思路及算法」可以省去不写，因为在「方法 x」下面直接开始写这一部分也是很合理的。同样的道理，如果这两者之间有「预备知识」，那么「预备知识」这个小标题也是可以省去的；
对于「代码」这个小标题，由于力扣有专门的代码环境，因此「代码」也可以省去不写；
对于「时空复杂度分析」这个小标题，一般的习惯是写成「复杂度分析」，并且需要保留，具体的原因在讲解「时空复杂度分析」这一部分的章节会进行阐述。
此外，作者可以自行添加一些额外的小标题，常见的例如「细节」「优化」等等，用来对题解的段落进行区分，使得题解更加流畅。（20210827 修改）

预备知识

预备知识部分一般用来对「思路及算法」部分中的一些不常用的技巧进行简单的介绍：

如果使用的是不常用的数据结构，可以介绍一下我们会用到哪些操作和 API：
- 例子：「树状数组」，我们会用到它的「区间查询」和「单点修改」这两个操作。
如果使用的是不常用的算法，可以介绍一下这种算法的具体作用：
- 例子：「Rabin-Karp 字符串加密算法」，它是将字符串看成一个 $k$ 进制的数，其对应的十进制表示就是加密的结果。
如果使用的是不常用的技巧，可以介绍一下这些技巧以及对应的伪代码：
- 例子：「位运算」，我们可以使用 $x & (1 << i)$ 判断 $x$ 二进制表示的第 $i$ 位是否为 $1$ 。

考虑到这是「题解」而不是「算法小百科」，我们并不需要花长篇幅来对使用的技巧进行详细的讲解，点到为止即可。我们期望读者不要「超前」地去做自己能力范围之外的题，可以通过网上的其它「百科」性质的资料先进行学习，再通过「预备知识」以及后面的部分来验证自己是否学习完成。

思路及算法

这是题解中最重要的一部分。不同的作者对于这一部分都有自己习惯的处理方式，因此这里不对这部分做详细的规范，只给一些建设性的建议：

避免「保姆式」的算法讲解。在「思路及算法部分」，作者应当更多地讲解抽象的概念，而不是将代码翻译成自然语言：
- 正确的例子：最后一步我们可以用二分查找来解决。二分的上下界分别为 ... 和 ...。在二分查找的每一步中，如果满足 ...，我们就修改上界，否则修改下界。当二分查找完成后，我们可以得到最小的满足 ... 要求的整数，这样就可以得到最终的答案了；（20210827 修改）
- 错误的例子：最后一步我们可以用二分查找来解决。
  - 二分查找的上界为 ...，下界为 ...；
  - 在二分查找的每一步中，我们用 $mid = (left + right) /2$ ` 得到待查找的整数，并与 ... 进行比较。如果 ... 就将 $left$ 置为 ...，否则就将 $right$ 置为 ...；
  - 当 ... 时，我们结束二分查找，最终答案存储在变量 ... 中。
用图解的形式对讲解进行补充。相较于概念性的文字而言，读者更愿意接受形象化的图解。图解一般有三种类型：
- MarkDown 中的 ``` ``` 「代码块」环境，图解以「字符画」的形式，出现在代码框中；
- 图片环境，图解以单张图片的形式，出现在文字段落中；
- 幻灯片环境，这是力扣编辑器支持的一种环境，图解以多张图片的形式，被放在幻灯片环境中进行播放。
行文保持一致。如果在前文进行了定义，那么后文相同的定义需要保持一致，并且所有在题目描述中未出现，但在这部分出现了的定义都需要进行解释：
- 正确的例子：我们用 $lchild$ 和 $rchild$ 表示该节点的左孩子和右孩子；
- 错误的例子：我们用 $lchild$ 和 $rchild$ 表示该节点的左孩子和右儿子；
- 正确的例子：我们用 $f (x_{i}) = f (x_{i - 1}) + C (∣ x_{i} - x_{i - 1} ∣)$ 来进行递推，其中 $C (∣ x_{i} - x_{i - 1} ∣)$ 表示函数 ...，这样就能得到最终的答案；
- 错误的例子：我们用 $f (x_{i}) = f (x_{i - 1}) + C (∣ x_{i} - x_{i - 1} ∣)$ 来进行递推，这样就能得到最终的答案。

代码

代码需要有基本的代码规范，遵守代码规范可以使得代码更加易读。题解中的代码一般只有十几到几十行，虽然不需要像工程代码那样完全遵守规范，但也需要有基本的准则，建议做到下面的两条：

一行只做一件事情：
- 正确的例子：
  C++
  auto result = get(); if (result > threshold) { ... }
- 错误正确的例子（20210827 修改，由于 $Python 3.7$ 之后增加了海象运算符， $C++17$ 也支持类似的写法，因此这样写在一行也是合理的，无需拆成两行）：
```
if (auto result = get(); result > threshold) {
    ...
}
```
- 错误的例子：
```
arr[++pos] = x++;
```
- 正确的例子（ $arr[++pos] = x$ 这种通俗易懂的语句，可以考虑写在一行）：
```
arr[++pos] = x;
++x;
```
加上括号：
- 正确的例子：
  C++
  for (int i = 0; i < n; ++i) { result += get(i); }
- 错误的例子：
```
for (int i = 0; i < n; ++i)
    result += get(i);
```
对于 Python 这类没有大括号的语言则可以不加。
- 正确的例子：
  C++
  if (cond_a || (cond_b && cond_c)) { ... }
- 错误的例子：
```
if (cond_a || cond_b && cond_c) {
    ...
}
```
不同语言的运算符优先级是不相同的，尤其是逻辑运算的部分。为了使得学习不同语言的读者都能看懂代码，应当适当地添加括号，突出运算顺序。

这些准则保证了代码的易读性且无歧义。

如果作者想要提供多种语言的代码，则需要使用力扣编辑器的「混合代码块」环境。同时需要注意，由于 Python2 已经停止维护，不要提供 Python2 的代码。

时空复杂度分析

复杂度分析也是题解中不可或缺的一部分。这部分的作用是：解释方法可以在规定的时间和空间的限制内通过的原因。

由于复杂度分析一般会拆分成「时间复杂度」和「空间复杂度」，因此会使用「无序列表」环境分别进行阐述，因此需要加上「复杂度分析」这一小标题，否则在「代码」部分之后直接接上「无序列表」的环境显得不美观。

对于这两个部分：

使用「大 O 表示法」，并且需要对复杂度进行简单的解释；
如果复杂度中出现字母，并且在题目描述中没有对应（以字母的形式），则需要进行说明。常见的有数组的长度、数组中元素的最大值等；
如果复杂度中出现了非系数的常数，并且会随着题目要求变化，则不能省略，一般用 $C$ 表示，并且要说明 $C$ 的含义以及本题中 $C$ 的值：
- 例子：对 $N$ 个在 $[1, 10000]$ 内的整数进行计数排序，时间复杂度为 $O (N + C)$ ，其中 $C$ 表示待排序整数的范围，在本题中 $C = 10000$ ；
- 例子：在 32 位二进制数的范围内进行二分查找，每次查找的时间复杂度为 $O (N)$ ，那么总时间复杂度为 $O (N lo g C)$ ，其中 $C$ 表示二分查找的范围，在本题中 $C = 2^{32}$ 。

对于「时间复杂度」部分：

除了有约定俗成的表示（例如快速排序的最坏时间复杂度为 $O (N^{2})$ ，但我们一般说的是平均时间复杂度 $O (N lo g N)$ ），其余情况需要给出算法在「最坏情况下」的时间复杂度。一些暴力的算法在「平均情况下」拥有和正确算法媲美的时间复杂度，但在「最坏情况下」则会超出时间限制。（20210827 修改）

对于「空间复杂度」部分：

我们只计算除了函数返回值（也就是答案）以外的「额外空间复杂度」。也就是说，如果题目中需要返回一个数组，在代码中申请了一个（用来返回的）数组的空间和若干个临时变量，那么空间复杂度记为 $O (1)$ ；
如果重复使用同一个数组，使用的空间只记录一次。也就是说，如果我们使用「滚动数组」优化动态规划，将原本的二维数组减少至两个一维数组，那么虽然我们的计算量不变，但空间复杂度只记为 $O (N)$ ，其中 $N$ 是数组的长度；
栈空间经常容易被忽略，但也必须计入空间复杂度：
- 例子：使用语言自带的排序，空间复杂度一般是 $O (lo g N)$ ，其中 $N$ 是待排序的元素个数。

环境要求

变量环境

在编写题解的过程中，我们一般会用到三种环境（20210827 修改）：

行内代码环境，即 $result = x + y + 233$ ；
行内公式环境，即 $result = x + y + 233$ 或 $False$ ；
整行公式环境，即
$result = x + y + 233$

一般来说，对于比较长的公式（例如状态转移方程）我们用「整行公式环境」；对于「大 O 表示法」「变量」「函数」「数值型常数」，我们用「行内公式环境」中的斜体（\textit），如果只有一个字母，可以无需使用 \textit；对于「字符型常数」，我们用「行内公式环境」中的正体（\text）；对于「代码」，我们用行内代码环境（\texttt）。

正确的例子：对于数组中的任意一个元素 $x$ ，我们用
$result = result + f (result, x^{3})$
来更新答案 $result$ ，其中 $f (a, b)$ 表示 $a$ 和 $b$ 的相关程度。
错误的例子：对于数组中的任意一个元素 x，我们用
$res u lt = res u lt + f (res u lt, x^{3})$
来更新答案 $res u lt$ ，其中 $f (a, b)$ 表示 $a$ 和 $b$ 的相关程度。

错误原因：（1） $x$ 没有使用行内公式环境（2） $result$ 没有使用 \textit。

常用技巧

很多的数学符号都是有对应的 $L A T E X$ 表示的：
- 正确的例子： $max min lo g ln$ 对应 \max, \min, \log, \ln；
- 错误的例子： $ma x min l o g l n$ 。
如果变量较长，可以使用 \textit 环境使其变得紧凑。
- 正确的例子： $result = xx + yy$ 对应 \textit{result}；
- 错误的例子： $res u lt = xx + yy$ 。

小例子

读者可以发现，本篇「综述」就是按照题解的格式要求编写的，但缺少了例如「代码」等内容部分。下面以最经典的 Hello World! 为例，给出一个题解的范例。

说明

Hello World! 是程序员在学习一门新语言时会尝试编写的第一段代码，可以算得上是经典中的经典。在这篇题解中，我们将会学习到两种不同的让程序输出 Hello World! 的方法。

方法一：直接输出

大部分语言都直接提供了输出字符串常量的 API，因此我们可以直接调用 API 输出 Hello World!。

C++

Python3

void hello() {
    puts("Hello World!");
}

复杂度分析

时间复杂度： $O (1)$ ，这里我们将字符串 Hello World! 的长度看作是常数。
空间复杂度： $O (1)$ 。

方法二：格式化输出

我们也可以将 Hello 和 World 分别保存在临时变量中，随后调用格式化输出字符串的 API 得到结果。

Python3

void hello() {
    char* hello = "Hello";
    char* world = "World";
    printf("%s %s!\n", hello, world);
}

复杂度分析

时间复杂度： $O (1)$ ，这里我们将字符串 Hello 和 World 的长度均看作是常数。
空间复杂度： $O (1)$ 。

总结

你学会了吗？