数据结构学习 jz46把数字翻译成字符串

2024-01-03 16:38:37

关键词:动态规划 字符串 数组 滚动数组优化

这道题还算简单,调滚动数组废了点时间,dp状态和转移方程比较容易推出。

用时28mins。

题目:

思路:

把ciphertext拆成一个一个数字的方法:

求10的余数得到最低一位的数。

求10的商相当于把最低一位的数去掉。

外面可以套个循环,判断条件是ciphertext 不为零
{
int pre = ciphertext % 10;
ciphertext /= 10;
}

注意这样得到的第一个数是个位数。?

dp状态:

dp[i]:倒数第i个数以后的数(包括倒数第i个数)可以组成的解密结果的个数。

比如:

?初始状态:

因为需要知道dp[i-1] dp[i-2],所以得保证i>1,但是实际试过发现i>0即可。

转移方程:

这里分两种情况:

1、curr*10+pre>=26?

说明和前一个数没法组成一个小于26的数,没法一起解密。

那就只能单独解密:dp[i]=dp[i-1]

2、curr*10+pre<26

说明和前一个数可以组成一个小于26的数,可以一起解密。

那就既可以单独解密,也可以和前一个数一起解密:dp[i]=dp[i-1]+dp[i-2]

复杂度计算:

时间复杂度O(n)

空间复杂度O(1) 滚动数组优化

代码:

class Solution {
public:
    int crackNumber(int ciphertext) {
        std::vector<int> dp(3);
        if (ciphertext / 10 == 0)return 1;
        dp[0] = 1;
        dp[1] = 1;
        int pre = ciphertext % 10;//取最后一位
        ciphertext /= 10;//把最后一位去掉
        while (ciphertext)
        {
            int curr = ciphertext % 10;
            dp[2] = dp[1];
            if (curr!=0&&pre + curr*10 < 26)
                dp[2] += dp[0];
            pre = curr;//后面都是为下一次滚动、循环做准备
            ciphertext /= 10;
            dp[0] = dp[1];
            dp[1] = dp[2];
        }
        return dp[2];
    }
};

文章来源:https://blog.csdn.net/rainssssss/article/details/135363687
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。