0. 题目

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. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.
Note: Each term of the sequence of integers will be represented as a string.

Example 1:
Input: 1
Output: "1"
Explanation: This is the base case.

Example 2:
Input: 4
Output: "1211"
Explanation: For n = 3 the term was "21" in which we have two groups "2" and "1", "2" can be read as "12" which means frequency = 1 and value = 2, the same way "1" is read as "11", so the answer is the concatenation of "12" and "11" which is "1211".

1. C++版本

思想，主要采用递归的思想，但是其实存在栈溢出的问题。当n>=30后，容易溢出

    string read(string ori_str) {
        if (ori_str.empty())
            return "";
        string result;
        char prev = ori_str[0];
        int count=0, len = ori_str.size();
        for (int i=0; i<len;) {
             if (prev == ori_str[i]) {
                 count++;
                 i++;
             }
             else {
                 result += to_string(count) + prev;
                 prev = ori_str[i];
                 count = 0;
             }
        }
        result += to_string(count) + prev;
        return result;
    }
    string countAndSay(int n) {
        if (n == 1)
            return "1";
        else 
            return read(countAndSay(n-1));
    }

非递归版本，参考

2. python版本

    def read(self, ori_str):
        if not ori_str:
            return ""
        prev = ori_str[0]
        count, i, result = 0, 0, ''
        length = len(ori_str)
        while (i < length):
            if prev == ori_str[i]:
                i = i+1
                count = count + 1
            else:
                result += str(count) + prev
                prev = ori_str[i]
                count = 0
        result += str(count) + prev
        return result
    
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n == 1:
            return "1"
        else:
            return self.read(self.countAndSay(n-1))