Type：easy
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 nwhere 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:1Output:"1"
Example 2:
Input:4Output:"1211"
如上解释所示，第一个数为1，第二个数读第一个数为1个1（11），第三个数读第二个数为2个1（21），第四个数读第三个数1个2、1个1（1211），第五个数读第四个数1个1、1个2、2个1（111221），以此类推。
根据上述情报，我们可以知道，一个数字连续显示的个数不会超过3，若超过3，例如22111122，说明上一个数是2个2、1个1、1个1、2个2，即221122，则下一个应写作222122,。因此矛盾。
显然本题应使用递归法，返回一个string。countAndSay(n)获取countAndSay(n-1)返回的string，遍历这个string，比较str[i]与str[i+1]是否相等，用count记录str[i]出现的次数，当匹配到不相等的str[i+1]，输出的字符串s加上to_string(count)再加上str[i]。由于最后一个字符及个数未输出，最后还要输出to_string(count)及str.back()。
class Solution {
public:
string countAndSay(int n) {
if(n == 1) return "1";
string str;
str = countAndSay(n-1);
int count = 1;
int l = str.length();
string s = "";
for(int i=0; i<l-1; i++){
if(str[i] == str[i+1]) count++;
else {
s = s + to_string(count) + str[i];
count = 1;
}
}
s = s + to_string(count) + str.back();
return s;
}
};
