38. Count and Say

本题来自 LeetCode：38. Count and Say^[1]

题目描述

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.
Note: Each term of the sequence of integers will be represented as a string.
Example 1:

Input: 1
Output: "1"
Explanation: This is the base case.

Example 2:

Input: 4
Output: "1211"
Explanation: For n = 3 the term was "21" in which we have two groups "2" and "1", "2" can be read as "12" which means frequency = 1 and value = 2, the same way "1" is read as "11", so the answer is the concatenation of "12" and "11" which is "1211".

题目分析

本题的题意是以 1为起始值，根据一定规则生成一个字符串，递归处理每一轮生成的字符串。规则如下：

第一轮，直接输出`1`;

第二轮，只有`1`个数字`1`，那么输出`11`；

第三轮，有`2`个连续的`1`，那么输出`21`；

第四轮，有`1`个`2`，`1`个`1`，那么按顺序生成的字符串为`12` + `11` = `1211`；

也就是说对字符串的连续相同数字进行计数，按照`数量`+`数字`的顺序连接起来。

题目解答

迭代版

class Solution {
    public String countAndSay(int n) {
        //起始值
        String str = "1";
        for(int i = 1; i  n; i ++) {
            // 存储当前轮次的值
            StringBuilder sb = new StringBuilder();
            int length = str.length();
            // 取上一轮字符串的第一个字符
            char preDigit = str.charAt(0);
            // 对当前数字计数
            int count = 1;
            // 遍历str字符串
            int k = 1;
            while(k  length) {
                // 将连续同等的数字 计数
                while(k  length && preDigit == str.charAt(k)) {
                    count ++;
                    k ++;
                }
                // 若与前一个数字不同，则表示需要重新计数
                if(k  length) {
                    sb.append(count).append(preDigit);
                    count = 1;
                    preDigit = str.charAt(k ++);
                }
            }
            // 当 k == length时
            sb.append(count).append(preDigit);

            str = sb.toString();
        }

        return str;
    }
}

复杂度分析：
时间复杂度： O(n)
空间复杂度： O(n)

递归版

class Solution {
    public String countAndSay(int n) {
        return countAndSay(n - 1, "1");
    }

    public String countAndSay(int n, String str) {
        if(n == 0) {
            return str;
        }
        // 存储当前轮次的值
        StringBuilder sb = new StringBuilder();
        int length = str.length();
        // 取上一轮字符串的第一个字符
        char preDigit = str.charAt(0);
        // 对当前数字计数
        int count = 1;
        // 遍历str字符串
        int k = 1;
        while(k  length) {
            // 将连续同等的数字 计数
            while(k  length && preDigit == str.charAt(k)) {
                count ++;
                k ++;
            }
            // 若与前一个数字不同，则表示需要重新计数
            if(k  length) {
                sb.append(count).append(preDigit);
                count = 1;
                preDigit = str.charAt(k ++);
            }
        }
        // 当 k == length时
        sb.append(count).append(preDigit);

        return countAndSay(n - 1, sb.toString());
    }
}

复杂度分析：
时间复杂度： O(n)
空间复杂度： O(n)

参考资料

38. Count and Say: https://leetcode-cn.com/problems/count-and-say/

原文始发于微信公众号（xiaogan的技术博客）：