给定一个正整数 n ,输出外观数列的第 n 项。
「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列:
前五项如下:
1. 1
2. 11
3. 21
4. 1211
5. 111221
第一项是数字 1
描述前一项,这个数是 1 即 “ 一 个 1 ”,记作 "11"
描述前一项,这个数是 11 即 “ 二 个 1 ” ,记作 "21"
描述前一项,这个数是 21 即 “ 一 个 2 + 一 个 1 ” ,记作 "1211"
描述前一项,这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ,记作 "111221"
要 描述 一个数字字符串,首先要将字符串分割为 最小 数量的组,每个组都由连续的最多 相同字符 组成。然后对于每个组,先描述字符的数量,然后描述字符,形成一个描述组。要将描述转换为数字字符串,先将每组中的字符数量用数字替换,再将所有描述组连接起来。
例如,数字字符串 "3322251" 的描述如下图:
示例 1:
输入:n = 1
输出:"1"
解释:这是一个基本样例。
示例 2:
输入:n = 4
输出:"1211"
解释:
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
提示:
1 <= n <= 30
这是一道模拟题。
我们可以实现一个 nextString
方法,传入一个字符串 s
,返回该字符串对应的外观数列。
具体的实现,我们只需要统计字符串 s
中每一段连续出现的字符的类型和出现次数即可:
class Solution {
public String countAndSay(int n) {
String s = "1";
for (int i = 2; i <= n; i++) {
s = nextString(s);
}
return s;
}
String nextString(String s) {
StringBuilder sb = new StringBuilder();
int n = s.length();
char[] cs = s.toCharArray();
char c = cs[0];
int cnt = 1;
for (int i = 1; i < n; i++) {
char cur = cs[i];
if (cur == c) {
cnt++;
} else {
sb.append(cnt);
sb.append(c);
c = cur;
cnt = 1;
}
}
sb.append(cnt);
sb.append(c);
return sb.toString();
}
}
n
次,复杂度为 ;每次循环处理一遍当前的 s
字符串,复杂度为
。整体复杂度为
。
之前三叶在不少的链表题中为你介绍过「哨兵技巧」,例如 【刷穿 LeetCode】24. 两两交换链表中的节点(中等) 。
但是「哨兵」可不是只能应用在链表题上,「哨兵」的本质是帮助我们简化边界的判断。
例如我们上述解法中,就可以使用「哨兵技巧」来简化我们统计的逻辑,避免在循环外统计最后一次字符:
class Solution {
public String countAndSay(int n) {
String s = "1";
for (int i = 2; i <= n; i++) {
s = nextString(s);
}
return s;
}
String nextString(String s) {
// 往结尾添加一个“哨兵”
s = s + "a";
StringBuilder sb = new StringBuilder();
int n = s.length();
char[] cs = s.toCharArray();
char c = cs[0];
int cnt = 1;
for (int i = 1; i < n; i++) {
char cur = cs[i];
if (cur == c) {
cnt++;
} else {
sb.append(cnt);
sb.append(c);
c = cur;
cnt = 1;
}
}
return sb.toString();
}
}
n
次,复杂度为 ;每次循环处理一遍当前的 s
字符串,复杂度为
。整体复杂度为
。
这是我们「刷穿 LeetCode」系列文章的第 No.38
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加,为了方便我们统计进度,我们将按照系列起始时的总题数作为分母,完成的题目作为分子,进行进度计算。当前进度为 38/1916
。
为了方便各位同学能够电脑上进行调试和提交代码,我在 Github 建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。