外观数列 | 每日算法 · 变量语义法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

「外观数列」是一个数位字符串序列，由递归公式定义：

countAndSay(1) = "1"
countAndSay(n) 是 countAndSay(n-1) 的行程长度编码（RLE）。

行程长度编码将每个最大连续相同字符组替换为「组长度 + 该字符」。例如 "3322251" 编码为 "23321511"（"33"→"23"，"222"→"32"，"5"→"15"，"1"→"11"）。

给定整数 n，返回外观数列的第 n 项。

示例 1

输入：n = 4

输出："1211"

countAndSay(1) = "1"
countAndSay(2) = "1" 的 RLE = "11"
countAndSay(3) = "11" 的 RLE = "21"
countAndSay(4) = "21" 的 RLE = "1211"

示例 2

输入：n = 1

输出："1"

基本情况，无需编码。

💭 模拟答题者思考

1. 我先想暴力：按定义递归 countAndSay(n-1) 再对其做 RLE——逻辑对，但每层都重新从头编码，函数调用栈深 n，且中间串反复构造。

2. 重复在哪里？无论递归还是迭代，核心子问题都是「给定字符串 s，输出它的行程长度编码」；第 k 项只依赖第 k-1 项，与更早项无关。

3. 关键转化：迭代维护 cur，从 "1" 出发做 n-1 轮编码；每轮用双指针扫描 cur，数清连续相同字符后追加 计数+字符 到 nxt。

4. 手推 n=4："1"→"11"→"21"→"1211"。第三轮读 "21"：先 1 个 '2' 得 "12"，再 1 个 '1' 得 "11"，合并 "1211"。

5. n=1 直接返回 "1"，循环 0 次；n≤30 时串长可控，双指针每轮总扫描长度等于当前串长，整体可行。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`cur`	str	定义：当前轮的外观数列字符串，初始为 `"1"` 维护：每完成一轮 RLE 编码后，`cur` 被替换为新生成的字符串更新：外层循环执行 `n-1` 次后，`cur` 即为第 `n` 项答案
`nxt`	str / StringBuilder	定义：对 `cur` 做一轮行程长度编码后得到的新串维护：每轮编码前清空，扫描 `cur` 时逐段追加 `计数+字符` 更新：一轮扫描结束后令 `cur = nxt`，进入下一轮
`i`	int	定义：在 `cur` 上的扫描指针，指向当前连续段的起始位置维护：每处理完一段相同字符后，跳到该段末尾的下一位更新：内层 `while i < len(cur)` 循环推进；段长由 `j` 探测得到
`j`	int	定义：从 `i` 出发，向右延伸直到字符与 `cur[i]` 不同维护：`cnt = j - i` 即为当前连续段长度更新：将 `str(cnt) + cur[i]` 追加到 `nxt` 后，令 `i = j`
`cnt`	int	定义：以 `cur[i]` 为首的连续相同字符个数维护：由双指针 `i, j` 一次 O(段长) 统计，每段只算一次更新：编码为十进制数字字符串拼在字符前，如 `3` 个 `'2'` → `"32"`

⌨️ 落码步骤

1. 若 n == 1，直接返回 "1"

2. 令 cur = "1"，准备执行 n-1 轮编码

3. 每轮初始化空串 nxt，双指针 i = 0 扫描 cur

4. 固定 ch = cur[i]，令 j = i 向右扩直到 cur[j] != ch，cnt = j - i

5. 将 str(cnt) + ch 追加到 nxt，i = j 处理下一段

6. 一轮结束 cur = nxt；全部轮次完成后返回 cur

💻 代码实现

class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"
        cur = "1"
        for _ in range(n - 1):
            nxt = []
            i = 0
            while i < len(cur):
                ch = cur[i]
                j = i
                while j < len(cur) and cur[j] == ch:
                    j += 1
                nxt.append(str(j - i))
                nxt.append(ch)
                i = j
            cur = "".join(nxt)
        return cur

class Solution {
public:
    string countAndSay(int n) {
        if (n == 1) return "1";
        string cur = "1";
        for (int round = 1; round < n; ++round) {
            string nxt;
            for (int i = 0; i < (int)cur.size(); ) {
                char ch = cur[i];
                int j = i;
                while (j < (int)cur.size() && cur[j] == ch) ++j;
                nxt += to_string(j - i);
                nxt += ch;
                i = j;
            }
            cur = move(nxt);
        }
        return cur;
    }
};
// 时间 O(L)，空间 O(L)

📈 复杂度分析

时间复杂度 O(L)（L 为各轮字符串长度之和，n≤30 时可控）

空间复杂度 O(L)（存放当前轮与下一轮字符串）

⚠️ 常见坑

❗ 计数与字符拼接顺序反了：应先写个数再写字符，3 个 '2' 是 "32" 而非 "23"。

❗ 循环次数 off-by-one：只需编码 n-1 次；多跑一轮会把答案再 RLE 一次，n=4 会错成 "111221"。

❗ 内层扫描未正确跳段：每处理完一段必须令 i = j，否则会在同一字符上死循环或重复计数。

🔍 必测边界 Case

Case 1：n = 1

直接返回 "1"，不进入编码循环

Case 2：n = 4

经典手推链 "1"→"11"→"21"→"1211"

Case 3：含多段相同模式

"111221" 编码为 "312211"（3个1 + 2个2 + 1个1）

Case 4：单字符段

"21" 中两段长度均为 1 → "1211"

Case 5：较大 n

n = 30 时串长可达数千，仍须用 O(当前长度) 扫描，避免暴力递归重复计算