网站域名备案服务,wordpress 积分支付,大数据培训班需要多少钱,重庆新媒体运营公司有哪些文章目录 题目题目分析思路解法正常解法优化解法 题目
题目链接#xff1a;力扣 91. 解码方法 备用链接#xff1a;https://leetcode.cn/problems/decode-ways/description/
题目分析
1.首先我们知道题目给定A~Z编码为1 ~26 #xff0c;而数字十一字符串的形式给出所以… 文章目录 题目题目分析思路解法正常解法优化解法 题目
题目链接力扣 91. 解码方法 备用链接https://leetcode.cn/problems/decode-ways/description/
题目分析
1.首先我们知道题目给定A~Z编码为1 ~26 而数字十一字符串的形式给出所以需要转换成整型 2.在解码部分我们可以了解到分为两种可能 1单独一个数字能否解码如图
2两个数字能否解码如图 3.返回是解法的总数 4.字符串s的范围在1 ~ 100之间 5.字符串s 只包含数字并且可能包含前导零
思路
首先我们想到用动态规划的解法 那么进入动态规划几个基本步骤 1. 确定dp状态表示什么 一般来说在dp问题中都是以i位置为起点表示什么什么或者以i位置为结尾表示什么什么… 那么我们就想一下这道题是正常给的字符串s我们解码的时候从左向右解码所以我们就这样来确定 dp[i]以i为结尾时解码方法的总数
2. 状态转移方程的表示 我们可以分为两种情况如图
解读
单独解码的时候只有数字在1 ~ 9 之间才有对应字母即解码成功单独解码时候一个字母解码成功不代表全解码成功而我们dp[i]的意思是以i为结尾时解码方法的总数那么之后到达最后一个字符s[i]也解码成功才算一种方法所以相较于i-1的解码只是在后面又加了一个字符进行判断能否成功解码所以成功也还是dp[i-1]解码失败那么前面的解码都白费所以就不加 dp[i-1]这种方法组合解码数字在10 ~ 26而不是0 ~ 26是防止“06”/“01”等这种情况最后dp[i]的状态转移方程就是dp[i]if(1 ~ 9 ){dp[i-1]}if(10 ~ 26){dp[i-2]}如果单独解码成功则加dp[i-1]如果组合解码成功就加dp[i-2]
3. 初始化 因为我们会用到 i -1 和 i - 2 所以我们初始化的时候要初始化dp[0]和dp[1]两个 4. 填表方向 我们要先知道dp[i-2],dp[i-1]才能推出dp[i]所以方向是从左向右
5. 返回值 返回dp[size-1],给定字符串的最后一项
解法
正常解法
class Solution {
public:int numDecodings(string s) {int sizes.size();int dp[110]{0};int num100,num10,num0;if(s[0]!0) dp[0]1;if(size1) return dp[0];//如果字符串s中只有一个字符那个只有一种情况直接返回if(s[1]!0s[0]!0) dp[1]1;num10s[0]-0,num1s[1]-0,numnum10*10num1;//i-1作为十位i作为个位if(num10num26) dp[1]1;for(int i2;isize;i){if(s[i]!0) dp[i]dp[i-1];//解码成功加dp[i-1]num10s[i-1]-0,num1s[i]-0,numnum10*10num1;if(num10num26) dp[i]dp[i-2];//解码成功加dp[i-2]}return dp[size-1];//返回最后一个总数减一}
};优化解法
在上面的代码中我们初始化和正常的填表操作有很大的重复所以我们改进一下 我们人为添加一个dp[0]的虚拟位其余位依次向下挪一位这样在填表的操作中就能实现从第二位开始填表
这种方法的注意事项
下标的映射关系
我们在多加了一个虚拟下标之后就等于dp的位多了一位所以我们在获取s的时候要s[i-1]才能获取到对应dp[i]的s的值。
人为填写的值要正确一般情况下都是0本题就要计算下
我们填写的时候dp[2]dp[1]dp[0]dp[1]是不会出错的dp[2]我们又能直接算出来所以dp[0]我们就可以直接得到本题dp[0]要填1。
class Solution {
public:int numDecodings(string s) {int sizes.size();int dp[110]{0};int num100,num10,num0;dp[0]1;if(s[1-1]!0) dp[1]1;if(size1) return dp[1];for(int i2;isize;i){if(s[i-1]!0) dp[i]dp[i-1];num10s[i-1-1]-0,num1s[i-1]-0,numnum10*10num1;if(num10num26) dp[i]dp[i-2];}return dp[size];}
};
