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