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

Diffculty
Easy

Similar Problems
[LeetCode ] Encode and Decode Strings Medium

Analysis

思路：

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

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

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

// string-operation. The only trick thing is Line11. seq[seq.size()] always '\0'. // It will help to save an "if" statement. string countAndSay(int n){ string seq = "1"; int k = 1; while(k < n){ stringstream newSeq; char last = seq[0]; int count = 0; for(int i = 0; i <= seq.size(); i++){ if(seq[i] ==last){ ++count; } else{ newSeq << count << last; last = seq[i]; count = 1; } } seq = newSeq.str(); k++; } return seq; }