leetcode.38 ---外观数列

外观数列

题解：

动图演示：

代码如下:

class Solution {
    
public:
    string countAndSay(int n) {
    
        string res = "1";
        if(n == 1) return res;//n=1直接返回
        for(int i = 1;i < n;i++){
    
            string tmp;
           int l = 0, r = 0;//双指针找重复元素
           while(r < res.size()){
         
               while(r < res.size() && res[r] == res[l]) r++;//相等r就一直往右走
               tmp += to_string(r - l) + res[l]; //拼接起来
               l = r;//更新l到r的位置
           }
          res = tmp;
        }
        return res;
    }
};

时间复杂度:O(n^2)
空间复杂度;O(1)