資訊專欄INFORMATION COLUMN
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];
}
}
*/
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66991.html
摘要：經(jīng)總結(jié)，發(fā)現(xiàn)當(dāng)前字符前面的兩個(gè)字符和一個(gè)字符可以拿出來(lái)進(jìn)行分析。當(dāng)前的數(shù)目可以作為和的數(shù)目的疊加。所以關(guān)系式是其他的特殊情況可以進(jìn)行特殊處理。需要注意的是如果錢兩位是，，則這兩位作廢，不能計(jì)入其他情況的統(tǒng)計(jì)，即。 描述 A message containing letters from A-Z is being encoded to numbersusing the following...
摘要：最新更新請(qǐng)見動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路解碼是有規(guī)律的，所以我們可以嘗試動(dòng)態(tài)規(guī)劃。如果字符串的第位和第位不能組成有效二位數(shù)字，而且第位不是的話，說(shuō)明我們是在第位的解碼方法上繼續(xù)解碼。 Decode Ways 最新更新請(qǐng)見：https://yanjia.me/zh/2019/02/... A message containing letters from A-Z is being en...
摘要：用將子字符串轉(zhuǎn)化為，參見和的區(qū)別然后用動(dòng)規(guī)方法表示字符串的前位到包含方法的個(gè)數(shù)。最后返回對(duì)應(yīng)字符串末位的動(dò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 ...
摘要：前言肝了一天，最后打了第三，記錄下。同一樣，它也將輸入的字符串或數(shù)據(jù)編碼成全是碼的可打印字符串。 前言 肝了一天，最后打了第三，記錄下。我逆向真的好菜啊~~~~ Reverse baby_reverse 加密函數(shù)如下 int __fastcall encode(const char *a1, __int64 a2) { char v3[32]; // [rsp+10h] [rbp-...
閱讀 1414·2021-11-25 09:43
閱讀 2272·2021-09-27 13:36
閱讀 1125·2021-09-04 16:40
閱讀 1964·2019-08-30 11:12
閱讀 3320·2019-08-29 14:14
閱讀 575·2019-08-28 17:56
閱讀 1335·2019-08-26 13:50
閱讀 1258·2019-08-26 13:29
