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"。
代码如下：
|
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
27
28
29
30
31
32
33
34
35
36
|
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
本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1836606
