C++实现LeetCode(91.解码方法)
[LeetCode] 91. Decode Ways 解码方法
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
这道题要求解码方法,跟之前那道 Climbing Stairs 非常的相似,但是还有一些其他的限制条件,比如说一位数时不能为0,两位数不能大于 26,其十位上的数也不能为0,除去这些限制条件,跟爬梯子基本没啥区别,也勉强算特殊的斐波那契数列,当然需要用动态规划 Dynamci Programming 来解。建立一维 dp 数组,其中 dp[i] 表示s中前i个字符组成的子串的解码方法的个数,长度比输入数组长多多1,并将 dp[0] 初始化为1。现在来找状态转移方程,dp[i] 的值跟之前的状态有着千丝万缕的联系,就拿题目中的例子2来分析吧,当 i=1 时,对应s中的字符是 s[0]='2',只有一种拆分方法,就是2,注意 s[0] 一定不能为0,这样的话无法拆分。当 i=2 时,对应s中的字符是 s[1]='2',由于 s[1] 不为0,那么其可以被单独拆分出来,就可以在之前 dp[i-1] 的每种情况下都加上一个单独的2,这样 dp[i] 至少可以有跟 dp[i-1] 一样多的拆分情况,接下来还要看其能否跟前一个数字拼起来,若拼起来的两位数小于等于26,并且大于等于 10(因为两位数的高位不能是0),那么就可以在之前 dp[i-2] 的每种情况下都加上这个二位数,所以最终 dp[i] = dp[i-1] + dp[i-2],是不是发现跟斐波那契数列的性质吻合了。所以0是个很特殊的存在,若当前位置是0,则一定无法单独拆分出来,即不能加上 dp[i-1],就只能看否跟前一个数字组成大于等于 10 且小于等于 26 的数,能的话可以加上 dp[i-2],否则就只能保持为0了。具体的操作步骤是,在遍历的过程中,对每个数字首先判断其是否为0,若是则将 dp[i] 赋为0,若不是,赋上 dp[i-1] 的值,然后看数组前一位是否存在,如果存在且满足前一位是1,或者和当前位一起组成的两位数不大于 26,则当前 dp[i] 值加上 dp[i - 2]。最终返回 dp 数组的最后一个值即可,代码如下:
C++ 解法一:
class Solution { public: int numDecodings(string s) { if (s.empty() || s[0] == '0') return 0; vector<int> dp(s.size() + 1, 0); dp[0] = 1; for (int i = 1; i < dp.size(); ++i) { dp[i] = (s[i - 1] == '0') ? 0 : dp[i - 1]; if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) { dp[i] += dp[i - 2]; } } return dp.back(); } };
Java 解法一:
class Solution { public int numDecodings(String s) { if (s.isEmpty() || s.charAt(0) == '0') return 0; int[] dp = new int[s.length() + 1]; dp[0] = 1; for (int i = 1; i < dp.length; ++i) { dp[i] = (s.charAt(i - 1) == '0') ? 0 : dp[i - 1]; if (i > 1 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))) { dp[i] += dp[i - 2]; } } return dp[s.length()]; } }
下面这种方法跟上面的方法的思路一样,只是写法略有不同:
C++ 解法二:
class Solution { public: int numDecodings(string s) { if (s.empty() || s[0] == '0') return 0; vector<int> dp(s.size() + 1, 0); dp[0] = 1; for (int i = 1; i < dp.size(); ++i) { if (s[i - 1] != '0') dp[i] += dp[i - 1]; if (i >= 2 && s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10") { dp[i] += dp[i - 2]; } } return dp.back(); } };
Java 解法二:
class Solution { public int numDecodings(String s) { if (s.isEmpty() || s.charAt(0) == '0') return 0; int[] dp = new int[s.length() + 1]; dp[0] = 1; for (int i = 1; i < dp.length; ++i) { if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1]; if (i >= 2 && (s.substring(i - 2, i).compareTo("10") >= 0 && s.substring(i - 2, i).compareTo("26") <= 0)) { dp[i] += dp[i - 2]; } } return dp[s.length()]; } }
我们再来看一种空间复杂度为 O(1) 的解法,用两个变量 a, b 来分别表示 s[i-1] 和 s[i-2] 的解码方法,然后从 i=1 开始遍历,也就是字符串的第二个字符,判断如果当前字符为 '0',说明当前字符不能单独拆分出来,只能和前一个字符一起,先将 a 赋为0,然后看前面的字符,如果前面的字符是1或者2时,就可以更新 a = a + b,然后 b = a - b,其实 b 赋值为之前的 a,如果不满足这些条件的话,那么 b = a,参见代码如下:
C++ 解法三:
class Solution { public: int numDecodings(string s) { if (s.empty() || s[0] == '0') return 0; int a = 1, b = 1, n = s.size(); for (int i = 1; i < n; ++i) { if (s[i] == '0') a = 0; if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) { a = a + b; b = a - b; } else { b = a; } } return a; } };
Java 解法三:
class Solution { public int numDecodings(String s) { if (s.isEmpty() || s.charAt(0) == '0') return 0; int a = 1, b = 1, n = s.length(); for (int i = 1; i < n; ++i) { if (s.charAt(i) == '0') a = 0; if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) <= '6')) { a = a + b; b = a - b; } else { b = a; } } return a; } }
到此这篇关于C++实现LeetCode(91.解码方法)的文章就介绍到这了,更多相关C++实现解码方法内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25