leecode-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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# author：sarizzm time:2020/12/31 0031

class Solution:
    def countAndSay(self, n):
        result = ''
        start_str = ''
        for i in range(n):
            num = 0
            if i == 0:
                start_str = '1'
                continue
            for j in range(len(start_str)):
                num += 1
                if j< len(start_str)-1 and start_str[j] == start_str[j+1]:
                    continue
                else:   # 当start_str[j] ！= start_str[j+1] 或者j=len(start_str)-1时，num肯定也是为1的
                    result = result + str(num) + start_str[j]
                    num = 0
            start_str = result
            result = ''
        return start_str

# print(Solution().countAndSay(0))
print(Solution().countAndSay(1))
print(Solution().countAndSay(2))
print(Solution().countAndSay(3))
print(Solution().countAndSay(4))

执行用时：68 ms, 在所有 Python3 提交中击败了17.13%的用户

内存消耗：14.9 MB, 在所有 Python3 提交中击败了5.17%的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# author：sarizzm time:2020/12/31 0031


# 递归求解

class Solution:
    def countAndSay(self, n):
        if n == 1:
            return '1'
        start_str = self.countAndSay(n-1)
        num = 0
        result = ''
        for j in range(len(start_str)):
            num += 1
            if j< len(start_str)-1 and start_str[j] == start_str[j+1]:
                continue
            else: # 当start_str[j] ！= start_str[j+1] 或者j=len(start_str)-1时，num肯定也是为1的
                result = result + str(num) + start_str[j]
                num = 0

        return result


# print(Solution().countAndSay(0))
print(Solution().countAndSay(1))
print(Solution().countAndSay(2))
print(Solution().countAndSay(3))
print(Solution().countAndSay(4))

执行用时：64 ms, 在所有 Python3 提交中击败了26.71%的用户

内存消耗：14.6 MB, 在所有 Python3 提交中击败了16.97%的用户

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) {
        if (n == 1){
            return "1";
        }
        int cnt = 1;
        String pre = countAndSay(n - 1);
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < pre.length(); i++){
            if (i < pre.length() - 1 && pre.charAt(i) == pre.charAt(i + 1)){
                cnt++;
            }else{
                res.append(cnt).append(pre.charAt(i));
                cnt = 1;
            }
        }
        return res.toString();
    }
}

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public String countAndSay(int n) {
        // 递归终止条件
        if (n == 1) {
            return "1";
        }
        StringBuffer res = new StringBuffer();
        // 拿到上一层的字符串
        String str = countAndSay(n - 1);
        int length = str.length();
        // 开始指针为0
        int start = 0;
        // 注意这从起始条件要和下面长度统一
        for (int i = 1; i < length + 1; i++) {
            // 字符串最后一位直接拼接
            if (i == length) {
                res.append(i - start).append(str.charAt(start));
            // 直到start位的字符串和i位的字符串不同，拼接并更新start位
            } else if (str.charAt(i) != str.charAt(start) ) {
                res.append(i - start).append(str.charAt(start));
                start = i;
            }
        }
        return res.toString();
    }
}

//作者：ruo-guang
//链接：https://leetcode-cn.com/problems/count-and-say/solution/1-ms-zai-suo-you-java-ti-jiao-zhong-ji-bai-liao-97/