leetcode解题: Count and Say (38)

发表于 | 分类于

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 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, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

解法1： Recursive

用递归求得n-1的字符串，然后一位位遍历，每当得到和前一位不一样的字符时，保存前一位的字符的计数和字符。要注意的是最后一位的结果要在扫描结束后保存。
C++
C++ 里 从1个char转换到string可以用string(1, character)

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
class Solution {
public:
    string countAndSay(int n) {
        if (n <= 0) {
            return "";
        }
        if (n == 1) {
            return "1";
        }
        
        string prev = countAndSay(n - 1);
        string res = "";
        int count = 1;
        char cur = prev[0];
        for (int i = 1; i < prev.size(); ++i) {
            if (prev[i] == prev[i - 1]) {
                count++;
            } else {
                res += to_string(count) + string(1, cur);
                cur = prev[i];
                count = 1;
            }
        }
        res += to_string(count) + string(1, prev[prev.size() - 1]);
        return res;
    }
};

Java

1