點擊關註上方「圖解面試算法」,
設為「置頂或星標」,一起刷 LeetCode。
作者:孤磊
題目來源於 LeetCode 上第 38 號問題:外觀數列。題目難度為 Easy。題目描述「外觀數列」是一個整數序列,從數字 1 開始,序列中的每一項都是對前一項的描述。前五項如下:1. 1
2. 11
3. 21
4. 1211
5. 111221
1 被讀作 "one 1" ("一個一") , 即 11。11 被讀作 "two 1s" ("兩個一"), 即 21。21 被讀作 "one 2", "one 1" ("一個二" , "一個一") , 即 1211。給定一個正整數 n(1 ≤ n ≤ 30),輸出外觀數列的第 n 項。輸入: 4
輸出: "1211"
解釋:當 n = 3 時,序列是 "21",其中我們有 "2" 和 "1" 兩組,"2" 可以讀作 "12",也就是出現頻次 = 1 而 值 = 2;類似 "1" 可以讀作 "11"。所以答案是 "12" 和 "11" 組合在一起,也就是 "1211"。
題目解析送迭法:當 n = 1 的時候序列為 1,n = 2的時候為 11,每一個數字對應的都是固定的,都是根據上個數字計算而來的結果。那這樣就可以利用送迭法來進行每一輪的計算,完成後將結果傳遞到下一輪計算過程。直到符合 n 的條件為止。動畫描述代碼實現// 38. 外觀數列
// https://leetcode-cn.com/problems/count-and-say
// 時間複雜度:O(n)
// 空間複雜度:O(1)
class Solution {
public String countAndSay(int n) {
String re;
re=digui(2,n,"1");
return re;
}
private String digui(int i ,int n,String str){
if (i>n){
return str;
}
StringBuilder stringBuilder=new StringBuilder();
char c=0;
int num=0;
for (char ch:str.toCharArray()) {
if (ch!=c){
char t= (char) (num+'0');
stringBuilder.append(t);
num=0;
stringBuilder.append(c);
}
c=ch;
num++;
}
stringBuilder.append((char)(num+'0'));
stringBuilder.append(c);
stringBuilder.delete(0,2);
String s=digui(i+1,n,stringBuilder.toString());
return s;
}
}
複雜度分析