[Lc]38外观数列

题目

题解

• 时间复杂度$O(N*M)$
• 空间复杂度$O(M_{end}+M_{end-1})

class Solution {
public:
    string countAndSay(int n) {
        if(n == 0) return "";
        string res = "1";//第一行
        while(--n){//一行一行生成
            string cur = "";//用来保存下一行
            for(int i=0; i<res.size(); ++i){//统计与i处相同的字符数量
                int n = 1;//先计数，n=1，即该处字符的数量只是为1
                //i+1 < res.size()是因为在i为倒数第二个数的时候就已经和i+1处的字符进行比较了，到最后一位就不用比了
                //若相等，则在前一位的时候已经加过了，若不相等，外层循环也会在记一次最后一个字符
                while(i+1 < res.size() && res[i] == res[i+1]){
                    n++;
                    i++;
                }
                cur += to_string(n) + res[i];//cur加上res[i]的数量和res[i]
            }
            res = cur;
        }
        return res;
    }
};