38.外观数列
38. 外观数列
鲁迅曾说，我以前很讨厌刷题，但在二哥这里我找到了刷题的快乐，他写的每一
个题解我都能轻松掌握，这可太棒了。
题意
「外观数列」是一个数位字符串序列，由递归公式定义：
• countAndSay(1) = “1”
• countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。
行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复
两次或更多次）替换为字符重复次数（运行长度）和字符的串联。
例如，要压缩字符串 “3322251” ，我们将 “33” 用 “23” 替换，将 “222” 用 “32” 替换，将
“5” 用 “15” 替换并将 “1” 用 “11” 替换。因此压缩后字符串变为 “23321511”。
给定一个整数 n ，返回外观数列的第 n 项。
难度
中等
示例 1
• 输入：n = 4
• 输出：“1211”
解释：
• countAndSay(1) = “1”
• countAndSay(2) = “1” 的行程长度编码 = “11”
• countAndSay(3) = “11” 的行程长度编码 = “21”
• countAndSay(4) = “21” 的行程长度编码 = “1211”
示例 2
• 输入：n = 1
• 输出：“1”
解释：这是基本情况。
分析
首先，我们需要理解题目的意思。尤其是这个「外观数列」是什么鬼？
说实话题目上信息这么多，我就看懂了“例如”那一段：2222，那么就是 4 个 2， 可以压缩
为 42。
好，我们来给【外观数列】下一个定义：
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
好像还是不太懂。什么是对前一项的描述？
不着急，我们先用一个例子来带入一下：
比如数列 113334422，我们可以描述成 两个一 三个三 两个四 两个二，然后再把这个描
述转化成数字——21332422。
这是「外观数列」，能理解吧。
理解什么是【外观数列】后，我们需要再搞清楚题目中的 n 是什么意思？“序列中的每一
项都是对前一项的描述”又是什么意思？
好，说句废话，n 是指第 n 项，那第一项是什么呢？
第一项是 1，因为题目中给出了 countAndSay(1) = "1"。
那么第二项呢？
第二项是对第一项的描述，也就是 1 的描述，那么 1 的描述是什么呢？
1 的描述是 1 个 1，所以第二项是 11。
第三项呢？第四项呢？第五项呢？
1. 1
2. 11 （一个 1）
3. 21 （两个 1）
4. 1211 （一个 2，一个 1）
5. 111221 （一个 1，一个 2，两个 1）
是不是一下子就恍然大悟了？所以遇到这种题的时候，最好自己演算一下，稍微推敲个三
五步，答案就很清晰了。
好，来看一下解题思路：
1. 从第 1 项开始，逐步生成每一项，直到生成第 n 项。
2. 对于当前项的每一个字符，统计其连续出现的次数，并生成下一项的描述。
3. 继续上述过程，直到生成第 n 项。
class Solution03801 {
public String countAndSay(int n) {
// 初始项是 "1"
String result = "1";
// 逐步生成每一项，直到第 n 项
for (int i = 1; i < n; i++) {
result = getNextSequence(result);
}
return result;
}
// 生成外观数列的下一项
private String getNextSequence(String sequence) {
StringBuilder nextSequence = new StringBuilder();
int length = sequence.length();
int count = 1; // 记录当前字符的出现次数
for (int i = 1; i < length; i++) {
if (sequence.charAt(i) == sequence.charAt(i - 1)) {
count++; // 如果当前字符与前一个字符相同，计数加一
} else {
// 如果当前字符与前一个字符不同，将前一个字符和计数添加到下一项中
nextSequence.append(count).append(sequence.charAt(i - 1));
count = 1; // 重置计数
}
}
// 处理最后一个字符
nextSequence.append(count).append(sequence.charAt(length - 1));
return nextSequence.toString();
}
public static void main(String[] args) {
Solution03801 solution = new Solution03801();
int n = 5;
String result = solution.countAndSay(n);
System.out.println("外观数列的第 " + n + " 项: " + result);
}
}
我把测试代码也放进来了，这样子大家可以直接在 IDEA 中运行或者 debug 了解代码的执
行过程。
好，我们把 countAndSay 和 getNextSequence 复制到 LeetCode 上，提交一下，看看结
果。
038.外观数列-20240802180128.png
效率还不错，这其中的核心方法在于 getNextSequence，这个方法是递归调用的关键，我
多加点注释大家细致看看。
private String getNextSequence(String sequence) {
// 用于构建下一项的字符串
StringBuilder nextSequence = new StringBuilder();
// 获取输入字符串的长度
int length = sequence.length();
// 记录当前字符的出现次数，初始值为 1
int count = 1;
// 从索引 1 开始遍历输入字符串
for (int i = 1; i < length; i++) {
// 如果当前字符与前一个字符相同，计数增加
if (sequence.charAt(i) == sequence.charAt(i - 1)) {
count++;
} else {
// 如果当前字符与前一个字符不同，将前一个字符的计数和字符本身添加到结果中
nextSequence.append(count).append(sequence.charAt(i - 1));
// 重置计数为 1
count = 1;
}
}
// 处理最后一个字符及其计数
nextSequence.append(count).append(sequence.charAt(length - 1));
// 将 StringBuilder 转换为字符串并返回
return nextSequence.toString();
}
假设 sequence 为 “1211”，我们来看一下 getNextSequence 的执行过程：
1. 初始化 nextSequence 为一个空的 StringBuilder。
2. 获取 sequence 的长度 length，此时 length 为 4。
3. 初始化 count 为 1。
4. 从索引 1 开始遍历 sequence。
5. 当 i = 1 时，sequence.charAt(1) = ‘2’，sequence.charAt(0) = ‘1’，两者不相等，将
count 和 sequence.charAt(0) 添加到 nextSequence 中，此时 nextSequence 为 “11”。
6. 重置 count 为 1。
7. 当 i = 2 时，sequence.charAt(2) = ‘1’，sequence.charAt(1) = ‘2’，两者不相等，将
count 和 sequence.charAt(1) 添加到 nextSequence 中，此时 nextSequence 为
“1121”。
8. 重置 count 为 1。
9. 当 i = 3 时，sequence.charAt(3) = ‘1’，sequence.charAt(2) = ‘1’，两者相等，count 加
1 为 2。
10. 处理最后一个字符，将 count 和 sequence.charAt(3) 添加到 nextSequence 中，此时
nextSequence 为 “111221”。
能看得出来，这道题在代码层面并没有什么难度，难在理解题目的意思，理解了题目的意
思，代码就水到渠成了。
总结
这道题主要考察的是递归，是 LeetCode 中最常见的题型了，能不能举一反三，就看大家
对递归的掌握程度了。
看似简单，但遇到新的提醒时，能不能快速地理清思路，是我们在刷题过程中需要不断提
升的。
力扣链接：https://leetcode.cn/problems/count-and-say/