05 August 2008
The count-and-say sequence is the sequence of integers with the first five terms as following:
1
2
3
4
5
1. 1
2. 11
3. 21
4. 1211
5. 111221
1
1
1
"one 1"
1
11
1
11
1
"two 1s"
1
21
1
21
1
"one 2
1
one 1"
1
1211
Given an integer n, generate the nth term of the count-and-say sequence.
Note: Each term of the sequence of integers will be represented as a string.
Example 1:
1
2
Input: 1
Output: "1"
Example 2:
1
2
Input: 4
Output: "1211"
对于前一个数，找出相同元素的个数，把这个“个数”和该元素存到新的string里面， 字符串中永远只会出现1,2,3这三个字符，假设第k个字符串中出现了4，那么第k-1个字符串必定有四个相同的字符连续出现，假设这个字符为1，则第k-1个字符串为x1111y。第k-1个字符串是第k-2个字符串的读法，即第k-2个字符串可以读为“x个1,1个1,1个y” 或者“*个x,1个1,1个1,y个*”，这两种读法分别可以合并成“x+1个1,1个y” 和 “*个x，2个1，y个*”，代表的字符串分别是“(x+1)11y” 和 “x21y”，即k-1个字符串为“(x+1)11y” 或 “x21y”，不可能为“x1111y”。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public String countAndSay(int n) {
if (n <= 0) {
return "";
}
String result = "1";//如果不为空，至少是1
while (--n > 0) {
String cur = "";
for (int i = 0; i < result.length(); i++) {//遍历result每个字符
int count = 1;
while (i + 1 < result.length() && result.charAt(i) == result.charAt(i + 1)) {//数一下总共有几个相同的字符，可以一起说
count++;
i++;
}
cur = cur + count + result.charAt(i);
}
result = cur;
}
return result;
}
}