問題

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.

例子

5
111221

分析

統(tǒng)計字符串的連續(xù)重復(fù)字符

要點

盡量迭代，不用遞歸

時間復(fù)雜度

O(n^2) n次迭代，每次迭代的結(jié)果字符串的長度呈線性增長。

空間復(fù)雜度

O(1)

代碼

class Solution {
public:
    string countAndSay(int n) {
        string res("1");
        for (int i = 0; i < n - 1; i++)
            res = say(res);
        return res;
    }
    
private:
    string say(const string &str) {
        string res;
        char c = str[0];
        int cnt = 1;
        for (int i = 1; i < str.size(); i++) {
            if (str[i] == c) cnt++;
            else {
                res += to_string(cnt) + string(1, c);
                c = str[i];
                cnt = 1;
            }
        }
        res += to_string(cnt) + string(1, c);
        return res;
    }
};