成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Decode Ways 解碼方式

animabear / 1662人閱讀

摘要：最新更新請見動態(tài)規(guī)劃復(fù)雜度時間空間思路解碼是有規(guī)律的，所以我們可以嘗試動態(tài)規(guī)劃。如果字符串的第位和第位不能組成有效二位數(shù)字，而且第位不是的話，說明我們是在第位的解碼方法上繼續(xù)解碼。

Decode Ways 最新更新請見：https://yanjia.me/zh/2019/02/... 
A message containing letters from A-Z is being encoded to numbers using the following mapping:


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



Given an encoded message containing digits, determine the total number of ways to decode it.


For example, Given encoded message "12", it could be decoded as "AB"
(1 2) or "L" (12).


The number of ways decoding "12" is 2.
動態(tài)規(guī)劃 復(fù)雜度

時間 O(N) 空間 O(N)

思路

解碼是有規(guī)律的，所以我們可以嘗試動態(tài)規(guī)劃。假設(shè)數(shù)組dp[i]表示從頭到字符串的第i位，一共有多少種解碼方法的話，那么如果字符串的第i-1位和第i位能組成一個10到26的數(shù)字，說明我們是在第i-2位的解碼方法上繼續(xù)解碼。如果字符串的第i-1位和第i位不能組成有效二位數(shù)字，而且第i位不是0的話，說明我們是在第i-1位的解碼方法上繼續(xù)解碼。所以，如果兩個條件都符合，則dp[i]=dp[i-1]+dp[i-2]，否則dp[i]=dp[i-1]。

注意

如果出現(xiàn)無法被兩位數(shù)接納的0，則無法解碼，我們可以在一開始就判斷，并將其初始化為0，這樣后面的相加永遠(yuǎn)都是加0

代碼 
public class Solution {
    public int numDecodings(String s) {
        if(s.length() == 0) return s.length();
        int[] dp = new int[s.length() + 1];
        // 初始化第一種解碼方式
        dp[0] = 1;
        // 如果第一位是0，則無法解碼
        dp[1] = s.charAt(0) == "0" ? 0 : 1;
        for(int i = 2; i <= s.length(); i++){
            // 如果字符串的第i-1位和第i位能組成一個10到26的數(shù)字，說明我們可以在第i-2位的解碼方法上繼續(xù)解碼
            if(Integer.parseInt(s.substring(i-2, i)) <= 26 && Integer.parseInt(s.substring(i-2, i)) >= 10){
                dp[i] += dp[i - 2];
            }
            // 如果字符串的第i-1位和第i位不能組成有效二位數(shù)字，在第i-1位的解碼方法上繼續(xù)解碼
            if(Integer.parseInt(s.substring(i-1, i)) != 0){
                dp[i] += dp[i - 1];
            }
        }
        return dp[s.length()];
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64607.html

相關(guān)文章

  • [LintCode/LeetCode] Decode Ways [String to Integer

    摘要：用將子字符串轉(zhuǎn)化為，參見和的區(qū)別然后用動規(guī)方法表示字符串的前位到包含方法的個數(shù)。最后返回對應(yīng)字符串末位的動規(guī)結(jié)果。 Problem A message containing letters from A-Z is being encoded to numbers using the following mapping: A -> 1 B -> 2 ... Z -> 26 Given ...

    andong777 評論0 收藏0

  • leetcode-91-Decode Ways

    摘要：經(jīng)總結(jié)，發(fā)現(xiàn)當(dāng)前字符前面的兩個字符和一個字符可以拿出來進(jìn)行分析。當(dāng)前的數(shù)目可以作為和的數(shù)目的疊加。所以關(guān)系式是其他的特殊情況可以進(jìn)行特殊處理。需要注意的是如果錢兩位是，，則這兩位作廢，不能計入其他情況的統(tǒng)計，即。 描述 A message containing letters from A-Z is being encoded to numbersusing the following...

    sihai 評論0 收藏0

  • [Leetcode] Encode and Decode Strings 字符串編解碼

    摘要：記錄長度法復(fù)雜度時間空間思路本題難點(diǎn)在于如何在合并后的字符串中，區(qū)分出原來的每一個子串。這里我采取的編碼方式，是將每個子串的長度先賦在前面，然后用一個隔開長度和子串本身。這樣我們先讀出長度，就知道該讀取多少個字符作為子串了。 Encode and Decode Strings Design an algorithm to encode a list of strings to a s...

    gself 評論0 收藏0

  • LeetCode 394：字符串解碼 Decode String

    摘要：用棧暫存的邏輯與遞歸基本一致，可以理解為用遞歸實現(xiàn)棧。沒有棧這種數(shù)據(jù)結(jié)構(gòu)，可以用數(shù)組或雙端隊列可以只用一個棧以元組的形式重復(fù)次數(shù)和字符串，如利用棧初始化數(shù)據(jù)結(jié)構(gòu)遞歸字符串入棧刷新計算重復(fù)次數(shù)可直接操作字符串真的很方便。 題目： 給定一個經(jīng)過編碼的字符串，返回它解碼后的字符串。Given an encoded string, return its decoded string. 編碼規(guī)則...

    鄒強(qiáng) 評論0 收藏0

  • leetcode394. Decode String

    摘要：利用棧我們可以存儲外圍層已持有的字符串以及應(yīng)當(dāng)展開的次數(shù)。用棧的思路來寫要求思路更加嚴(yán)謹(jǐn)，以免出現(xiàn)邏輯錯誤。這里需要額外注意的是，如果當(dāng)前該括號外圍存在父元素，則我們應(yīng)當(dāng)將父元素的計數(shù)和已有字符串壓入棧中。 題目要求 Given an encoded string, return its decoded string. The encoding rule is: k[encoded_...

    Ilikewhite 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<