MarsCode--字符串有多少种可能性【简单】

问题描述

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

输入格式

一个 int 型的数字，0 <= num <= 2 的 31 次方

输出格式

也是一个 int 型数字，代表字符串的总共可能性

输入样例

输入: 12258

输出样例

输出: 5

解释: 12258 有 5 种不同的翻译，分别是 “bccfi”, “bwfi”, “bczi”, “mcfi” 和 “mzi”

分析

要解决这个问题，我们需要找到数组中一段连续的区间，使得这些元素的乘积尽可能大。由于数组中的元素都是2的幂，乘积会增长得非常快，因此这个问题实际上是要找到一段区间，使得这些2的幂的乘积最大。

我们可以通过以下步骤来解决这个问题：

初始化变量：我们需要一个变量来记录当前的最大乘积，以及对应的区间开始和结束位置。
遍历数组：使用两个指针来表示当前考虑的区间，并计算该区间的乘积。
更新最大值：如果当前区间的乘积大于之前的最大乘积，则更新最大乘积和对应的区间。
处理边界条件：当乘积为0时，需要特别处理。

完整代码

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int solution(int num) {
    if (num < 0) return 0;  // 处理非法输入

    string numStr = to_string(num);
    int n = numStr.size();
    if (n == 0) return 0;  // 处理空字符串

    vector<int> dp(n + 1, 0);
    dp[0] = 1;  // 初始条件
    dp[1] = 1;  // 初始条件

    for (int i = 2; i <= n; ++i) {
        // 当前数字单独翻译
        dp[i] = dp[i - 1];

        // 当前数字和前一个数字组合翻译
        int twoDigits = stoi(numStr.substr(i - 2, 2));
        if (twoDigits >= 10 && twoDigits <= 25) {
            dp[i] += dp[i - 2];
        }
    }

    return dp[n];
}

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;
}