报数

题意

报数指的是,按照其中的整数的顺序进行报数,然后得到下一个数。如下所示:

1, 11, 21, 1211, 111221, ...

1 读作 "one 1" -> 11.

11 读作 "two 1s" -> 21.

21 读作 "one 2, then one 1" -> 1211.

给定一个整数 n, 返回 第 n 个顺序。

样例

给定 n = 5, 返回 "111221".

思路

这道题的题意不太容易理解,提示是: n = 1 时输出字符串 1,n = 2 时由于上次字符串为 1,所以记作一个 1,也就是输出 11,n = 3 时,由于上一个输出是 11,记作两个 1,输出 21。以此类推……,有点类似于 斐波那契数列

题意理解后就容易做了,可以用递归法或循环即可。

代码实现

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
public class Solution {

/*
* @param n: the nth
* @return: the nth sequence
*/
//递归法
public String countAndSay(int n) {
String str = "1";

while (--n > 0) {
StringBuilder sb = new StringBuilder();
char[] c = str.toCharArray();

for (int i = 0; i < c.length; i++) {
int count = 1;
while ((i + 1) < c.length && c[i] == c[i + 1]) {
count++;
i++;
}
sb.append(String.valueOf(count) + String.valueOf(c[i]));
}
str = sb.toString();
}
return str;
}
};

原题地址

LintCode:报数