LeetCode 38. 外观数列

2023-07-26 HGNULB 约 8 分钟

文章信息 6 个分类 1 个标签

分类

题目描述

✅ 38. 外观数列

题意分析

这是一个由字符串递推定义的序列：第一项固定是 "1"，之后每一项都由「读出上一项」得到——把上一项按连续相同的数字切成若干段，每段写成「段长 + 该数字」，再依次拼起来。题目要求返回第 $n$ 项。

「读出」这个动作要读准："1211" 应当被切成 1、2、11 三段，读作「一个 $1$、一个 $2$、两个 $1$」，得到 "111221"。切分依据是相邻字符是否相同，而不是按固定长度或按数值大小。

约束是 $1 \le n \le 30$，是个很小的常数。这个上界的意义在于：序列长度虽然每一项都在增长（增长率约为 $1.3$ 倍），但到第 $30$ 项也只有几千个字符，所以老老实实迭代生成完全可行，不需要找通项公式——事实上这个序列也没有简洁的闭式通项。

边界方面：$n = 1$ 时直接返回 "1"，一次生成都不做；段长有可能达到两位数吗？这个序列的性质保证任何一项里连续相同数字最多出现三个，所以段长恒为一位，但实现上不该依赖这个性质，用通用的数字转字符串更稳。

解法：字符串分组计数

核心思路

这题不存在「暴力与优化」的对立，真正的问题是怎么把递推定义准确无误地翻译成代码，以及避免朴素实现里的性能陷阱。

朴素实现最容易踩的坑是用不可变字符串反复做 += 拼接：每次拼接都要复制一遍已有内容，一项内部的拼接就退化成平方级别，几十项累积下来常数相当可观。所以用可变缓冲区（Java 的 StringBuilder、Go 的字节切片）逐段追加，是这类题的标准写法。

生成一项的核心是分段扫描。用一个游标从左往右走，每次先记下段的起点和该段的字符，然后让游标一直前进到字符发生变化或越界为止，此时「游标 $-$ 起点」就是段长。这里维持的不变量是：每一轮外层循环处理完，游标恰好停在下一段的第一个字符上，且缓冲区里已经写完了此前所有段的描述。因为每段都由「一段连续相同字符」唯一确定，且段与段之间无缝衔接，所以扫描一遍就能不重不漏地切分完毕。

外层用一个从第 $2$ 项数到第 $n$ 项的循环驱动，每轮把新生成的字符串赋回当前值。注意生成新串时必须始终读取上一项的完整快照，不能边读边改同一个缓冲区。

解题步骤

把当前项初始化为 "1"，这是序列的定义起点。若 $n = 1$，外层循环一次都不执行，直接返回它。

外层循环从 $i = 2$ 走到 $i = n$，每轮生成一项。之所以从 $2$ 起步而不是从 $1$，是因为第 $1$ 项是给定的，共需要 $n-1$ 次生成。

每轮开始时新建一个可变缓冲区，用来承载本轮结果。缓冲区必须独立于当前项，读写分离才能保证读到的是完整的上一项。

内层用游标 idx 从 $0$ 扫到末尾。每段开始时记下 start = idx 和该段字符 ch，然后让 idx 在「未越界且字符仍等于 ch」的条件下持续前进。两个条件的先后顺序不能颠倒，否则末段会读到越界位置。

内层小循环结束后，段长就是 idx - start，把段长和字符依次追加进缓冲区。追加顺序是「先数量后字符」，这是题目对「读出」的定义，反过来就成了另一个完全不同的序列。

一轮扫描结束后把缓冲区转成字符串赋回当前项，进入下一轮。所有轮次跑完后返回当前项。

以 n = 5 走一遍：初始当前项为 "1"。第 $2$ 轮读 "1"，游标从 $0$ 出发，段字符是 '1'，一直走到越界停在 $1$，段长为 $1$，追加得 "11"，当前项更新为 "11"。第 $3$ 轮读 "11"，游标从 $0$ 出发，段字符 '1'，连续走过两个 '1' 停在 $2$，段长为 $2$，追加得 "21"，当前项更新为 "21"。第 $4$ 轮读 "21"：第一段起点 $0$、字符 '2'，走一步停在 $1$，段长 $1$，追加 "12"；第二段起点 $1$、字符 '1'，走一步停在 $2$ 越界，段长 $1$，追加 "11"；合并得 "1211"，当前项更新为 "1211"。第 $5$ 轮读 "1211"：第一段起点 $0$、字符 '1'，停在 $1$，段长 $1$，追加 "11"；第二段起点 $1$、字符 '2'，停在 $2$，段长 $1$，追加 "12"；第三段起点 $2$、字符 '1'，连续走过下标 $2$ 和 $3$ 后停在 $4$ 越界，段长 $2$，追加 "21"；合并得 "111221"。外层循环到此结束，返回 "111221"，与题目给出的第 $5$ 项一致。

代码实现

// 每次遍历当前字符串，按连续相同字符分组，拼接 `数量 + 字符`。
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;
    }
}

// 每次遍历当前字符串，按连续相同字符分组，拼接 `数量 + 字符`。
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(L)$，$L$ 为第 $n$ 项的长度。生成每一项时游标只单向走过上一项一遍，代价与该项长度成正比；各项长度呈约 $1.3$ 倍的等比增长，所有项长度之和被最后一项主导，故总代价与 $L$ 同阶。$n \le 30$ 时 $L$ 只有几千。

空间复杂度：$O(L)$。同一时刻只需保存上一项和正在构造的这一项，两者长度均为 $O(L)$；不保留历史项，也没有递归栈。

关键点总结

面对递推定义的序列，先把「一步递推」封装清楚再考虑迭代次数。本题把「读出一个字符串」这一步写对，外层循环就只是简单的重复调用。

分段扫描的标准骨架是「记起点、取段值、内层前进到不同为止、结算段长」。这个骨架在游程编码、压缩字符串、统计连续重复段等题里可以直接复用。

内层循环的判空条件必须写在字符比较之前。这是短路求值的常见依赖，顺序写反会在处理末段时越界。

字符串在循环里反复拼接要用可变缓冲区。这不只是常数优化，在项数较多时能把平方级的复制降回线性。

面试视角：面试官往往先让你手算前五项确认理解无误，再让你写代码。主动先口算 "1" → "11" → "21" → "1211" → "111221"，能避免因误解「读出」规则而整题写偏。

面试视角：常见追问是「段长会不会超过 $9$」。可以答出该序列任意项中连续相同数字最多三个，但同时说明代码用通用的数字转字符串处理，不依赖这个性质，体现健壮性意识。

易错点总结

错误写法：追加顺序写成「先字符后数量」 → 第 $3$ 项会得到 "12" 而非 "21"，之后每一项都偏离，$n = 5$ 时返回的串与正确的 "111221" 完全不同。

错误写法：外层循环从 $i = 1$ 开始 → 多做一次生成，$n = 1$ 时会返回 "11"，正确答案是 "1"。

错误写法：内层条件写成 cur.charAt(idx) == ch && idx < cur.length() → 处理最后一段时先求值的是字符访问，直接越界抛异常。

错误写法：在同一个缓冲区上边读边写 → 新追加的内容会被当作上一项的一部分继续读取，产生自我引用的无限增长，第一轮就得不到 "11"。

错误写法：分段时用 cur.charAt(idx) == cur.charAt(idx - 1) 且不保护下标 $0$ → 首段起点处访问下标 $-1$ 越界；即使加了保护，段边界的归属也容易差一。

错误写法：段长直接用 char 拼接，例如 (char)(count) → 段长 $2$ 会被拼成 ASCII 码为 $2$ 的控制字符而不是字符 '2'，输出串不可读；必须用 count + '0' 或数字转字符串。

错误写法：假定段长恒为一位从而用单字符写入 → 虽然本序列确实不会出现四连相同数字，但这个前提没有在题面中给出，一旦初始项改变（例如某些变体从 "3" 起步）就会截断。

错误写法：用 String cur += ... 在内层逐段拼接 → 每次拼接复制整串，单项生成退化成平方级，虽然 $n \le 30$ 时仍能跑完，但在面试中会被指出为明显的性能缺陷。

错误写法：以为可以用哈希表缓存「某个数字读作什么」来加速 → 读出的结果依赖的是连续段长而非单个数字，缓存的键根本无法覆盖状态，会得到错误结果。

错误写法：把「外观数列」误解成对整个字符串按数值统计，例如统计 "1211" 中数字 $1$ 出现三次、数字 $2$ 出现一次而输出 "3112" → 这忽略了「连续」这个限定，正确结果是 "111221"。

相似题目

题目	难度	考察点
443. 压缩字符串	中等	同为游程编码，但要求原地写回且段长为 $1$ 时省略数字
420. 强密码检验器	困难	分段统计后还要按余数做贪心分配，重点在代价而非拼接
482. 密钥格式化	简单	按固定长度而非按内容分组，考察从右往左的分组与补齐
6. Z 字形变换	中等	按行号规律重排字符，同样靠可变缓冲区避免反复拼接
68. 文本左右对齐	困难	分组规则由宽度限制决定，且需要处理末行与空格分配的特例