当前位置：首页 > article >正文

54.数字翻译成字符串的可能性|Marscode AI刷题

article 2025/1/31 2:39:25

1.题目

问题描述

小M获得了一个任务，需要将数字翻译成字符串。翻译规则是：0对应"a"，1对应"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(); //字符串的大小
    vector<int> dp; //dp[i]表示到第i位有几种翻译方法
    dp[0] = 1; //第一位有一种翻译方法
    for (int i = 1; i < n; i++) {
        dp[i] = dp[i - 1];
        // 判断后两位是否小于25
        string 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 here
    std::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) 是一个常见的运行时错误，通常是由于程序试图访问未分配的内存或试图访问已释放的内存导致的。以下是一些可能的原因和解决方法：

可能的原因：

数组越界：访问数组时超出了数组的边界。

空指针解引用：尝试访问一个空指针指向的内存。

未初始化的指针：使用了一个未初始化的指针。

递归深度过大：递归调用过深，导致栈溢出。

内存泄漏：分配的内存没有正确释放，导致后续操作出错。

vector<int> 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(); //字符串的大小
    vector<int> dp(n, 0); //dp[i]表示到第i位有几种翻译方法
    dp[0] = 1; //第一位有一种翻译方法
    for (int i = 1; i < n; i++) {
        dp[i] = dp[i - 1];
        // 判断后两位是否小于25
        string 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 here
    std::cout << (solution(12258) == 5) << std::endl;
    std::cout << (solution(1400112) == 6) << std::endl;
    std::cout << (solution(2110101) == 10) << std::endl;

    return 0;
}