4.1　外觀數列（報數）

題目描述（第38題）

外觀數列是一個整數序列，從數字1開始，序列中的每一項都是對前一項的描述。前5項如下。

1 被讀作“one 1”(一個一)，即11。

11 被讀作“two 1s”（兩個一），即21。

21 被讀作“one 2，one 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”。

解法一　迭代法

思路

這道題目的英文標題為count and say，直譯過來是計算并報數，與外觀數列的描述相比，作者認為前者要形象許多。這是一種并不復雜的報數游戲，根據題意，11被讀作“two 1s”(兩個一），即21；21被讀作“one 2，one 1”（一個二，一個一)，即1211，每次報數產生的新的字符串由原字符串的每個字符及其計數拼接構成。

從1到n的過程需要逐次報數，每次報數又需要從頭到尾遍歷上一次報數的結果，因此在這里使用雙重循環是順理成章的。

●　內層循環實現報數，即字符拼接過程。遍歷數列，使用變量current_char和char_count記錄正在報數的數字和出現次數。

?　如果當前數字和正在記錄的數字一致，增加計數。

?　否則就進行一次報數，即將被記錄數字和出現次數拼接在臨時結果序列tmp中，同時將記錄的數字替換為當前數字，將計數設置為1。

●　外層循環負責為下一次報數提供新的數列，并進行中間變量的初始化。

?　初始化tmp、current_char、char_count，并在內層循環結束時為末尾的數字進行一次報數。

?　將結果記錄到ans中。

?　循環的最后一輪，被保存的結果就是我們需要的答案。

代碼

復雜度分析

●　時間復雜度：計算規模隨著迭代次數n及每次計算得到的字符串長度的變大而變大，因此時間復雜度為O(mn)，m為最后一次計算時的字符串長度。

●　空間復雜度：O(m)，m為最后一次計算時的字符串長度。

解法二　遞歸法

下面換一種思路，先不考慮具體如何報數，從1到n的數列產生邏輯很好地體現了遞歸思想。假設報數，即字符的拼接過程為函數do_string，我們可以很快得到遞歸解法的雛形。

剩下要做的無非是實現字符拼接邏輯do_string：依照題意遍歷字符串，以當前記錄中的字符為基準，遇到相同字符時記錄字符個數；遇到不同的字符時打印計數和字符，并替換記錄的字符；繼續遍歷直至末尾。

與前面已經列出的遞歸框架結合，我們可以很快地完成這道題目的解答。

代碼

復雜度分析

●　遞歸次數隨著輸入值n的增加而增加，每次計算的規模隨著字符串previous_string的變長而變大，因此時間復雜度為O(mn)，m為最后一次計算的字符串長度。

●　空間復雜度：由于使用了遞歸，遞歸函數的參數n每次減少1，因此空間復雜度為O(n+m)，m為最后一次計算時的字符串長度。