LeetCode-038：Count and Say

题目：

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     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 where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

 

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

题意：

n=1时，输出“1”；

n=2时，上一个数字的结果是1个1，所以输出“11”；

n=3时，上一个数字的结果是2个1，所以输出“21”；

n=4时，上一个数字的结果是1个2、1个1，所以输出“1211”；

n=5时，上一个数字的结果是1个1、1个2、2个1，所以输出“111221”；

。。。。。。

思路：

没思路，暴力，就是把数字转换成字符串麻烦了点。。。

Code：

class Solution {
public:
    string countAndSay(int n) {
        if(n==1) return "1";
        string s="1";
        for(int i=1;i<n;i++){
            string cur="";
            int m=s.size();
            for (int j=0;j<m;j++){
                int cnt=1;
                while((j+1<m)&&(s[j]==s[j+1])){
                    cnt++;
                    j++;
                }
                cur+=std::to_string(cnt)+s[j];
            }
            s=cur;
            cur.clear();
        }
        return s;
    }
};