切換
舊版
前往
大廳
主題

LeetCode - 38. Count and Say 解題心得

Not In My Back Yard | 2020-08-03 00:00:06 | 巴幣 0 | 人氣 341

題目連結:


題目意譯:
外觀數列(Count-and-say Sequence)是一個整數數列,前五項為下列:
1.     1
2.     11
3.     21
4.     1211
5.     111221
1 讀作為「1 個 1」或是 11;
11 讀作為 「2 個 1」 或是 21;
21 讀作為 「1 個 2,接著 1 個 1」或是 1211。

給定一整數 n (1 ≦ n ≦ 30),請生成外觀數列的第 n 項。可以遞迴的方式去做,也就是說從前一項去「讀出來」,去數連續的數字之個數。

注:整數數列的每一項須各自以一個字串來表示。



範例測資:
範例 1:
輸入: 1
輸出: "1"
解釋: 這是基礎條件。

範例 2:
輸入: 4
輸出: "1211"
解釋: n = 3 的項為「21」,在此我們有兩個數組,一個是「2」、一個是「1」。「2」可讀作「12」,代表頻率 = 1 、 值 = 2 ;同樣地,「1」可讀作「11」。因此,答案為「12」與「11」的合併,即「1211」。


解題思維:
以字串 S = 「1」作為開頭,重複以下步驟 n - 1 次,即可得到所求:

對於一個數字字串 S ,數其連續的相同數字之連續長度(數連續數字的方式,如這題),將該長度之值轉為字串並接著那個被重複的數字。接著把每組連續數字產生的字串全部接在一起,將其作為 S 的新值,並迭代下去。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作