Vue.js

Appearance

On this page

实战：外观数列 ​

这道题的难点不在于算法，而在于理解题意。很多人第一次看到题目描述时会一脸懵——"描述"是什么意思？

首先要问一个问题：什么叫"对前一项的描述"？

题目描述 ​

LeetCode 38. 外观数列

给定一个正整数 n，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

让我们看看这个序列是怎么生成的：

n=1:  "1"
      第 1 项就是 "1"

n=2:  "11"
      描述第 1 项 "1"：一个 1 → "11"

n=3:  "21"
      描述第 2 项 "11"：两个 1 → "21"

n=4:  "1211"
      描述第 3 项 "21"：一个 2，一个 1 → "1211"

n=5:  "111221"
      描述第 4 项 "1211"：一个 1，一个 2，两个 1 → "111221"

懂了吗？所谓"描述"，就是报数：数一数有几个连续相同的数字，然后说出来。

这就是为什么英文名叫 "Count and Say"——数（count）然后说（say）。

解题思路 ​

现在我要问第二个问题：如何实现"描述"这个操作？

核心是统计连续相同字符。遍历字符串，记录当前字符和它的连续出现次数，当遇到不同字符时，输出描述。

然后从 "1" 开始，执行 n-1 次描述操作即可。

解法：迭代描述 ​

javascript
function countAndSay(n) {
    let result = '1';  // 第 1 项
    
    // 执行 n-1 次描述
    for (let i = 1; i < n; i++) {
        result = describe(result);
    }
    
    return result;
}

// 描述一个字符串
function describe(s) {
    let desc = '';
    let count = 1;
    
    for (let i = 0; i < s.length; i++) {
        // 检查下一个字符是否相同
        if (i + 1 < s.length && s[i + 1] === s[i]) {
            count++;
        } else {
            // 不同或到达末尾，记录描述
            desc += count + s[i];  // "几个什么"
            count = 1;  // 重置计数
        }
    }
    
    return desc;
}

执行过程追踪 ​

以 n = 5 为例：

初始：result = "1"

i=1: result = describe("1")
     遍历 "1"：
       i=0, char='1', 下一个越界, desc="11", count=1
     result = "11"

i=2: result = describe("11")
     遍历 "11"：
       i=0, char='1', 下一个='1'相同, count=2
       i=1, char='1', 下一个越界, desc="21", count=1
     result = "21"

i=3: result = describe("21")
     遍历 "21"：
       i=0, char='2', 下一个='1'不同, desc="12", count=1
       i=1, char='1', 下一个越界, desc="1211", count=1
     result = "1211"

i=4: result = describe("1211")
     遍历 "1211"：
       i=0, char='1', 下一个='2'不同, desc="11", count=1
       i=1, char='2', 下一个='1'不同, desc="1112", count=1
       i=2, char='1', 下一个='1'相同, count=2
       i=3, char='1', 下一个越界, desc="111221", count=1
     result = "111221"

返回 "111221"

复杂度分析 ​

  • 时间复杂度：O(n × m)，n 是项数，m 是字符串长度。字符串长度增长较快，但对于合理的 n（题目约束 n ≤ 30），这是可接受的
  • 空间复杂度：O(m)，存储当前项

双指针优化 ​

describe 函数还可以用双指针写，逻辑更清晰：

javascript
function describe(s) {
    let desc = '';
    let i = 0;
    
    while (i < s.length) {
        const char = s[i];
        let j = i;
        
        // j 指针找到连续相同字符的结束位置
        while (j < s.length && s[j] === char) {
            j++;
        }
        
        // j - i 就是连续字符的个数
        desc += (j - i) + char;
        i = j;  // 跳到下一段
    }
    
    return desc;
}

这种写法的好处是：每轮循环处理一个"连续段"，逻辑边界更清晰。

递归写法 ​

既然是递推关系，自然也可以用递归：

javascript
function countAndSay(n) {
    if (n === 1) return '1';
    
    // 先获取前一项，再描述
    return describe(countAndSay(n - 1));
}

代码更简洁，但有递归调用的开销。对于 n ≤ 30，两种写法性能差异不大。

常见错误 ​

  1. 理解题意：这是"描述"题不是"计算"题，不要试图找数学规律
  2. 边界处理：最后一组连续字符必须正确输出。上面的代码通过 else 分支或 while 循环结束条件自然处理了这一点
  3. n=1 特殊情况：直接返回 "1"，不需要进入循环

本章小结 ​

外观数列的核心是连续字符计数——这是字符串处理中的常见模式。

解题步骤：

  1. 理解"描述"操作：统计连续相同字符，输出"几个什么"
  2. 从 "1" 开始，迭代执行描述操作 n-1 次
  3. 用双指针或计数器实现描述函数

这道题属于"理解题意比实现困难"的类型。一旦搞清楚规则，代码本身并不复杂。

相关题目 ​

  • 443. 压缩字符串：原地压缩，类似的分组计数思想
  • 13. 罗马数字转整数：逐字符解析，相似的遍历模式

下一章我们来看另一个经典问题——字符串形式的大数相加。

在 GitHub 上编辑此页