h********o
发帖数: 14 | 1 http://www.leetcode.com/onlinejudge 进入这个链接， 搜索 页面上“decode ways”就能找到题目。leetcode 大侠对题目的表达很清楚， 为了避免表达不清造成歧义，就不转述了
我觉得是个较为简单的DP，先列举出最后只剩一个字符，和两个字符的情况，然后往前推
代码如下：
int numDecodings(string s) {
int l = s.size();
vector r(l,0);
r[l-1] = 1;
if ((s[l-2]-'0')*10+s[l-1]-'0' <= 26) r[l-2] = 2;
else r[l-2] = 1;
for (int i = l-3; i>=0; i--) {
r[i] = r[i+1];
if ((s[i]-'0')*10+s[i+1]-'0' <= 26)
r[i] = r[i] + r[i+2];
}
return r[0];
}
但是leetcode online judge说是 running time error， 不知道哪里出了问题，还是
我想的不对，或者有比O(n)跟好的算法， 请版上各位大侠指教，非常感谢 |
p********s
发帖数: 37 | |
b**a
发帖数: 1118 | 3 My code passed the small test but failed big test. Can anyone take a look
and suggest the reason? Thanks.
int numDecodings(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(s.size()==0)
return 0;
char first, second;
first=s[0];
if((first-'0')==0)
return 0;
int len= s.size();
int count=1;
for(int i=1; i
{
char second=s[i];
if(second=='0')
{
if(0==(first-'0')||(first-'0')>2)
return 0;
else
{
if(count>1)count--;
}
}
else//second is not 0
{
if(((first-'0')<=2 && (first-'0')>0) && (second-'0')<=6 )
{
count++;
}
}
first=second;
}
return count;
} |
p*****2
发帖数: 21240 | 4 我写了一个练练。
public int numDecodings(String s)
{
if(s==null || s.length()==0)
return 0;
int len=s.length();
int[] dp=new int[len+1];
dp[len]=1;
for(int i=len-1;i>=0;i--)
{
if(s.charAt(i)!='0')
{
dp[i]=dp[i+1];
if(i
dp[i]+=dp[i+2];
}
}
return dp[0];
} |
p*****2
发帖数: 21240 | 5
前推
随便看了一下，你怎么得出来的这个？
【在 h********o 的大作中提到】
: http://www.leetcode.com/onlinejudge 进入这个链接， 搜索 页面上“decode ways”就能找到题目。leetcode 大侠对题目的表达很清楚， 为了避免表达不清造成歧义，就不转述了
: 我觉得是个较为简单的DP，先列举出最后只剩一个字符，和两个字符的情况，然后往前推
: 代码如下：
: int numDecodings(string s) {
: int l = s.size();
: vector r(l,0);
: r[l-1] = 1;
: if ((s[l-2]-'0')*10+s[l-1]-'0' <= 26) r[l-2] = 2;
: else r[l-2] = 1;
: for (int i = l-3; i>=0; i--) {
|
h********o
发帖数: 14 | 6 非常惭愧，犯了几个低级的错误：
1. 竟然没考虑到到遇到 ‘0’ 不能单独解码
2. vector 下标溢出。
以后要多加注意，谢谢各位的回复和指点。
buaa (ming)， 你的code我没有看明白：每次 看 first 和 second 两个字符，如果能
解码就 count++，否则就 count--， 我不确定这样能得出正确的结果。 建议还是用
DP 更容易理解。
peking2 (myfacebook) 的java代码是对的
我修改后的c++代码和 peking2 (myfacebook)的是一个思路， 贡你参考，如下：
int numDecodings(string s) {
int l = s.size();
if (l==0) return 0;
vector r(l+1,0);
if (s[l-1]=='0') r[l-1] = 0; // 先考虑最后一个字符的情况
else r[l-1] = 1;
r[l]=1;
for (int i = l-2; i>=0; i--) { //然后从倒数第二个字符往前推
if (s[i]=='0') r[i] = 0;
else{
r[i] = r[i+1];
if ((s[i]-'0')*10+s[i+1]-'0' <= 26)
r[i] = r[i] + r[i+2];
}
}
return r[0];
}
【在 p*****2 的大作中提到】
:
: 前推
: 随便看了一下，你怎么得出来的这个？
|
p*****2
发帖数: 21240 | 7
这题我也没一次作对，调了一会儿才行。
【在 h********o 的大作中提到】
: 非常惭愧，犯了几个低级的错误：
: 1. 竟然没考虑到到遇到 ‘0’ 不能单独解码
: 2. vector 下标溢出。
: 以后要多加注意，谢谢各位的回复和指点。
: buaa (ming)， 你的code我没有看明白：每次 看 first 和 second 两个字符，如果能
: 解码就 count++，否则就 count--， 我不确定这样能得出正确的结果。 建议还是用
: DP 更容易理解。
: peking2 (myfacebook) 的java代码是对的
: 我修改后的c++代码和 peking2 (myfacebook)的是一个思路， 贡你参考，如下：
: int numDecodings(string s) {
|
b**a
发帖数: 1118 | 8 Thanks. It seemed mine is not right. I tried but failed to work from start.
Both you guys start from the end. I was wondering, is this required by DP
since you are using it? or something else? Mind sharing your thought train?
Really appreciate it.
【在 h********o 的大作中提到】
: 非常惭愧，犯了几个低级的错误：
: 1. 竟然没考虑到到遇到 ‘0’ 不能单独解码
: 2. vector 下标溢出。
: 以后要多加注意，谢谢各位的回复和指点。
: buaa (ming)， 你的code我没有看明白：每次 看 first 和 second 两个字符，如果能
: 解码就 count++，否则就 count--， 我不确定这样能得出正确的结果。 建议还是用
: DP 更容易理解。
: peking2 (myfacebook) 的java代码是对的
: 我修改后的c++代码和 peking2 (myfacebook)的是一个思路， 贡你参考，如下：
: int numDecodings(string s) {
|
j*******e
发帖数: 1058 | |
h********o
发帖数: 14 | 10 Sorry for late rely. I don't think that DP requires the start from the end.
The idea is to solve the smallest and simplest sub-problem first, and then,
with that result, you can derive the larger sub-problems which are more
complicated. In this problem, i guess starting from the end gives you the
smallest and simplest sub-problem that you can solve right away.
.
【在 b**a 的大作中提到】
: Thanks. It seemed mine is not right. I tried but failed to work from start.
: Both you guys start from the end. I was wondering, is this required by DP
: since you are using it? or something else? Mind sharing your thought train?
: Really appreciate it.
|
b**a
发帖数: 1118 | 11 I see. I learn quite some from this question. Really thx.
.
,
【在 h********o 的大作中提到】
: Sorry for late rely. I don't think that DP requires the start from the end.
: The idea is to solve the smallest and simplest sub-problem first, and then,
: with that result, you can derive the larger sub-problems which are more
: complicated. In this problem, i guess starting from the end gives you the
: smallest and simplest sub-problem that you can solve right away.
:
: .
|
