leetCode 38. Count and Say 字符串
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.
根据规律可以写出后面的:
1. 1
2. 11
3. 21
4. 1211
5. 111221
6. 312211
7. 13112221
8. 1113213211
9. 31131211131221
10. 13211311123113112211
思路:
1.用2个串来替换存储记录result,tmp。
2.记录当前值n,获取当前值最大连续长度m。
3.tmp串追加"m",再追加"n"。
代码如下:
class Solution { public: string countAndSay(int n) { if (--n < 0) return ""; string result = "1"; string tmp; //临时串 int step = 1;//步长 char cur; //当前元素 while (n) { cur = result[0]; for (int i = 0; i < result.size(); i++) { if ( i+1 < result.size() && result[i] == result[i + 1]) { step++; } else { stringstream stepStream; stepStream << step; string stepStr = stepStream.str(); tmp.append(1,stepStr[0]); tmp.append(1,cur); step = 1; cur = result[i + 1]; } } swap(result, tmp); tmp = ""; n--; } return result; } };
2016-08-10 17:24:26