x***e 发帖数: 11 | 1 题目是decode ways
但是input String可以包含 *
比如 1*2,可以有 102 (1),112 (3), 122(3),132(2), 142(2), 152(2),
162(2), 172(2) 182(2) 192 (2) 一共 21种解法。
返回多少解, 刚开始想还挺简单的,写起来并不简单,比如 1**1 ,两个*都要判断。。 | W***o 发帖数: 6519 | 2 关注一下,我也想知道
。。
【在 x***e 的大作中提到】 : 题目是decode ways : 但是input String可以包含 * : 比如 1*2,可以有 102 (1),112 (3), 122(3),132(2), 142(2), 152(2), : 162(2), 172(2) 182(2) 192 (2) 一共 21种解法。 : 返回多少解, 刚开始想还挺简单的,写起来并不简单,比如 1**1 ,两个*都要判断。。
| G**O 发帖数: 147 | 3 我赶脚,就是对每个*枚举咯。
。。
【在 x***e 的大作中提到】 : 题目是decode ways : 但是input String可以包含 * : 比如 1*2,可以有 102 (1),112 (3), 122(3),132(2), 142(2), 152(2), : 162(2), 172(2) 182(2) 192 (2) 一共 21种解法。 : 返回多少解, 刚开始想还挺简单的,写起来并不简单,比如 1**1 ,两个*都要判断。。
| c******w 发帖数: 1108 | 4 Let A be the input array of digits or *
Let I(n, 1) = count of valid values (between 1 and 26) can be obtained by A[
n].
If A[n] == 0, then I(n, 1) = 0;
else if A[n] == *, then I(n, 1) = 9; // 1~9
else A[n] = 1~9, then I(n, 1) = 1.
Let I(n, 2) = count of valid values can be obtained by A[n-1] * 10 A[n].
If A[n-1] == 1, then I(n, 2) = (A[n] == * ? 10 : 1); // 10~19
else if A[n-1] == 2, then I(n, 2) = (A[n] == * ? 7 : (A[n] <= 6 ? 1 : 0))
; // 20~26
else if A[n-1] == *, then I(n, 2) = (A[n] == * ? 17 : (A[n] <= 6 ? 2 : 1)
); // 10~26
else I(n, 2) = 0. // A[n-1] == 0 or A[n-1] > 2
For both basic version and follow-up version:
D[n] = D[n-1] * I(n, 1) D[n-2] * I(n, 2) | j**********1 发帖数: 14 | 5 不知道对不对 大概跑了几个test case貌似没啥问题
public static int decodeWays(String s) {
if (s == null || s.length() == 0) return 0;
int[] dp = new int[s.length() + 1];
dp[s.length()] = 1;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '0') dp[i] = 0;
else if (s.charAt(i) != '*') {
dp[i] += dp[i + 1];
if (i + 1 < s.length()) {
if (s.charAt(i + 1) != '*') {
int num = (s.charAt(i) - '0') * 10 + (s.charAt(i + 1
) - '0');
if (num >= 10 && num <= 26) dp[i] += dp[i + 2];
}
else if (s.charAt(i) == '1') dp[i] += dp[i + 2] * 10;
else if (s.charAt(i) == '2') dp[i] += dp[i + 2] * 7;
}
} else {
dp[i] += dp[i + 1] * 9;
if (i + 1 < s.length()) {
if (s.charAt(i + 1) != '*') {
if (s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '6'
) dp[i] += dp[i + 2] * 2;
else dp[i] += dp[i + 2];
} else {
dp[i] += dp[i + 2] * 17;
}
}
}
}
return dp[0];
} | i***h 发帖数: 12655 | 6 112 (3)括号里的3是什么意思?
。。
【在 x***e 的大作中提到】 : 题目是decode ways : 但是input String可以包含 * : 比如 1*2,可以有 102 (1),112 (3), 122(3),132(2), 142(2), 152(2), : 162(2), 172(2) 182(2) 192 (2) 一共 21种解法。 : 返回多少解, 刚开始想还挺简单的,写起来并不简单,比如 1**1 ,两个*都要判断。。
| m******e 发帖数: 82 | 7 112->[1,1,2], [11,2], [1,12]
楼上的方法应该是对的 | G**O 发帖数: 147 | 8 这是对的。
【在 j**********1 的大作中提到】 : 不知道对不对 大概跑了几个test case貌似没啥问题 : public static int decodeWays(String s) { : if (s == null || s.length() == 0) return 0; : int[] dp = new int[s.length() + 1]; : dp[s.length()] = 1; : for (int i = s.length() - 1; i >= 0; i--) { : if (s.charAt(i) == '0') dp[i] = 0; : else if (s.charAt(i) != '*') { : dp[i] += dp[i + 1]; : if (i + 1 < s.length()) {
|
| G**O 发帖数: 147 | 9 还有个followup
我decode不是按照1-26
而是有MAP, 比如 A -> 50, B -> 2, C = 200
怎么办 | f******4 发帖数: 51 | 10
说说思路?最后那里乘以17是怎么来的?
【在 G**O 的大作中提到】 : 这是对的。
| | | m******e 发帖数: 82 | 11 **
10...19
20...26
【在 f******4 的大作中提到】 : : 说说思路?最后那里乘以17是怎么来的?
| G**O 发帖数: 147 | 12 这广告做的有点。。。。
又要关注,又要转发,才能看个答案。上面都贴出对的了。 | s********x 发帖数: 914 | 13 那个解法有bug吧
【在 G**O 的大作中提到】 : 这广告做的有点。。。。 : 又要关注,又要转发,才能看个答案。上面都贴出对的了。
| h****n 发帖数: 1 | 14 我有解题答案,发邮件到 [email protected] 跟我要 | z*********n 发帖数: 1451 | 15 直接上干货, leetcode已经有这题了 (* 代表1~9 而非0~9),这是我过了的一个解:
class Solution {
int base = 1000000007;
public:
int numDecodings(string s) {
//last1: decode ways of s ending at i-1, last2 decode ways of s
ending at i-2, nlast1 : next last1.
long long last1 = 1, last2 = 1, nlast1 = 0; //there is only 1 way to
decode "", so initialized with 1.
for (int i = 0; i < s.size(); ++ i)
{
//Just look at current character
if (s[i] == '*')
nlast1 = last1 * 9 % base;
else if (s[i] == '0')
nlast1 = 0;
else
nlast1 = last1;
//All three if below: look at last two characters.
if (i > 0 && s[i - 1] == '1')
if (s[i] == '*')
nlast1 = (nlast1 + last2 * 9) % base;
else
nlast1 = (nlast1 + last2) % base;
if (i > 0 && s[i - 1] == '2')
if (s[i] == '*')
nlast1 = (nlast1 + last2 * 6) % base;
else if (s[i] <= '6')
nlast1 = (nlast1 + last2) % base;
if (i > 0 && s[i - 1] == '*')
if (s[i] == '*')
nlast1 = (nlast1 + last2 * 15) % base; //1* + 2* = 15
else if (s[i] <= '6')
nlast1 = (nlast1 + last2 * 2) % base; //1a + 2a = 2, a
is one fixed number.
else
nlast1 = (nlast1 + last2) % base; //1a = 1 case
last2 = last1;
last1 = nlast1;
}
return last1;
}
}; | u**u 发帖数: 668 | |
|