38. 外觀數列
給定一個正整數 n ，輸出外觀數列的第 n 項。
「外觀數列」是一個整數序列，從數字 1 開始，序列中的每一項都是對前一項的描述。
你可以將其視作是由遞歸公式定義的數字字符串序列：
- countAndSay(1) = “1”
- countAndSay(n) 是對 countAndSay(n-1) 的描述，然后轉換成另一個數字字符串。
前五項如下：
-
1 -
11 -
21 -
1211 -
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
解題思路
由遞歸公式定義的數字字符串序列：
- countAndSay(1) = “1”
- countAndSay(n) 是對 countAndSay(n-1) 的描述
對countAndSay(n-1) 的描述本質上就是解析字符串，獲取字符串中連續字符的出現的次數，將字符出現次數和字符組成新的字符串，使用遞歸的方法，不斷地對下一層返回的字符串進行解析，直到到達遞歸邊界1.
代碼
class Solution {public String countAndSay(int n) {return n==1?"1":parse(countAndSay(n-1));}public String parse(String n) {char pre=n.charAt(0);int cnt=1;StringBuilder sb = new StringBuilder();for (int i=1;i<n.length();i++){if (n.charAt(i)==pre)cnt++;else {sb.append(cnt).append(pre);pre=n.charAt(i);cnt=1;}}sb.append(cnt).append(pre);return sb.toString();}}
)
