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
| class Solution {
public String countAndSay(int n) {
if (n == 1) {
return "1";
}
StringBuilder lastSay = new StringBuilder("1");
for (int i = 2; i <= n; i++) {
lastSay = getCurrSay(lastSay);
}
return lastSay.toString();
}
private StringBuilder getCurrSay(StringBuilder lastSay) {
int count = 1;
lastSay.append('*');
StringBuilder sb = new StringBuilder();
for (int i = 0; i < lastSay.length() - 1; i++) {
if (lastSay.charAt(i) == lastSay.charAt(i + 1)) {
count += 1;
} else {
sb.append(count).append(lastSay.charAt(i));
count = 1;
}
}
return sb;
}
}
|
主要是这个问题描述有点儿迷.
1的count say是1, 这是base case.
2的话看1的count say是啥, 1是1, 那么就是1个1, 因此2的count say是1(个)1, 合在一起就是11.
3的话看2, 2是11, 那就是2个1, 因此是2(个)1, 合在一起就是21.
4的话看3, 3是21, 那就是1个2, 1个1; 因此是1(个)2 1(个)1 合在一起就是1211.
也就是连续出现的数字可以合在一起说. 单独的数字就单独说.
时间复杂度和空间复杂度不知道咋分析.
