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

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

这道题还算简单，调滚动数组废了点时间，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];
    }
};