每日一道 LeetCode (11)：外觀數(shù)列
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉(cāng)庫(kù)
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：外觀數(shù)列
題目來源：https://leetcode-cn.com/problems/count-and-say/
給定一個(gè)正整數(shù) n（1 ≤ n ≤ 30），輸出外觀數(shù)列的第 n 項(xiàng)。
注意：整數(shù)序列中的每一項(xiàng)將表示為一個(gè)字符串。
「外觀數(shù)列」是一個(gè)整數(shù)序列，從數(shù)字 1 開始，序列中的每一項(xiàng)都是對(duì)前一項(xiàng)的描述。前五項(xiàng)如下：
1.?????1
2.?????11
3.?????21
4.?????1211
5.?????111221
第一項(xiàng)是數(shù)字 1
描述前一項(xiàng)，這個(gè)數(shù)是 1 即 “一個(gè) 1 ”，記作 11
描述前一項(xiàng)，這個(gè)數(shù)是 11 即 “兩個(gè) 1 ” ，記作 21
描述前一項(xiàng)，這個(gè)數(shù)是 21 即 “一個(gè) 2 一個(gè) 1 ” ，記作 1211
描述前一項(xiàng)，這個(gè)數(shù)是 1211 即 “一個(gè) 1 一個(gè) 2 兩個(gè) 1 ” ，記作 111221
示例 1:
輸入:?1
輸出:?"1"
解釋：這是一個(gè)基本樣例。
示例 2:
輸入:?4
輸出:?"1211"
解釋：當(dāng) n = 3 時(shí)，序列是?"21"，其中我們有?"2"?和?"1"?兩組，"2"?可以讀作?"12"，也就是出現(xiàn)頻次?= 1 而?值?= 2；類似?"1"?可以讀作?"11"。所以答案是?"12"?和?"11"?組合在一起，也就是?"1211"。
解題思路
今天下班回來太晚了，我就簡(jiǎn)單寫寫，有不理解的再私信問我吧。
首先幫忙理解下這道題，這道題的意思實(shí)際上就是按照一種規(guī)律來進(jìn)行描述數(shù)字。
按照正常人的思路，這個(gè)算法首先需要一個(gè)大循環(huán)，直接循環(huán)到 n ，然后在每一次循環(huán)中得到上一次結(jié)果的新的描述。
最開始第一次是 1 ， 這個(gè)是規(guī)定。 第二次循環(huán)是描述上一個(gè)數(shù)字，結(jié)果是 11 ，意思是上一個(gè)數(shù)字是 1 個(gè) 1 。 第三次循環(huán)上描述上一次的 11 ，結(jié)果是 21 ，含義是 2 個(gè) 1 。 第四次循環(huán)還是描述上一次的 21 ，結(jié)果是 1211 ，含義是 1 個(gè) 2 ， 1 個(gè) 1 。 ......
后面的我就不寫了，這道題就先拆解到這里，確實(shí)蠻難理解的，說實(shí)話，我看題是沒看懂的，直到我看到了答案分析了代碼后才看懂題。
我這是真的菜的一批。
解題
首先聲明，這道題我沒有想出來任何解法，所有解法均來自于 LeetCode 的網(wǎng)友。
最皮的解法
第一個(gè)我一定要介紹這個(gè)解法，因?yàn)檫@個(gè)題給出的數(shù)字是有限的，所以有一個(gè)非常皮的網(wǎng)友直接給了這么一串代碼，看的我是目瞪口呆：
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:
????????//?中簡(jiǎn)代碼省略，太長(zhǎng)了
????????...
????????default:
????????????return?"0";
????}
}
這位同學(xué)抓住了這道題的輸入是有限制的，直接把所有的結(jié)果窮舉出來，然后用了一波 switch ，我是真的服。
果然刷 LeetCode 題的人的腦回路和正常人完全不同。
常規(guī)迭代解法
對(duì)于題還沒理解清楚的同學(xué)可以多 debug 幾次下面這段代碼，這種方案是一個(gè)人的常規(guī)正向的思維過程。
public?static?String?countAndSay(int?n)?{
????if?(?n?==?1?)?return?"1";
????String?s_n_1?=?"1";
????//?首先外層先循環(huán)到 n ，從 2 開始。
????for?(?int?i?=?2;?i?<=?n;?i++?)?{
????????StringBuilder?sb?=?new?StringBuilder();
????????int?pre?=?0;//?前驅(qū)節(jié)點(diǎn)
????????int?j?=?0;
????????//?開始描述上一次得到的數(shù)字
????????for?(?j?=?0;?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;
}
不好寫的遞歸方案
遞歸講道理我還是不大會(huì)寫，硬著頭皮先抄一遍代碼吧。
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?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();
}
先這樣，今天晚上時(shí)間比較緊，寫的內(nèi)容不多，還望各位看到這篇文章的同學(xué)海涵，明天我一定找補(bǔ)回來。
