东莞网站建设都找菲凡网络,网站动态页面,广告设计网课,有道搜索1.题目
问题描述
小M获得了一个任务#xff0c;需要将数字翻译成字符串。翻译规则是#xff1a;0对应a#xff0c;1对应b#xff0c;依此类推直到25对应z。一个数字可能有多种翻译方法。小M需要一个程序来计算一个数字有多少种不同的…1.题目
问题描述
小M获得了一个任务需要将数字翻译成字符串。翻译规则是0对应a1对应b依此类推直到25对应z。一个数字可能有多种翻译方法。小M需要一个程序来计算一个数字有多少种不同的翻译方法。
例如数字12258可以翻译成 bccfi, bwfi, bczi, mcfi 和 mzi共5种方式。 测试样例
样例1 输入num 12258 输出5 样例2 输入num 1400112 输出6 样例3 输入num 2110101 输出10 样例4 输入num 25 输出2 样例5 输入num 1023 输出4 2.思路
**定义状态**dp[i]表示前i个字符可以翻译的方法数
状态转移
遍历到第i位最后一位可以翻译根据分步计数乘法原理dp[i]dp[i-1] 如果后两位小于26则后两位可以翻译还有一种情况根据分步计数加法原理dp[i]dp[i-1]dp[i-2] **初始化**dp[0]1
**目标状态**dp[n-1]
3.代码
#include iostream
#include string
#include vector
#include sstream
using namespace std;
int solution(int num) {// Please write your code here// 数字转字符串string str_num to_string(num);int n str_num.size(); //字符串的大小vectorint dp; //dp[i]表示到第i位有几种翻译方法dp[0] 1; //第一位有一种翻译方法for (int i 1; i n; i) {dp[i] dp[i - 1];// 判断后两位是否小于25string last_two_str to_string(str_num[i - 1]) to_string(str_num[i]);int last_two_int;stringstream(last_two_str) last_two_int;if (last_two_int 26) {dp[i] dp[i - 2];}}return dp[n - 1];
}int main() {// You can add more test cases herestd::cout (solution(12258) 5) std::endl;std::cout (solution(1400112) 6) std::endl;std::cout (solution(2110101) 10) std::endl;return 0;
}Segmentation fault (core dumped) 是一个常见的运行时错误通常是由于程序试图访问未分配的内存或试图访问已释放的内存导致的。以下是一些可能的原因和解决方法
可能的原因
数组越界访问数组时超出了数组的边界。
空指针解引用尝试访问一个空指针指向的内存。
未初始化的指针使用了一个未初始化的指针。
递归深度过大递归调用过深导致栈溢出。
内存泄漏分配的内存没有正确释放导致后续操作出错。
vectorint dp; 未初始化大小你在声明 dp 向量时没有指定大小这会导致在访问 dp[0] 时出现越界错误。string last_two_str to_string(str_num[i - 1]) to_string(str_num[i]); 错误to_string(str_num[i - 1]) 和 to_string(str_num[i]) 都是字符而不是数字直接拼接字符会导致错误的结果。dp[i - 2] 访问越界当 i 为 1 时dp[i - 2] 会访问 dp[-1]这会导致越界错误。考虑str_num[i-1]0的情况后两位仅小于26也不一定能翻译成字符还需要大于9
#include iostream
#include string
#include vector
#include sstream
using namespace std;
int solution(int num) {// Please write your code here// 数字转字符串string str_num to_string(num);int n str_num.size(); //字符串的大小vectorint dp(n, 0); //dp[i]表示到第i位有几种翻译方法dp[0] 1; //第一位有一种翻译方法for (int i 1; i n; i) {dp[i] dp[i - 1];// 判断后两位是否小于25string last_two_str str_num.substr(i - 1, 2); //取后两位if (stoi(last_two_str) 26 stoi(last_two_str) 9) {if (i 1) {dp[i] 1;}else{dp[i] dp[i - 2];}}}return dp[n - 1];
}int main() {// You can add more test cases herestd::cout (solution(12258) 5) std::endl;std::cout (solution(1400112) 6) std::endl;std::cout (solution(2110101) 10) std::endl;return 0;
}4.参考资料
《剑指 Offer》46. 把数字翻译成字符串【LeetCode 力扣官方题解】_哔哩哔哩_bilibili
