boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 脸书的高频题decode ways的follow up怎么解
相关主题
求助各位大牛:LeetCode的Decode Ways
decode ways follow up string 里面有* 怎么修改代码?
Docode 问题
做个题吧。decoder.
leetcode上 decode ways 那一题 running time error
Hackercup: Squished Status & LeetCode: Decode Ways
一刀题
问一道题(8)
F电面
我这个 4sum的解法是 o^3还是o^2? , xiexie
相关话题的讨论汇总
话题: nlast1话题: dp话题: else话题: last2话题: last1
进入JobHunting版参与讨论
1 (共1页)
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 的大作中提到】
: 这是对的。
相关主题
做个题吧。decoder.
leetcode上 decode ways 那一题 running time error
Hackercup: Squished Status & LeetCode: Decode Ways
一刀题
进入JobHunting版参与讨论
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
16
这题已经上lc了自己去刷
1 (共1页)
进入JobHunting版参与讨论
相关主题
我这个 4sum的解法是 o^3还是o^2? , xiexie
DP的状态转移方程
问一道Google的题
问道老题
贴一个OJ 的 longest valid parenthesis
G家最新电面
leetcode我这2个palindrome的为什么过不了大oj
rocket fuel第一轮面经
LeetCode 上的题目 AC Rate。
g电面
相关话题的讨论汇总
话题: nlast1话题: dp话题: else话题: last2话题: last1