LeetCode 38 - Count and Say

作者 QIFAN 日期 2017-06-06
LeetCode 38 - Count and Say

原题链接: https://leetcode.com/problems/count-and-say/#/description


很久没刷题了,重新开始练练手感。

题干

有这样一串数列。
1, 11, 21, 1211, 111221, ...
规律是“数数并读出来”
1 读作 “1 个 1” ,写成 11
11 读作 “2 个 1”, 写成 21
21 读作 “1 个 2 和 1 个 1” ,写成 1211
以此类推。

给出一个整型 n ,求该数列第 n 个数。

思路

简单的找规律题,写起来还是有一些麻烦。

有三层循环。最里层:数连续相同数字;第二层:遍历第 n - 1 个数来数数;最外层:算 n 个数。

时间复杂度所有数字的长度和(因为要遍历每一个数字)

代码:

public String countAndSay(int n) {
String res = "1";
if (n <= 1) {
return res;
}
for (int i = 2; i <= n; i++) {
String newres = "";
char last;
int count, j = 0;
while (j < res.length()) {
last = res.charAt(j);
count = 1;
while (j + count < res.length() && res.charAt(j + count) == last) {
count++;
}
newres += count + "" + last;
j = j + count;
}
res = newres;
}
return res;
}