[Leetcode] Count And Say 外觀序列

Towers 發布于2019-08-14 12:44 / 2975人閱讀

摘要：遞歸解法復雜度時間空間遞歸棧思路該序列又叫做外觀序列，無論如何我們都得將前一個序列元素算出來，才能計算后一個序列元素。當遞歸至的時候返回初始數字。另外，比如初始數字，第一次變成了，我們可以發現大于的數都只會一個一個出現了。

Count And Say

The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

遞歸解法 復雜度

時間 O(N!) 空間 O(N) 遞歸棧

思路

該序列又叫做外觀序列，無論如何我們都得將前一個序列元素算出來，才能計算后一個序列元素。當遞歸至0的時候返回初始數字1。

代碼

public class Solution {
    public String countAndSay(int n) {
        // 遞歸盡頭返回空或者1
        if(n == 0) return "";
        if(n == 1) return "1";
        // 計算出上一個字符串
        String s = countAndSay(n - 1);
        StringBuilder sb = new StringBuilder();
        // 通過記錄上次的字符來判斷是否重復
        char last = s.charAt(0);
        int cnt = 1;
        for(int i = 1; i < s.length(); i++){
            // 如果重復則計數器加1
            if(s.charAt(i) == last){
                cnt++;
            } else {
            // 否則添加上一個字符，并重置計數器為1
                sb.append(cnt);
                sb.append(last);
                last = s.charAt(i);
                cnt = 1;
            }
        }
        // 最后記得把最后一個字符加上
        sb.append(cnt);
        sb.append(last);
        return sb.toString();
    }
}

迭代解法 復雜度

時間 O(N!) 空間 O(N) 字符長度

思路

將遞歸換成了循環而已。

代碼

public class Solution {
    public String countAndSay(int n) {
        if(n == 0) return "";
        String s = "1";
        for(int j = 1; j < n; j++){
            StringBuilder sb = new StringBuilder();
            char last = s.charAt(0);
            int cnt = 1;
            for(int i = 1; i < s.length(); i++){
                if(s.charAt(i) == last){
                    cnt++;
                } else {
                    sb.append(cnt);
                    sb.append(last);
                    last = s.charAt(i);
                    cnt = 1;
                }
            }
            sb.append(cnt);
            sb.append(last);
            s = sb.toString();
        }
        return s;
    }
}

后續 Follow Up

Q：該序列有什么特點？
A：該序列最大的數不超過3，除非初始的數字大于3

Q: 對于101這種數字如何解讀？
A：因為10后面只有1個（奇數）數字，所以不可能是1個0，肯定是10個1.

Q: 如果有三位數，比如200個1，表示成2001時怎么辦？
A: 其實我們可以發現，除了第一次生成的數以外，以后再也不可能有200個連續的同一個數，所以這種情況只可能發生在第一次count and say，特殊處理一下就好了。另外，比如初始數字9991999，第一次變成了391139，我們可以發現大于3的數都只會一個一個出現了。

云服務器 GPU云服務器 Say LeetCode LeetCode_String leetcode_35_SearchIn

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.hztianpu.com/yun/64675.html

[Leetcode] Count and Say 數個數

摘要：反轉字符法復雜度時間空間思路因為數字不好從前向后遍歷每一位要先統計一共有多少位，比較麻煩，所以我們直接從后向前計數，最后把結果倒置就行了。 Count Consecutive Digits in Integer Count consecutive digits and say it. For example, return 132341 if input is 1112224. The...

whjin 2019-08-14 12:30 評論0 收藏0
leetcode 38 count and say

摘要：而讀起來是兩個，所以第三個字符串就應當是。同理第四個字符串是一個一個，因此是。依次類推而我們的目的是，對于輸入的正整數，我們要給出第個字符串是什么。這里采用了是為了減少內存的開銷。解法設置初始字符串將重新賦值當前字符字符計數題目詳情 The count-and-say sequence is the sequence of integers with the first five t...

不知名網友 2019-08-16 10:31 評論0 收藏0
leetcode38 count and say 數數游戲

摘要：題目要求英文的題目有點繞口，所以去網上找了一下題目的意思。題目的核心邏輯在于將口語化的數數字轉化為字符串。題目要求 The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ... 1 is read off as one 1 or 11...

dabai 2019-08-14 18:04 評論0 收藏0
[LeetCode] 398. Random Pick Index (Reservoir Sampl

Problem Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array. Note:The array siz...

edagarli 2019-08-16 13:46 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0