Decode Ways
A message containing letters fromA-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.
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.
头疼的题目,突然脑子失灵一样,硬是没办法转弯!
转弯过来了:两个条件判断的时候就使用两个动态规划表来存储数据,因为每次交叉判断.
当然leetcode论坛有使用一个表的,不过使用一个表就很不好理解。
记住:有多少个条件判断就需要使用多少个表来存储数据,因为每个判断条件要改动的数据结果都不一样,不能混饶了,保持思路清晰。
注意:一定需要画递归树,一步一步地区填表,才不会乱,否则很容易出错!
int numDecodings(string s)
{
if (s.length()<1 || s[0] == '0') return 0;
if (s.length() == 1) return 1;
vector<int> ta1(s.length());
vector<int> ta2(s.length());
ta1[0] = 1; ta2[0] = 0;
if (s[1] != '0') ta1[1] = 1;
if (s[0] == '1' || s[0]=='2'&&s[1]<='6') ta2[1]=1;
else ta2[1]=0;
for (int i = 2; i < s.length(); i++)
{
if (s[i]!='0') ta1[i]=ta1[i-1]+ta2[i-1];
else ta1[i]=0;
if (s[i-1]=='1' || s[i-1] =='2' && s[i] <= '6')
ta2[i] = ta1[i-2]+ta2[i-2];
else ta2[i] = 0;
}
return ta1[s.length()-1]+ta2[s.length()-1];
}
6个变量2个一维表,存储数据的动态规划法:
int numDecodings2(string s)
{
if (s.length()<1 || s[0] == '0') return 0;
if (s.length() == 1) return 1;
vector<int> ta1(3);
vector<int> ta2(3);
ta1[0] = 1; ta2[0] = 0;
if (s[1] != '0') ta1[1] = 1;
if (s[0] == '1' || s[0]=='2'&&s[1]<='6') ta2[1]=1;
else ta2[1]=0;
for (int i = 2; i < s.length(); i++)
{
if (s[i]!='0') ta1[i%3]=ta1[(i-1)%3]+ta2[(i-1)%3];
else ta1[i%3]=0;
if (s[i-1]=='1' || s[i-1] =='2' && s[i] <= '6')
ta2[i%3] = ta1[(i-2)%3]+ta2[(i-2)%3];
else ta2[i%3] = 0;
}
return ta1[(s.length()-1)%3]+ta2[(s.length()-1)%3];
}
也是使用6个变量就可以了:
int numDecodings3(string s)
{
if (s.length()<1 || s[0] == '0') return 0;
if (s.length() == 1) return 1;
int a=0,b=0,c=0;
int d=0,e=0,f=0;
a = 1; d = 0;
if (s[1] != '0') b = 1;
if (s[0] == '1' || s[0]=='2'&&s[1]<='6') e=1;
else e=0;
for (int i = 2; i < s.length(); i++)
{
c=b;
if (s[i]!='0') b=b+e;
else b=0;
f=e;
if (s[i-1]=='1' || s[i-1] =='2' && s[i] <= '6')
e = a+d;
else e = 0;
a=c; d=f;
}
return b+e;
}
高级境界,已经是绕过递归思维,直接填表就行了。
至于是怎么做到的?
前提应该是:
1 递归法很熟了
2 动态规划法很熟了
简单描述下面程序的思维:
当前编码方法可以是两种:
1 当前字母编码编码为一个字母
2 当前字母和前一个字母编码为两个字母
判断两者是否合法。
//2014-2-14 update
int numDecodings(string s)
{
if (s.empty() || s[0] == '0') return 0;
int *A = new int[s.length()+1];
A[0] = 1, A[1] = 1;
for (int i = 1; i < s.length(); i++)
{
A[i+1] = (s[i]=='0')? 0:A[i];
if (s[i-1]=='1' || s[i-1]=='2'&&s[i]<'7') A[i+1] += A[i-1];
}
return A[s.length()];
}
最高境界,三个变量:
//2014-2-14 update
int numDecodings(string s)
{
if (s.empty() || s[0] == '0') return 0;
int a = 1, b = 1, c = 1;
for (int i = 1; i < s.length(); i++)
{
c = (s[i]=='0')? 0:b;
if (s[i-1]=='1' || s[i-1]=='2'&&s[i]<'7') c += a;
a = b, b = c;
}
return c;
}
分享到:
相关推荐
js代码-leetcode 91 DEcode Ways
leetcode怎么改密码 Code leetcode easy 测试一下本地的... emmmmm之前修改了一下,现在用ssh提交 应该不用输入密码了吧 ~~emmmmm 先在这里立个flag!!!~~都F了一年了 windows test <<<<<<< ...
收集LeetCode问题以完成编码面试!-使用[LeetHub v2]()创建.zip
如何正确刷题?LeetCode刷题误区和刷题方法论分享【LeetCode刷题套路教程1】
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
密码 每天AC一道题!
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
leetcode 答案力码 LeetCode 每月挑战编码问题和答案
leetcode oj 和 leetcode 编码 该存储库用于编码消费税
leetcode中国leetcode leetcode 编码面试解决方案 参考链接: 力码: 力扣中国: 智慧峰的 LeetCode 回购: 系统设计入门:
密码 我的密码
leetcode2021:密码
LeetCode 收集LeetCode问题以使编码面试更加出色!
密码收集LeetCode问题以使编码面试更上一层楼!
LeetCode LeetCode编码
LeetCode全合一 English |针对所有Leetcode编码问题提供我所有的中文解决方案和解释。 与此相同: 注意:所有说明均写在Github Issues中,请不要在该项目中创建任何新问题,因为问题索引应与问题索引一致,谢谢! ...
Leetcode_Solutions 收集LeetCode问题以使编码面试更加出色!
leetcode 修改密码 :four_leaf_clover: 编码问题解决方案 :four_leaf_clover: 来自 LeetCode 和 CodeWars 的问题解决方案 我所有的解决方案都可以在以下位置找到: 设置 git clone ...修改archgenerator/archgenerator/...
LeetCode解决方案 这个存储库保存了我对LeetCode上常见的编码挑战的解决方案。