LC 38. 外观数列

题目描述

这是 LeetCode 上的 38. 外观数列 ，难度为 简单。

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

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

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

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

前五项如下：

1
2
3
4
5
6
7
8
9
10
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"

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

例如，数字字符串 "3322251" 的描述如下图：

示例 1：

1
2
3
4
5
输入：n = 1

输出："1"

解释：这是一个基本样例。

示例 2：
1
2
3
4
5
6
7
8
9
输入：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 <= n <= 30$

模拟

一个朴素的想法是：根据题意进行模拟，从起始条件 $k = 1$ 时 ans = "1" 出发，逐步递推到 $k = n$ 的情况，对于第 $k$ 项而言，其实就是对第 $k - 1$ 项的「连续段」的描述，而求「连续段」长度，可以使用双指针实现。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String countAndSay(int n) {
        String ans = "1";
        for (int i = 2; i <= n; i++) {
            String cur = "";
            int m = ans.length();
            for (int j = 0; j < m; ) {
                int k = j + 1;
                while (k < m && ans.charAt(j) == ans.charAt(k)) k++;
                int cnt = k - j;
                cur += cnt + "" + ans.charAt(j);
                j = k;
            }
            ans = cur;
        }
        return ans;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string countAndSay(int n) {
        string ans = "1";
        for (int i = 2; i <= n; i++) {
            string cur = "";
            int m = ans.length();
            for (int j = 0; j < m; ) {
                int k = j + 1;
                while (k < m && ans[j] == ans[k]) k++;
                int cnt = k - j;
                cur += to_string(cnt) + ans[j];
                j = k;
            }
            ans = cur;
        }
        return ans;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def countAndSay(self, n: int) -> str:
        ans = "1"
        for i in range(2, n + 1):
            cur = ""
            m, j = len(ans), 0
            while j < m:
                k = j + 1
                while k < m and ans[j] == ans[k]:
                    k += 1
                cnt = k - j
                cur += str(cnt) + ans[j]
                j = k
            ans = cur
        return ans

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function countAndSay(n: number): string {
    let ans: string = "1";
    for (let i: number = 2; i <= n; i++) {
        let cur: string = "";
        let m: number = ans.length;
        for (let j: number = 0; j < m; ) {
            let k: number = j + 1;
            while (k < m && ans[j] === ans[k]) {
                k++;
            }
            const cnt: number = k - j;
            cur += cnt.toString() + ans[j];
            j = k;
        }
        ans = cur;
    }
    return ans;
};

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$

打表

利用数据范围只有 $30$，我们可以使用 static 进行打表操作，从而节省掉不同样例之间的「重复」部分的计算量。

例如对于 $n = 5$ 和 $n = 6$ 都存在先计算前五项的公共部分，打表可以确保这部分只会被计算一次，同时能够应用到后面项中。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    static String[] f = new String[35];
    static {
        f[1] = "1";
        for (int i = 2; i < 35; i++) {
            String prev = f[i - 1], cur = "";
            int m = prev.length();
            for (int j = 0; j < m; ) {
                int k = j + 1;
                while (k < m && prev.charAt(j) == prev.charAt(k)) k++;
                int cnt = k - j;
                cur += cnt + "" + prev.charAt(j);
                j = k;
            }
            f[i] = cur;
        }
    }
    public String countAndSay(int n) {
        return f[n];
    }
}

  • 时间复杂度：将打表逻辑到放本地执行，复杂度为 $O(1)$；放到 $OJ$ 执行则为 $O(n^2)$
  • 空间复杂度：$O(C)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.38 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。