資訊專欄INFORMATION COLUMN
摘要：用將子字符串轉(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 an encoded message containing digits, determine the total number of ways to decode it.
ExampleGiven encoded message 12, it could be decoded as AB (1 2) or L (12).
The number of ways decoding 12 is 2.
用parseInt將子字符串轉(zhuǎn)化為int，參見parseInt和valueOf的區(qū)別；
然后用動規(guī)方法：
dp[i]表示字符串s的前i位（0到i-1）包含decode方法的個數(shù)。
若前一位i-2到當(dāng)前位i-1的兩位字符串s.substring(i-2, i)對應(yīng)的數(shù)字lastTwo在10到26之間，則當(dāng)前位dp[i]要加上這兩位字符之前一個字符對應(yīng)的可能性：dp[i-2];
若當(dāng)前位i-1的字符對應(yīng)1到9之間的數(shù)字（不為0），則當(dāng)前dp[i]要加上前一位也就是第i-2位的可能性：dp[i-1]。
最后返回對應(yīng)字符串s末位的動規(guī)結(jié)果dp[n]。
class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0) return 0;
int n = s.length();
int[] dp = new int[n+1];
dp[0] = 1; //if the first two digits in [10, 26]
dp[1] = s.charAt(0) == "0" ? 0 : 1;
for (int i = 2; i <= n; i++) {
if (s.charAt(i-1) != "0") dp[i] += dp[i-1]; //XXX5X
int lastTwo = Integer.parseInt(s.substring(i-2, i));
if (lastTwo >= 10 && lastTwo <= 26) dp[i] += dp[i-2]; //XXX10X
}
return dp[n];
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65974.html
摘要：建立動規(guī)數(shù)組，表示從起點處到達(dá)該點的可能性。循環(huán)結(jié)束后，數(shù)組對所有點作為終點的可能性都進(jìn)行了賦值。和的不同在于找到最少的步數(shù)。此時的一定是滿足條件的最小的，所以一定是最優(yōu)解。 Jump Game Problem Given an array of non-negative integers, you are initially positioned at the first index...
摘要：這里要注意的是的用法。所以記住，用可以從自動分離出數(shù)組。跳過第一個元素并放入數(shù)組最快捷語句建立的用意記錄處理過的結(jié)點并按處理所有結(jié)點和自己的連接下面先通過判斷，再修改的符號的順序，十分巧妙更輕便的解法 Problem Design an algorithm and write code to serialize and deserialize a binary tree. Writin...
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 n...
Problem Given a positive integer n and you can do operations as follow: 1.If n is even, replace n with n/2.2.If n is odd, you can replace n with either n + 1 or n - 1. What is the minimum number of re...
Problem Implement a stack with min() function, which will return the smallest number in the stack. It should support push, pop and min operation all in O(1) cost. Example push(1)pop() // return 1pus...
閱讀 1215·2021-11-23 09:51
閱讀 1993·2021-10-08 10:05
閱讀 2352·2019-08-30 15:56
閱讀 1911·2019-08-30 15:55
閱讀 2645·2019-08-30 15:55
閱讀 2498·2019-08-30 13:53
閱讀 3510·2019-08-30 12:52
閱讀 1259·2019-08-29 10:57
