通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            jpress从3.x升级到4.x,显示有些问题,慢慢修复中

leetcode 剑指 Offer 46. 把数字翻译成字符串

308人浏览 / 0人评论 / | 作者:whisper  | 分类: 剑指offer2  | 标签: 剑指offer2  | 

作者:whisper

链接:https://www.proprogrammar.com/article/892

声明:请尊重原作者的劳动,如需转载请注明出处


剑指 Offer 46. 把数字翻译成字符串

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

示例 1:

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

提示:

  • 0 <= num < 231

难度:中等;标签:无;编程语言:C++


我的解法

class Solution {
public:
    int translateNum(int num) {
        if(num < 10)return 1;
        int dp[12] = {0};
        dp[0] = 1;
        int index = 1;
        int pre = num % 10;
        num /= 10;
        int cur;
        while(num > 0){
            cur = num % 10;
            if(cur == 0 || cur > 2 || (cur == 2 && pre > 5)){
                dp[index] = dp[index - 1];
            }else if(index > 1){
                dp[index] = dp[index - 1] + dp[index - 2];
            }else{
                dp[index] = 2;
            }

            num /= 10;
            pre = cur;
            index++;
        }

        return dp[index - 1];
    }
};

这是一道动态规划问题,方法是这样的

1、从右向左进行动态规划,如果当前是0,那么当前位置和前一个位置数量相同,如果当前是1,那么当前位置是前两个位置之和,如果当前是2,如果前一个位置是0~5,那么也是前两个位置之和,否则和前一个位置数量相同,如果大于2,也是和前一个位置数量相同

2、为什么呢,比如当前是2,如果前一个位置是4,那么以当前为结束位置,可以为2,或者24,即分为两类(分类),为2时的数量即前一个位置的数量,为24即前二个位置的数量,两者相加

3、上面没有考虑边界情况,如当前位置是第一个位置,具体处理看代码


其它解法

class Solution {
public:
    int translateNum(int num) {
        string str = to_string(num);
        int p = 0;
        int q = 0;
        int r = 1;
        for(int i = 0; i < str.length(); ++i){
            p = q;
            q = r;
            r = q;
            if(i == 0) continue;
            else{
                string s = str.substr(i-1,2);
                if(s <= "25" && s >= "10"){
                    r += p;
                }
            }
        }
        return r;
    }
};

这里去掉了dp数组,因为当前位置只与之前的两个位置有关,所以只要3个变量,保存当前位置与之前两位置的数量就行了,这里当前位置事先加上前一个位置的数量(由我的解法的分析,是一定会加上的),如果当前位置和前一个位置组成的两位数在10到25之间,那么还要加上之前第二个位置,有了第一份代码的基础,再看这一份代码会容易点


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告