38. 外观数列
题目描述
外观数列是一串由数字字符组成的字符串。第 1 项是 "1"。从第 2 项起，每一项都是对前一项的“描述”。
描述的方法：把前一项切成若干段，每段由尽可能长的一串相同数字构成；每段写成“个数”后接“那个数字”，再按顺序连起来。例如 "3322251" 切成 33、222、5、1，描述为 "23321511"。
输入正整数 n，返回外观数列的第 n 项。
示例 1
输入：n = 1 输出："1"
解释：第 1 项就是 "1"。
示例 2
输入：n = 4 输出："1211"
解释：第 2 项描述“一个 1”得 "11"，第 3 项描述“两个 1”得 "21"，第 4 项描述“一个 2、一个 1”得 "1211"。
数据范围
1 <= n <= 30
进阶：能否不用递归，用循环完成？
解题思路
按定义模拟 n-1 轮。每一轮用双指针分段：i 指向一段的开头，j 向右走到第一个与 s[i] 不同的位置，这一段长 j-i，输出 "j-i" 和 s[i]，然后 i 跳到 j。一轮结束后把各段拼起来作为新的 s。
为什么正确
每轮内，s[:i] 已经被完整地描述在 nxt 中，且 i 总是一段的开头。
复杂度分析
时间 O(各项长度之和)，外观数列长度大约每项增长 30%，故约为 O(1.3^n)；空间与最后一项的长度同阶。
易错点
只描述连续相同的数字，不是统计整个字符串里每个数字的总次数："1211" 的下一项是 "111221"，不是 "3112"。另外只需要循环 n-1 轮。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def countAndSay(self, n: int) -> str:
s = '1'
for _ in range(n - 1):
nxt = []
i = 0
while i < len(s):
j = i
while j < len(s) and s[j] == s[i]:
j += 1
nxt.append(str(j - i) + s[i])
i = j
s = ''.join(nxt)
return sclass Solution {
public String countAndSay(int n) {
String s = "1";
for (int t = 0; t < n - 1; t++) {
StringBuilder nxt = new StringBuilder();
int i = 0;
while (i < s.length()) {
int j = i;
while (j < s.length() && s.charAt(j) == s.charAt(i)) {
j++;
}
nxt.append(j - i).append(s.charAt(i));
i = j;
}
s = nxt.toString();
}
return s;
}
}class Solution {
public:
string countAndSay(int n) {
string s = "1";
for (int t = 0; t < n - 1; t++) {
string nxt;
int i = 0;
while (i < (int)s.size()) {
int j = i;
while (j < (int)s.size() && s[j] == s[i]) {
j++;
}
nxt += to_string(j - i) + s[i];
i = j;
}
s = nxt;
}
return s;
}
};func countAndSay(n int) string {
s := "1"
for t := 0; t < n-1; t++ {
nxt := []byte{}
i := 0
for i < len(s) {
j := i
for j < len(s) && s[j] == s[i] {
j++
}
nxt = append(nxt, strconv.Itoa(j-i)...)
nxt = append(nxt, s[i])
i = j
}
s = string(nxt)
}
return s
}var countAndSay = function(n) {
let s = '1';
for (let t = 0; t < n - 1; t++) {
const nxt = [];
let i = 0;
while (i < s.length) {
let j = i;
while (j < s.length && s[j] === s[i]) {
j++;
}
nxt.push(String(j - i) + s[i]);
i = j;
}
s = nxt.join('');
}
return s;
};function countAndSay(n: number): string {
let s = '1';
for (let t = 0; t < n - 1; t++) {
const nxt: string[] = [];
let i = 0;
while (i < s.length) {
let j = i;
while (j < s.length && s[j] === s[i]) {
j++;
}
nxt.push(String(j - i) + s[i]);
i = j;
}
s = nxt.join('');
}
return s;
}