提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

把数字翻译成字符串（剑指offer 46）

2023-03-14 22:51:07 时间

一、题目描述


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


示例 1:

输入: 12258

输出: 5

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


提示：

0 <= num < 231


二、解题思路 

       

对于我这种算法小白来说，碰到这种题，第一反应就是动态规划 


只要能够按步骤画出表格来的，都可以用dp（动态规划来解），我们以12258为例


字符串方案数
11  （b）
122  （bc,j）
1223  （bcc,jc,bw）
12255  （bccf,jcf,bwf,bcz,jz）
122585  （bccfg,jcfg,bwfg,bczg,jzg）


你发现规律了吗？


我们将每行的方案数保存到dp[]数组中，不难发现：首先，后面加上来的数本身作为一个数字时，拥有dp[i-1]中方案；而假如后面加上来的数能够和原本末尾的数发生组合，那么就多出了dp[i-2]种方案，所以，我们可以得到dp的递推式：


当后加的数能和末尾的数字组合（两个数字组合不超过25）时，dp[i] = dp[i-1] + dp[i-2]；


当后加的数不能和末尾的数字组合（两个数字组合超过25）时 ，dp[i] = dp[i-1]


三、java代码实现


1、动态规划 

class Solution {
    public int translateNum(int num) {
        char []c = String.valueOf(num).toCharArray();
        int len = c.length;
        int []dp = new int[len+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<len+1; i++) {
            if(c[i-2]=='0') {
                dp[i] = dp[i-1];
                continue;
            }
            int temp = (c[i-2]-'0')*10+(c[i-1]-'0');
            if(temp>=0 && temp<=25) {
                dp[i] = dp[i-1] + dp[i-2];
            } else {
                dp[i] = dp[i-1];
            }
        }
        return dp[len];
    }
}


时间复杂度：        O(N)

       

空间复杂度：        O(N)


2、滚动数组优化空间

       

可以看到，dp数组当前位的结果只与他前两个位置有关，所以我们可以用三个变量来保存，节省dp数组的空间。

 

时间复杂度：        O(N)

       

空间复杂度：        O(N)


3、优化保存num的数组

       

由动态规划的对称性可知，我们从后往前来判断，跟从前往后判断，得到的结果是一致的。因此我们可以利用取余直接拿到最后的几位数，省去用于存放num的空间。

class Solution {
    public int translateNum(int num) {
        int a = 1, b = 1, x, y = num % 10;
        while(num != 0) {
            num /= 10;
            x = num % 10;
            int tmp = 10 * x + y;
            int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
            b = a;
            a = c;
            y = x;
        }
        return a;
    }
}


 时间复杂度：        O(N)

         

空间复杂度：        O(N)

相关文章