锐客网

  1. 首页 > it技术 > >

算法|LeetCode 91&&639 动态规划java

LeetCode 91&&639 动态规划java 小白写博客不会用画图，只能勉强用手写。。希望大家不要介意。。如果
有好的画图软件，希望大家告诉我一下！
1）91.解码方法

动态规划思路： 对于字符串s上任意第i个字符，都可能可以**解码当前字符**或者与前**一个字符 合并解码**，（如字符串"22"，对于第2个“2”，解码当前字符相对于（2，2）=>BB， 与前一个字符合并解码为（22）=>V） 那么遍历这个字符串，对于i个字符，有以下情况： 1）**字符为数字1~9**，说明可以解码当前字符； 判断能否与前一个字符合并： 1）如果第i-1个字符*10+ 当前字符 <=26，说明**当前字符可以与前一个 字符合并解码**，此时该字符的解码数=前i-1个+前i-2个。 2）如果不行，此时该字符的解码数=前i-1个。 2）**字符为0**，说明当前字符不能解码（因为0没有对应的字母），只能与前一个 字符合并解码，如果可以，那么第i个字符的解码数=前i-2个字符的解码数； 如果不行，返回0。

代码：dp[i] 保存第i-1个字符的解码数
public int numDecodings(String s){ if(s==null || s.length()==0) return 0; int len=s.length(); int[] dp=new int[len+1]; dp[0]=1; if(s.charAt(0)=='0') return 0; else dp[1]=1; //i is index of string //从1开始是为了防止下面s.charAt(i-1)报越界 for(int i=1; i

图解：
算法|LeetCode 91&&639 动态规划java
文章图片

2）639 解码方法2 难度：困难 这道题相对于91多了一个字符 * ，字符 * 可以代表1~9的任意数字。方法不是很难，大致思路都是一样的，大家不用畏难，冲！！！
分析：
老套路，从头开始遍历字符串S，对于第i个字符： 1）**第i个字符为 *** ，先考虑单独解码 1.1 单独解码：*** 表示 1~9 中任意一个数字**，对应 A-I 中的任意一个字母。前i个 字符的解码可以表示在前i-1个字符的结尾加上 A-I 中任意一个字母，因此前i 个字符的解码数=9*前i-1个字符的解码数，即**dp[i] +=dp[i-1]*9; ** 1.2 合并解码。合并解码有3种情况，前一个字符为1，2，*； 1.2.1 **前一个字符为1**，那么他们可以表示 11~19 中任意一个数字，对应字母 为 K-S ，即在前i-2个字符的结尾加上 K-S 任意一个字母，因此**dp[i] +=6 * dp[i-1]** 1.2.2**前一个字符为2**，即2*，可以表示 21~26 上任意一个数字，对应U~Z中 任意一个字母，因此，**dp[i] +=6 * dp[i-2]** 1.2.3 **前一个字符为***，那么 ** 可以表示 11~19 以及 21~26，对应字母就是 A~I 以及 U~Z，此时相对于在前i-2个字符的结尾加上A~I或者U~Z，因此 **dp[i] +=15 * dp[i-2]** 2) **第i个字符为数字**。首先考虑单个数字解码的情况。 2.1 如果字符为 1~9，此时前i个字符的解码数=前i-1个字符的解码数 2.2 如果字符为0，此时只能与前一个字符合并解码。前一个字符是1、2、*才可以 解码，具体情况如下： 2.2.1 前一个字符为1，此时对应 10~19 任意一个数字，前i个字符解码数=前i-2个字符解码数； 2.2.2 前一个字符为2，有效数字为 20~26。只有当前字符小于7，前i个字符的解码数=前i-2个字符解码数； 2.2.3 前一个字符为*，解码数取决于当前字符。如果当前字符小于7，那么 * 可以是1或者2，当前解码数=前i-2个解码数的两倍；如果当前字符大于7，那么 * 只能是 1，此时解码数=前i-2个解码数；

代码：
public intnumDecodings(String s){ if(s==null || s.length()==0) return 0; int len=s.length(); int M=(int)Math.pow(10,9)+7; //dp[i] 表示第i-1个字符的解码数 long[] dp=new long[len+1]; dp[0]=1; if(s.charAt(0)=='0') return 0; else if(s.charAt(0)=='*') dp[1]=9; else dp[1]=1; //i is index of string for(int i=1; i6)//*只能为1 dp[i+1] = (dp[i+1] + dp[i-1]) % M; else//*可以为1 也可以为2 dp[i+1] = ( dp[i+1] + dp[i-1]*2 ) % M; } } } return (int)dp[len]; }

【算法|LeetCode 91&&639 动态规划java】图解字符串s=“12**610”，dp初始化为{ 1,1,0,0,0,0,0,0,0 }
算法|LeetCode 91&&639 动态规划java
文章图片

算法|LeetCode 91&&639 动态规划java
文章图片

    推荐阅读


    上一篇：Django Admin站点的使用

    下一篇：本周小记