【刷穿 LeetCode】38. 外观数列（简单）
题目描述
给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：
- countAndSay(1) = "1"
- countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。
例如，数字字符串 "3322251" 的描述如下图：
示例 1：
输入：n = 1
输出："1"
解释：这是一个基本样例。
示例 2：
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
提示：
1 <= n <= 30
朴素解法
这是一道模拟题。
我们可以实现一个 nextString 方法，传入一个字符串 s，返回该字符串对应的外观数列。
具体的实现，我们只需要统计字符串 s 中每一段连续出现的字符的类型和出现次数即可：
class Solution {
public String countAndSay(int n) {
String s = "1";
for (int i = 2; i <= n; i++) {
s = nextString(s);
}
return s;
}
String nextString(String s) {
StringBuilder sb = new StringBuilder();
int n = s.length();
char[] cs = s.toCharArray();
char c = cs[0];
int cnt = 1;
for (int i = 1; i < n; i++) {
char cur = cs[i];
if (cur == c) {
cnt++;
} else {
sb.append(cnt);
sb.append(c);
c = cur;
cnt = 1;
}
}
sb.append(cnt);
sb.append(c);
return sb.toString();
}
}
- 时间复杂度：循环
n次，复杂度为
；每次循环处理一遍当前的 s 字符串，复杂度为
。整体复杂度为
。
- 空间复杂度：
使用「哨兵技巧」做一些小优化
之前三叶在不少的链表题中为你介绍过「哨兵技巧」，例如 【刷穿 LeetCode】24. 两两交换链表中的节点（中等） 。
但是「哨兵」可不是只能应用在链表题上，「哨兵」的本质是帮助我们简化边界的判断。
例如我们上述解法中，就可以使用「哨兵技巧」来简化我们统计的逻辑，避免在循环外统计最后一次字符：
class Solution {
public String countAndSay(int n) {
String s = "1";
for (int i = 2; i <= n; i++) {
s = nextString(s);
}
return s;
}
String nextString(String s) {
// 往结尾添加一个“哨兵”
s = s + "a";
StringBuilder sb = new StringBuilder();
int n = s.length();
char[] cs = s.toCharArray();
char c = cs[0];
int cnt = 1;
for (int i = 1; i < n; i++) {
char cur = cs[i];
if (cur == c) {
cnt++;
} else {
sb.append(cnt);
sb.append(c);
c = cur;
cnt = 1;
}
}
return sb.toString();
}
}
- 时间复杂度：循环
n次，复杂度为
；每次循环处理一遍当前的 s 字符串，复杂度为
。整体复杂度为
。
- 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.38 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 38/1916 。
为了方便各位同学能够电脑上进行调试和提交代码，我在 Github 建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。
腾讯云开发者
