原题链接:http://oj.leetcode.com/problems/decode-ways/这道题要求解一个数字串按照字符串编码方式可解析方式的数量。看到这种求数量的,我们很容易想到动态规划来存储前面信息,然后迭代得到最后结果。我们维护的量res[i]是表示前i个数字有多少种解析的方式,接下来来想想递归式,有两种方式:第一种新加进来的数字不然就是自己比较表示一个字符,那么解析的方式有res[i-1]种,第二种就是新加进来的数字和前一个数字凑成一个字符,解析的方式有res[i-2]种(因为上一个字符和自己凑成了一个)。当然这里要判断前面说的两种情况能否凑成一个字符,也就是范围的判断,如果可以才有对应的解析方式,如果不行,那么就是0。最终结果就是把这两种情况对应的解析方式相加。这里可以把范围分成几个区间:(1)00:res[i]=0(无法解析,没有可行解析方式);(2)10, 20:res[i]=res[i-2](只有第二种情况成立);(3)11-19, 21-26:res[i]=res[i-1]+res[i-2](两种情况都可行);(4)01-09, 27-99:res[i]=res[i-1](只有第一种情况可行);递推式就是按照上面的规则来得到,接下来我们只要进行一遍扫描,然后依次得到维护量就可以了,算法的时间复杂度是O(n)。空间上可以看出我们每次只需要前两位的历史信息,所以只需要维护三个变量然后迭代赋值就可以了,所以空间复杂度是O(1)。代码如下:public int numDecodings(String s) {
if(s==null || s.length()==0 || s.charAt(0)=='0')
{
return 0;
}
int num1=1;
int num2=1;
int num3=1;
for(int i=1;i<s.length();i++)
{
if(s.charAt(i)=='0')
{
if(s.charAt(i-1)=='1' || s.charAt(i-1)=='2')
num3 = num1;
else
return 0;
}
else
{
if(s.charAt(i-1)=='0' || s.charAt(i-1)>='3')
num3 = num2;
else
{
if(s.charAt(i-1)=='2' && s.charAt(i)>='7' && s.charAt(i)<='9')
num3 = num2;
else
num3 = num1+num2;
}
}
num1 = num2;
num2 = num3;
}
return num2;
}
这道题是一维动态规划的题目,递推式关系来说是比较容易得到的,主要是要对这些两位数进行划分有一些细节,容易出小错误。
分享到:
相关推荐
不会394.-解码字符串-c-Leetcode 给定一个编码字符串,返回它的解码字符串。 编码规则是:k[encoded_string],其中方括号内的encoded_string 正好重复k 次。 请注意,k 保证为正整数。 您可以假设输入字符串始终有效...
js代码-leetcode 91 DEcode Ways
介绍了解码转发机会中继下的性能参数分析,包括中断概率,误码率,和信道容量等参数的分析
decode-the-morse-code-for-real-passed Codewar题解
ANSI 到 UTF-8的编解码工具。非常好用。
前端开源库-decode-tiff解码TIFF,轻量级TIFF解码器
leetcode怎么计算空间复杂度是指 LeetCode-Solution my first solution of LeetCode 2015-5-7 Problem 95,98(80 ...我经常在递归的结束地方忘记return!...091:Decode Ways 简单的一维DP,用额外数组O(n)即可。 139,1
[ 9.567442] ##successful to hik-decode-daemon-toplained :/hom
RF-based Energy Harvesting in Decode-and-Forward Relaying Systems_ Ergodic and Outage Capacities PDF论文
资源来自pypi官网。 资源全名:decode-acc-1.0.0.tar.gz
leetcode过桥问题 Leetcode Learning 主要涉及到的算法思想: 回溯 递归 TopK最大 ...Decode String] 【收集的比较好的参考资料】: 递归,二叉树,回溯算法: 经典算法应用之六---过桥问题和过河问题:
STM32F4_NEC_Code_Decode-master.zip
在线protobuf编码/解码工具。 进入根目录,通过以下命令启动。 bower install serve
扩展矩阵leetcode interview-algorithm leetCode 待解决 上楼梯问题 how many ways to decode this message @leetCode 91
资源分类:Python库 所属语言:Python 资源全名:flask_cookie_decode-0.3.0-py2.py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
leetcode 分类 LeetCode Progress 128/154 Other Solutions C++,有详细思路解释 ...Decode Ways Palindrome Partitioning II Maximal Rectangle ###Recursion N-Queens N-Queens II Balanced Binary Tree Binar
协作通信中的解码转发程序,包括卷积编解码,8PSK调制
这个工具,是用来将中文编码为ansi或uft-8字符类型 ,或将ansi或uft-8字符类型 解码为中文