用c++写出一个只含数字的非空字符串s,请计算并返回解码方法的总数的完整代码。题目数据保证答案肯定是一个32位的整数,并能在DEV中运行运行
时间: 2023-07-16 17:13:46 浏览: 39
以下是使用动态规划求解的代码:
```cpp
#include <iostream>
#include <string>
using namespace std;
int numDecodings(string s) {
if (s.empty() || s[0] == '0') {
return 0;
}
int n = s.size();
int prev = 1, curr = 1;
for (int i = 1; i < n; i++) {
int temp = curr;
if (s[i] == '0') {
if (s[i - 1] == '1' || s[i - 1] == '2') {
curr = prev;
} else {
return 0;
}
} else {
if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] >= '1' && s[i] <= '6')) {
curr = curr + prev;
}
}
prev = temp;
}
return curr;
}
int main() {
string s = "226";
cout << numDecodings(s) << endl; // 输出3
return 0;
}
```
其中,变量 `prev` 表示前一个数字的解码方法数,变量 `curr` 表示当前数字的解码方法数。在每次循环中,我们根据 `s[i]` 和 `s[i-1]` 的值来更新 `curr` 和 `prev`,然后继续循环。最终返回 `curr` 即可。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)