题目链接：Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:

1, 11, 21, 1211, 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 sequence.

Note: The sequence of integers will be represented as a string.

这道题的要求是数数并记录，生成序列中第n个字符串。

这道题算就是字符串处理的问题，序列中第一个字符串是“1”，接下来依次统计前一个字符串中连续相同字符的数量，并添加到下一字符串中。前15字符串如下（LeetCode上貌似只有18测试用例）：

  1. 1
  2. 11
  3. 21
  4. 1211
  5. 111221
  6. 312211
  7. 13112221
  8. 1113213211
  9. 31131211131221
  10. 13211311123113112211
  11. 11131221133112132113212221
  12. 3113112221232112111312211312113211
  13. 1321132132111213122112311311222113111221131221
  14. 11131221131211131231121113112221121321132132211331222113112211
  15. 311311222113111231131112132112311321322112111312211312111322212311322113212221

时间复杂度：O(???)

空间复杂度：O(n)（结果字符串长度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution
{
public:
    string countAndSay(int n)
    {
        string s = "1";
        for(int i = 1; i < n; ++ i)
        {
            int count = 1;
            string temp = "";
            for(int j = 1; j < s.size(); ++ j)
            {
                if(s[j] == s[j - 1])
                    ++ count;
                else
                {
                    temp = temp + (char)(count + '0') + s[j - 1];
                    count = 1;
                }
            }
            s = temp + (char)(count + '0') + s[s.size() - 1];
        }
        return s;
    }
};

或者

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution
{
public:
    string countAndSay(int n)
    {
        string s = "1";
        for(int i = 1; i < n; ++ i)
        {
            string temp = "";
            for(int j = 0, count; j < s.size(); ++ j)
            {
                for(count = 1; j < s.size() && s[j] == s[j + 1]; ++ j, ++ count);
                temp = temp + (char)(count + '0') + s[j];
            }
            s = temp;
        }
        return s;
    }
};