LeetCode 38. 外观数列
题目描述
✅ 38. 外观数列
题意分析
第一项是字符串
"1"。之后每一项都描述上一项：从左到右把连续相同数字分成一组，依次写出每组的数量和数字本身，求第n项。
解法：字符串分组计数
核心思路
[!blue]
第
n项只依赖第n - 1项，因此从"1"出发迭代生成即可，不需要保存整条数列。用cur保存上一项，另建缓冲区保存本轮的新字符串，避免把刚生成的内容再次当作输入。每轮用
idx指向尚未处理的第一个字符，记住组起点start和字符ch，向右移动直到遇到不同字符或字符串末尾。此时[start, idx)恰好是一整组，数量为idx - start，向缓冲区追加这个数量的十进制文本，再追加ch。一组结束后，
idx已指向下一组的开头，无需额外移动。各组恰好覆盖上一项且保持原顺序，逐组拼接就得到定义中的下一项；整轮完成后才替换cur。执行n - 1轮后，cur就是答案。
解题步骤
- 初始化
cur = "1"。- 从第 2 项生成到第
n项，每轮创建空缓冲区，并从idx = 0开始扫描。- 找到当前连续段的右边界，追加段长与字符，再接着处理下一组。
- 扫描完上一项后，用缓冲区结果替换
cur，最终返回它。
n == 1时无需生成，直接返回初始项。最后一组由到达字符串末尾结束，也必须正常追加，不能只在遇到不同字符时输出。
代码实现
// 每次遍历当前字符串，按连续相同字符分组，拼接 `数量 + 字符`。
class Solution {
public String countAndSay(int n) {
String cur = "1";
for (int i = 2; i <= n; i++) {
StringBuilder sb = new StringBuilder();
int idx = 0;
while (idx < cur.length()) {
int start = idx;
char ch = cur.charAt(idx);
while (idx < cur.length() && cur.charAt(idx) == ch) {
idx++;
}
// 当前段已完整扫描，长度由结束位置减起点得到
sb.append(idx - start).append(ch);
}
// 整轮生成后才替换上一项，不能读到正在追加的新内容
cur = sb.toString();
}
return cur;
}
}
import "strconv"
// 每次遍历当前字符串，按连续相同字符分组，拼接 `数量 + 字符`。
func countAndSay(n int) string {
cur := "1"
for i := 2; i <= n; i++ {
builder := make([]byte, 0, len(cur)*2)
idx := 0
for idx < len(cur) {
start := idx
ch := cur[idx]
for idx < len(cur) && cur[idx] == ch {
idx++
}
// 当前段已完整扫描，长度由结束位置减起点得到
count := idx - start
builder = append(builder, []byte(strconv.Itoa(count))...)
builder = append(builder, ch)
}
// 整轮生成后才替换上一项，不能读到正在追加的新内容
cur = string(builder)
}
return cur
}
复杂度分析
- 时间复杂度：$O(T)$，
T为各轮扫描与生成的字符总数，含初始项。- 空间复杂度：$O(L)$，
L为生成过程中最大项长度，只同时保存相邻两项。
关键点总结
[!green]
- 连续段频次与整串频次不同。
- 数量必须转为十进制文本再追加。
- 每轮只读取上一项，扫描结束后再整体替换，满足迭代生成要求。
易错点总结
[!yellow]
- 先写字符再写数量，会改变递推规则。
- 生成时同时修改正在读取的上一项，会把新内容重新当作输入。
- 循环从第一项再生成一次，会多做一轮。
- 内层循环结束后
idx已位于下一组起点，再自增一次会漏掉字符。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 443. 压缩字符串 | 中等 | 同样扫描连续相同字符段并编码次数，本题把前一轮描述作为下一轮输入。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！