38. Count and Say 报数

题目链接
tag:

• Easy；

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

• 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"

思路：
  这道计数和读法问题第一次遇到，看似挺复杂，其实仔细一看，算法很简单，题目描述的不是很清楚，其实就是第i+1个字符串是第i个字符串的读法，第一字符串为 “1”，比如第四个字符串是1211，它的读法是 1个1、1个2、2个1，因此第五个字符串是111221。第五个字符串的读法是：3个1、2个2、1个1，因此第六个字符串是312211，代码如下：

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

出于好奇打印出了前12个数字，发现一个很有意思的现象，不管打印到后面多少位，出现的数字只是由1,2和3组成，网上也有人发现了并分析了原因 (http://www.cnblogs.com/TenosDoIt/p/3776356.html)，前十二个数字如下：

1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
1 3 1 1 2 2 2 1
1 1 1 3 2 1 3 2 1 1
3 1 1 3 1 2 1 1 1 3 1 2 2 1
1 3 2 1 1 3 1 1 1 2 3 1 1 3 1 1 2 2 1 1
1 1 1 3 1 2 2 1 1 3 3 1 1 2 1 3 2 1 1 3 2 1 2 2 2 1
3 1 1 3 1 1 2 2 2 1 2 3 2 1 1 2 1 1 1 3 1 2 2 1 1 3 1 2 1 1 3 2 1 1