LeetCode 圖解 | 38. 外觀數列

2021-02-20 五分鐘學算法

點擊關註上方「圖解面試算法」,

設為「置頂或星標」,一起刷 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;
    }
}

複雜度分析

相關焦點

  • LeetCode-38.外觀數列(Count and Say)
    38. 外觀數列給定一個正整數 n(1 ≤ n ≤ 30),輸出外觀數列的第 n 項。
  • LeetCode刷題第三周【數組(簡單)】
    斐波那契數(難度:簡單)Oct.31 題目要求:斐波那契數,通常用 F(n) 表示,形成的序列稱為斐波那契數列。該數列由 0 和 1 開始,後面的每一項數字都是前面兩項數字的和。也就是:F(0) = 0,   F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.給定 N,計算 F(N)。
  • 每天一道leetcode234-回文鍊表
    正當班主任要繼續發話,只聽到角落默默想起來一個聲音:」K2」前言 2018.11.6號打卡明天的題目:https://leetcode-cn.com/problems/remove-linked-list-elements/以後明天的題目提取公布一下哈,因為有些朋友想提前做一下~題目 leetcode234-回文鍊表中文連結:https
  • 每天一道leetcode56-合併區間
    正當班主任要繼續發話,只聽到角落默默想起來一個聲音:」K2」前言 2018.11.13號打卡明天的題目:https://leetcode-cn.com/problems/minimum-path-sum/descrip題目 每天一道leetcode56
  • 【數列和級數】圖解普林斯頓微積分 16
    數列的收斂和發散;兩個重要數列;數列極限和函數極限之間的聯繫;級數的收斂與發散, 以及幾何級數的斂散性討論;級數的第n 項判別法;級數和反常積分的聯繫;22.1 數列的收斂和發散(Convergence and Divergence of Sequences)數列是一列有序的數, 可能是有限項, 也可能有無窮項, 其中有無窮項的數列叫作
  • leetcode雞蛋掉落問題(egg drop)
    搜索後發現是leetcode上的一道經典面試題~因為過於經典,已經被踢出google面試題庫了(。)那我們就直接看看leetcode上的題目叭!leetcode現在有中文站,看起來更方便了:https://leetcode-cn.com/problems/super-egg-drop/solution/--你將獲得 K 個雞蛋,並可以使用一棟從 1 到 N  共有 N 層樓的建築。每個蛋的功能都是一樣的,如果一個蛋碎了,你就不能再把它掉下去。
  • 給大家圖解一款雲度π3,霸氣的外觀,一起了解一下吧!
    外觀是真的很漂亮,屬於耐看型車型,非常適合內斂的人選擇它,沉穩大氣,整體顯得很上檔次,風格上非常的年輕、運動。給大家圖解一款雲度π3,霸氣的外觀,一起了解一下吧!這款雲度π3估計最出名的就是外觀了吧,設計非常特別,有設計感,和大街上那些平平常常的車子比起來那就非常出類拔萃了,外觀方面既能讓人覺得好看又不會千篇一律,實在是難得。
  • [LeetCode] 912. Sort an Array 數組排序
    for (int idx = 0; idx < tmp.size(); ++idx) { nums[idx + start] = tmp[idx]; } }};Github 同步地址:https://github.com/grandyang/leetcode
  • LeetCode面試系列 第6天:No.9 - 迴文數
    迴文數https://leetcode-cn.com/problems/palindrome-number/題目描述判斷一個整數是否是迴文數。迴文數是指正序(從左向右)和倒序(從右向左)讀都是一樣的整數。
  • leetcode鍊表之回文鍊表
    序本文主要記錄一下leetcode鍊表之回文鍊表題目
  • [LeetCode] 976. Largest Perimeter Triangle 最大周長的三角形
    if (A[i] < A[i - 1] + A[i - 2]) { return A[i] + A[i - 1] + A[i - 2]; } } return 0; }};Github 同步地址:https://github.com/grandyang/leetcode
  • LeetCode-66.加一(Plus One)
    來源:力扣(LeetCode)連結:https://leetcode-cn.com/problems/plus-oneLink:https://leetcode.com/problems/plus-one/模擬加O(N)加後反轉數組分別放入個位,十位,百位...
  • Go 刷 leetcode|一道簡單難度卻讓我陷入沉思的題目
    來源:力扣(LeetCode)連結:https://leetcode-cn.com/problems/maximum-subarray著作權歸領扣網絡所有。商業轉載請聯繫官方授權,非商業轉載請註明出處。
  • LeetCode數組類知識點&題型總結
    leetcode第一題就是two-sum,對於這類題目,首先看題目要求的時間複雜度和空間複雜度是什麼,其次看有沒有限制條件,如要求不能有重複的子數組或者要求按照升序/降序排列等。1.按start排序2.在前一個區間的end和後一個區間的start找交集例題:252 meeting room[easy](https://leetcode.com/problems/meeting-rooms/)題目理解:給定一個數組,包含每個會議的開始時間和結束時間[[s1,e1],[s2,e2],...]
  • leetcode刷對了麼
    今天,逆行君就帶你從世界觀和方法論兩方面走進「leetcode」 簡單來說,leetcode是一個美國的在線編程網站,它收集了各大公司的經典算法面試題,用戶可以選擇不同的語言進行代碼的在線編寫、編譯和調試。
  • leetcode之羅馬數字轉整數
    序本文主要記錄一下leetcode之羅馬數字轉整數題目給定一個羅馬數字,將其轉換成整數。
  • 交易玄學:斐波那契數列
    斐波那契數列。  斐波那契數列是什麼呢?  1202年,那時印刷術還沒有出現,斐波那契的書《算盤書》在義大利出版,受到當時羅馬君主的支持,而得以幸運地傳播開來。《算盤書》將阿拉伯世界的阿拉伯數字引進了當時的西方,其中一篇短文最為著名。
  • 特殊數列之等差數列與等比數列
    特殊數列之等差數列等差數列是一種有特殊規律的數列,它的後面一項減去前面一項的差值是一個定值,其一般表示形式如下所示它的相鄰兩項具有統一性質的聯繫,其遞推關係為如果已知等差數列第1項,其第n項比第一項多出n-1個公差d,那麼其通項公式可表示為
  • 最美的數列-斐波那契數列
    今天跟大家一起分享一下斐波那契數列。斐波那契數列簡介斐波那契數列, 就是由這位義大利著名數學家萊昂納多·斐波那契在《計算之書》中以兔子繁殖為例子而提出的數列,故又稱為「兔子數列」。斐波那契數列:1、1、2、3、5、8、13、21、34、56……這個數列的特點是從第3項開始,每一項都是前兩項的和。例如 3=2+1,5=3+2,8=5+3等。省略號後面有無數項。斐波那契數列美在哪裡呢?
  • LeetCode-1732.找到最高海拔(Find the Highest Altitude)
    提示:n == gain.length1 <= n <= 100-100 <= gain[i] <= 100來源:力扣(LeetCode)連結:https://leetcode-cn.com/problems/find-the-highest-altitudeLink: