题目

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, 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次即可。

实现

class Solution {
public:
    string countAndSay(int n) {
        string input, output="1";
        n--;
        while(n--){
            input = output;
            output.clear();
            int i=0;
            while(i<input.size()){
                int count=1;
                char ch=input[i];
                while(i+1<input.size() && input[i+1]==ch){
                    count++;
                    i++;
                }
                output += count + '0';
                output += ch;
                i++;
            }
        }
        return output;
    }
};

思考

有趣的一点是，对于string类型来说，使用+操作符就比使用push_back()函数快了不少。