[LeetCode] 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.

思路：

逐个构建序列——根据第i-1个序列构建后第i个。理解题目意思后便知道在扫描前一个序列ret时，需要一个计数变量count记录当前字符重复的次数，以及需要一个字符变量prev记录上一个字符的值。当ret[i] = prev，则先不写入结果，而增加count。当ret[i] != prev时，说明prev的重复结束，需要将count和prev都写入结果，然后重置count为1，prev为ret[i]。

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 26

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

事实上可以证明count不会超过4，所以这里的to_string(count)改成'0'+count也可以：
https://oj.leetcode.com/discuss/6762/how-to-proof-the-count-is-always-less-than-10