题目描述
这是 LeetCode 上的 38. 外观数列 ，难度为 简单。
Tag : 「模拟」
给定一个正整数 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" 复制代码
要描述一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。
例如，数字字符串 "3322251" 的描述如下图：
示例 1：
输入：n = 1 输出："1" 解释：这是一个基本样例。 复制代码
示例 2：
输入：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 = 1k=1 时 ans = "1" 出发，逐步递推到 k = nk=n 的情况，对于第 kk 项而言，其实就是对第 k - 1k−1 项的「连续段」的描述，而求「连续段」长度，可以使用双指针实现。
代码：
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; } } 复制代码
- 时间复杂度：O(n^2)O(n2)
- 空间复杂度：O(n)O(n)
打表
利用数据范围只有 3030，我们可以使用 static 进行打表操作，从而节省掉不同样例之间的「重复」部分的计算量。
例如对于 n = 5n=5 和 n = 6n=6 都存在先计算前五项的公共部分，打表可以确保这部分只会被计算一次，同时能够应用到后面项中。
代码：
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)O(1)；放到 OJOJ 执行则为 O(n^2)O(n2)
- 空间复杂度：O(C)O(C)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.38 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
