Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

91. Decode Ways
該題提供一個由數字組成的字串s，並提供我們一個編碼表：

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

求出s共有幾種編碼的方式，若無法被編碼出來返回0。

Example：
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).


解法一 遞迴窮舉

思路：
1.每個字串每次都有兩個選擇，分別是一個一個切和兩個兩個切，遞迴樹如下所示：
https://i.imgur.com/InBW19F.png

2.當遇到下列情況時，表示當前的字串無法繼續解析：
  ＞ 字串長度為1且數字 < 1 （0）
  ＞ 字串長度為2且第一位數 < 1 或 > 2 （06, 38, 46, ...）
  ＞ 字串長度為2且第二位數 > 6 （27, 28, 29）

3.依據第二點之條件，不斷的把字串切分，當切到最後一個字串時，表示這個切分
  是合法的，res遞增

4.返回res

Java Code：
class Solution {
    public int numDecodings(String s) {
        return s.length() == 0 ? 0 : numDecodings(s, 0);
    }
    private int numDecodings(String s, int start) {
        int n = s.length();
        if(start == n) return 1;
        if(s.charAt(start) == '0') return 0;
        int res = numDecodings(s, start + 1);
        if(start < n - 1 && (s.charAt(start) == '1' ||
                s.charAt(start) == '2' && s.charAt(start + 1) < '7'))
            res += numDecodings(s,start + 2);
        return res;
    }
}

結果：TLE


解法二 記憶體最佳化

1.法一的遞迴過程有太多的重複計算，例如對於字串1111111，我們會重複算多次111, 11
  11, 11, ...等等

2.利用一個momo儲存已經算過的區段

Java Code：
class Solution {
    Integer[] memo;
    public int numDecodings(String s) {
        memo = new Integer[s.length()];
        return s.length() == 0 ? 0 : numDecodings(s, 0);
    }
    private int numDecodings(String s, int start) {
        int n = s.length();
        if(start == n) return 1;
        if(s.charAt(start) == '0') return 0;
        if(memo[start] != null) return memo[start];
        int res = numDecodings(s, start + 1);
        if(start < n - 1 && (s.charAt(start) == '1' ||
                s.charAt(start) == '2' && s.charAt(start + 1) < '7'))
            res += numDecodings(s,start + 2);
        return memo[start] = res;
    }
}

解法三 Button up
1.與法二概念類似，推導出狀態轉移方程後，直接iterative求得解

Java Code：
class Solution {
    public int numDecodings(String s) {
        if (s.charAt(0) == '0') return 0;
        char[] chars = s.toCharArray();
        int n = chars.length;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; ++i) {
            dp[i] = chars[i - 1] == '0' ? 0 : dp[i - 1];
            if (i > 1 && (chars[i - 2] == '1'
                || (chars[i - 2] == '2' && chars[i - 1] < '7'))) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[n];
    }
}


做過的題目 上次是用法三解

這次練習用遞迴解解看

告辭

--
https://i.imgur.com/YPBHGGE.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 115.165.253.177 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1664608873.A.435.html
推 DreaMaker167: 你要準備考什麼@@
推 pandix: 大師
推 abcd991276: 大師