每日一道 LeetCode (11)：外观数列
共 1885字，需浏览 4分钟
·
2020-08-07 19:53
❝每天 3 分钟，走上算法的逆袭之路。
❞
前文合集
代码仓库
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
题目：外观数列
题目来源：https://leetcode-cn.com/problems/count-and-say/
给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 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
示例 1:
输入: 1
输出: "1"
解释：这是一个基本样例。
示例 2:
输入: 4
输出: "1211"
解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组，"2" 可以读作 "12"，也就是出现频次 = 1 而 值 = 2；类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起，也就是 "1211"。
解题思路
今天下班回来太晚了，我就简单写写，有不理解的再私信问我吧。
首先帮忙理解下这道题，这道题的意思实际上就是按照一种规律来进行描述数字。
按照正常人的思路，这个算法首先需要一个大循环，直接循环到 n ，然后在每一次循环中得到上一次结果的新的描述。
最开始第一次是 1 ， 这个是规定。 第二次循环是描述上一个数字，结果是 11 ，意思是上一个数字是 1 个 1 。 第三次循环上描述上一次的 11 ，结果是 21 ，含义是 2 个 1 。 第四次循环还是描述上一次的 21 ，结果是 1211 ，含义是 1 个 2 ， 1 个 1 。 ......
后面的我就不写了，这道题就先拆解到这里，确实蛮难理解的，说实话，我看题是没看懂的，直到我看到了答案分析了代码后才看懂题。
我这是真的菜的一批。
解题
首先声明，这道题我没有想出来任何解法，所有解法均来自于 LeetCode 的网友。
最皮的解法
第一个我一定要介绍这个解法，因为这个题给出的数字是有限的，所以有一个非常皮的网友直接给了这么一串代码，看的我是目瞪口呆：
public String countAndSay(int n) {
switch (n) {
case 1:
return "1";
case 2:
return "11";
case 3:
return "21";
case 4:
return "1211";
case 5:
return "111221";
case 6:
return "312211";
case 7:
// 中简代码省略，太长了
...
default:
return "0";
}
}
这位同学抓住了这道题的输入是有限制的，直接把所有的结果穷举出来，然后用了一波 switch ，我是真的服。
果然刷 LeetCode 题的人的脑回路和正常人完全不同。
常规迭代解法
对于题还没理解清楚的同学可以多 debug 几次下面这段代码，这种方案是一个人的常规正向的思维过程。
public static String countAndSay(int n) {
if ( n == 1 ) return "1";
String s_n_1 = "1";
// 首先外层先循环到 n ，从 2 开始。
for ( int i = 2; i <= n; i++ ) {
StringBuilder sb = new StringBuilder();
int pre = 0;// 前驱节点
int j = 0;
// 开始描述上一次得到的数字
for ( j = 0; j < s_n_1.length(); j++ ) {
if ( s_n_1.charAt(j)!=s_n_1.charAt(pre) ){
sb.append(j-pre).append(s_n_1.charAt(pre));
pre = j;
}
}
sb.append(j-pre).append(s_n_1.charAt(pre));
s_n_1 = sb.toString();
}
return s_n_1;
}
不好写的递归方案
递归讲道理我还是不大会写，硬着头皮先抄一遍代码吧。
public String countAndSay_1(int n) {
if (n == 1) return "1";
StringBuilder res = new StringBuilder();
String str = countAndSay_1(n - 1);
int length = str.length();
int a = 0;
for (int i = 1; i < length + 1; i++) {
if (i == length) {
return res.append(i - a).append(str.charAt(a)).toString();
} else if (str.charAt(i) != str.charAt(a) ) {
res.append(i - a).append(str.charAt(a));
a = i;
}
}
return res.toString();
}
先这样，今天晚上时间比较紧，写的内容不多，还望各位看到这篇文章的同学海涵，明天我一定找补回来。
