<fieldset id="yqcyg"></fieldset>

<del id="yqcyg"></del>

91. Decode Ways

macg0406 發(fā)布于2019-08-14 18:05 / 1936人閱讀

A message containing letters from A-Z is being encoded to numbers using the following
"A" -> 1
"B" -> 2
...
"Z" -> 26
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.

// O(n) time, O(1) space
public class Solution {
    public int numDecodings(String s) {
        if(s.length() == 0) return 0;
        // i is decided by i+1, i+2
        int pre = 27, digit, first = 1, second = 1, res = 0;
        for(int i=s.length() -1; i>=0; i--) {
            digit = s.charAt(i) - "0";
            if(digit == 0) res = 0;
            else res = first + (digit*10 + pre <= 26 ? second : 0);
            second = first; first = res; pre = digit;
        }
        
        return res;
    }
}

/*  O(n) time, substring takes O(n), O(n) space
public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if(n == 0) return 0;
        int[] memo = new int[n+1];  // ways to decode after this position
        memo[n] = 1;                // nothing to decode
        memo[n-1] = s.charAt(n-1) == "0" ? 0 : 1;
        
        for(int i=n-2; i>=0; i--) {
            if(s.charAt(i) == "0") continue;
            memo[i] = (Integer.parseInt(s.substring(i, i+2)) <= 26) ? memo[i+1] + memo[i+2] : memo[i+1];  
        }
        
        return memo[0];
    }
}
*/

GPU云服務器云服務器 Ways decode json_decode json_decode_null

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

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/66991.html

leetcode-91-Decode Ways

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

sihai 2019-07-31 11:05 評論0 收藏0
[Leetcode] Decode Ways 解碼方式

摘要：最新更新請見動態(tài)規(guī)劃復雜度時間空間思路解碼是有規(guī)律的，所以我們可以嘗試動態(tài)規(guī)劃。如果字符串的第位和第位不能組成有效二位數(shù)字，而且第位不是的話，說明我們是在第位的解碼方法上繼續(xù)解碼。 Decode Ways 最新更新請見：https://yanjia.me/zh/2019/02/... A message containing letters from A-Z is being en...

animabear 2019-08-14 12:38 評論0 收藏0
[LintCode/LeetCode] Decode Ways [String to Integer

摘要：用將子字符串轉(zhuǎn)化為，參見和的區(qū)別然后用動規(guī)方法表示字符串的前位到包含方法的個數(shù)。最后返回對應字符串末位的動規(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 2019-08-14 15:44 評論0 收藏0
2019 “掘安杯” write up

摘要：前言肝了一天，最后打了第三，記錄下。同一樣，它也將輸入的字符串或數(shù)據(jù)編碼成全是碼的可打印字符串。前言肝了一天，最后打了第三，記錄下。我逆向真的好菜啊~~~~ Reverse baby_reverse 加密函數(shù)如下 int __fastcall encode(const char *a1, __int64 a2) { char v3[32]; // [rsp+10h] [rbp-...

Jochen 2019-07-31 10:17 評論0 收藏0