38. 外观数列(递规+双指针)

class Solution { public: // string count(string str){ // int nums=1; // string res=""; // for(int i=1;i<str.size();i++){ // if(str[i]==str[i-1]){ // nums++; // } // else{ // res+=(nums+'0'); // res+=str[i-1]; // nums=1; // } // } // res+=(nums+'0'); // res+=str[str.size()-1]; // return res; // } // 双指针 string count(string str){ string res=""; int l=0,r=0; while(l<str.size()){ while(str[r]==str[l]) r++; res+=(r-l +'0'); res+=str[l]; l=r; } return res; } string countAndSay(int n) { // 递规： if(n==1) return "1"; return count(countAndSay(n-1)); // 动态规划 // string dp[n]; // dp[0]="1"; // for(int i=1;i<n;i++){ // dp[i]=count(dp[i-1]); // } // return dp[n-1]; // string dp="1"; // for(int i=1;i<n;i++) // dp=count(dp); // return dp; } };