Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間1年前 (2022/10/01 15:21)推噓3(3推 0噓 0→)

留言3則, 3人參與討論串19/719 (看更多)

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