文章目录

• 1、描述
• 2、关键字
• 3、思路
• 4、notes
• 5、复杂度
• 6、code

1、描述

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：

1. 1
   

2. 11
   

3. 21
   

4. 1211
   

5. 111221
   

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2、关键字

描述

3、思路

一个一个的生成

4、notes

题意读懂，不是把这个n给描述出来，而是经过n次描述，第n行的字符串

5、复杂度

时间：O（N X M) N是数组给定正整数，M是字符串最大长度

空间：O(M）字符串最大长度

6、code

class Solution {
public:
    string countAndSay(int n) {
        string prev = "1";  // 第一行
        for(int i = 2; i <= n; i++){  // 剩下 2 ----> n  行
            string curr= "";  // 当前行初始化， 根据上一行进行初始化
            int start = 0, pos = 0;
            while(pos < prev.size()){  // 遍历 上一行，
                while(pos < prev.size() && prev[pos] == prev[start]){ // 遇到相等 直接往后
                    pos++;
                }
                curr += to_string(pos - start) + prev[start];  // 把这一段相等的加进来。
                start = pos;  // 重置初始位置
            }
            prev = curr;  // 进入下一行之前，把当前行 --> 更新成“上一行”
        }
        return prev;
    }
};