LeetCode-38 - 外观数列

题目

<中等> 外观数列

来源：LeetCode.

给定一个正整数 n ，输出外观数列的第 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”

示例 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$

接下来看一下解题思路：

思路一：遍历生成：

    定义字符串 $S_i$表示 $\text{countAndSay(i)}$，我们如果要求得 $S_n$，则我们需先求出 $S_{n-1}$，然后按照上述描述的方法生成，即从左到右依次扫描字符串 $S_{n-1}$中连续相同的字符的最大数目，然后将字符的统计数目转化为数字字符串再连接上对应的字符。已知 $S_1$为 $\text{"1"}$，我们按照上述方法依次生成 $S_2,S_3,\dots ,S_{n-1},S_n$即可。

class Solution {
    public String countAndSay(int n) {
        String str = "1";

        for(int i = 2; i <= n; ++i) {
            StringBuilder sb = new StringBuilder();
            int start = 0;
            int pos = 0;

            while (pos < str.length()) {
                while (pos < str.length() && (str.charAt(pos) == str.charAt(start))) {
                    ++pos;
                }
                sb.append((pos - start)).append(str.charAt(start));
                start = pos;
            }
            str = sb.toString();
        }
        return str;
    }
}

思路二：递归：

    题目中给定的递归公式定义的数字字符串序列如下：

• $\text{countAndSay(1) = "1"}$；

• $\text{countAndSay(n)}$ 是对 $\text{countAndSay(n-1)}$ 的描述，然后转换成另一个数字字符串。

class Solution {
    public String countAndSay(int n) {
        if(n == 1) {
            return "1";
        }
        // 要想知道第 n 个，首先需要知道 第 n - 1 个
        String in = countAndSay(n - 1);

        int length = in.length();
        StringBuilder sb = new StringBuilder();
        int start = 0;
        int pos = 0;

        while (pos < length) {
            while (pos < in.length() && (in.charAt(pos) == in.charAt(start))) {
                ++pos;
            }
            sb.append((pos - start)).append(in.charAt(start));
            start = pos;
        }
        return sb.toString();
    }
}

复杂度分析

时间复杂度：$O(N\times M)$，其中 $N$ 为给定的正整数，$M$ 为生成的字符串中的最大长度。
空间复杂度：$O(M)$。其中 $M$ 为生成的字符串中的最大长度。