剑指offer46-把数字翻译成字符串

原题

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

示例1:

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

提示:

  • 0 <= num < 231

解法

思想

动态规划:

可以使用leetcode70-爬楼梯的思想,每次翻译一位数看成跳一步,翻译两位数看成跳两步,那么对于任意要跳的一个位置来说,例如12258中的8,由于最后两位是58不能翻译,也就是只能由1225跳过来,此时f(12258)==f(1225),而对于1225,由于最后两位是25可以翻译,所以可以从12跳过来,也可以从122跳过来,此时f(1225) == f(12)+f(122)。将这两种情况一般化就能得出结论:

代码

class Solution {
    public int translateNum(int num) {
        if(num == 0) return 1;
        if(num < 10) return 1;
        int left = num%10;
        //去除最后一位数的last
        int last = num/=10;
        //计算出最后两位数的大小
        left = 10*(num%10)+left;
        //去除最后两位数的lastOfLast
        int lastOfLast = num /= 10;
        if(left>25||left<10) return translateNum(last);
        else return translateNum(last)+translateNum(lastOfLast);
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer46-%e6%8a%8a%e6%95%b0%e5%ad%97%e7%bf%bb%e8%af%91%e6%88%90%e5%ad%97%e7%ac%a6%e4%b8%b2/

发表回复

登录后才能评论