019-外观数列 (Count and Say)

题目描述

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

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

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1
描述前一项，这个数是 1 即 " 一 个 1 "，记作 "11"
描述前一项，这个数是 11 即 " 二 个 1 " ，记作 "21"
描述前一项，这个数是 21 即 " 一 个 2 + 一 个 1 " ，记作 "1211"
描述前一项，这个数是 1211 即 " 一 个 1 + 一 个 2 + 二 个 1 " ，记作 "111221"

要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

示例

输入：n = 1
输出："1"
解释：这是一个基本样例。

输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

解题思路

使用模拟法，从第1项开始，逐步生成每一项。对于每一项，遍历字符串，统计连续相同字符的个数，然后生成描述字符串。

JavaScript 解决方案

/**
 * @param {number} n
 * @return {string}
 */
const countAndSay = (n) => {
    if (n === 1) return "1";
    
    let result = "1";
    
    for (let i = 2; i <= n; i++) {
        let current = "";
        let count = 1;
        let char = result[0];
        
        for (let j = 1; j < result.length; j++) {
            if (result[j] === char) {
                count++;
            } else {
                current += count + char;
                char = result[j];
                count = 1;
            }
        }
        
        // 处理最后一组
        current += count + char;
        result = current;
    }
    
    return result;
};

复杂度分析

时间复杂度：O(n × L)，其中 n 是项数，L 是字符串的平均长度
空间复杂度：O(L)，需要存储当前项的字符串

测试用例

// 测试函数
const testCountAndSay = () => {
    const testCases = [
        {
            n: 1,
            expected: "1"
        },
        {
            n: 2,
            expected: "11"
        },
        {
            n: 3,
            expected: "21"
        },
        {
            n: 4,
            expected: "1211"
        },
        {
            n: 5,
            expected: "111221"
        },
        {
            n: 6,
            expected: "312211"
        },
        {
            n: 7,
            expected: "13112221"
        },
        {
            n: 8,
            expected: "1113213211"
        }
    ];

    testCases.forEach((testCase, index) => {
        const result = countAndSay(testCase.n);
        const passed = result === testCase.expected;
        console.log(`测试用例 ${index + 1}: ${passed ? '通过' : '失败'}`);
        console.log(`输入: n = ${testCase.n}`);
        console.log(`期望: "${testCase.expected}", 实际: "${result}"\n`);
    });
};

// 运行测试
testCountAndSay();

关键点总结

递归生成：每一项都是对前一项的描述
字符统计：统计连续相同字符的个数
字符串拼接：将个数和字符拼接成描述
边界处理：处理第一项和最后一组字符
迭代实现：使用循环而不是递归避免栈溢出

总结

这道题考察了以下重点：

字符串处理：如何高效地处理字符串拼接
字符统计：如何统计连续相同字符的个数
迭代思维：理解递归问题的迭代解法
边界处理：对特殊情况的处理

模拟法是最优解，时间复杂度为 O(n × L)，空间复杂度为 O(L)。在实际面试中，建议先理解外观数列的生成规律，然后实现算法。

019-外观数列 (Count and Say)

On this page