剑指offer46. 把数字翻译成字符串(斐波那契数列)

题解

• 题意：给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。现在给定一个输入是一个int数字num，编程计算一个数字有多少种不同的翻译方法。

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

• 题解：这题和斐波那契数列有点类似，为了方便，我们利用num[i]表示第i位数字
  • 当num[i-1]>2的时候，翻译方案数是不会增加的，因为这个字符只能翻译成一种情况，因此当nums[i]>5时候，我们只需要延续当前的数字即可即f[i] = f[i-1]
  • 当num[i-1] == 1 || num[i-1]==2&&nums[i]<=5的时候，方案数会增加，因为i-1可能与i结合，那么此时的方案数如何计算呢？这个问题可以进行分类讨论
    • 情况1：num[i-1]不与num[i]结合，那么它就属于num[0,i-1]这个子串，除了这个子串以外，还剩余一个数字num[i]，因此这种的方案数为f[i-1]
    • 情况2：num[i-1]归属于[i-1,i]这个子串，由于必须结合，因此不会增加翻译方案，此时方案数为[0,i-2]的所有方案，即f[i-2]
    • 总数：f[i] = f[i-1]+f[i-2]
• 实现，非递归

class Solution {
    public int translateNum(int num) {
        int cnt = 1; 
        int f1 = 1, f2 = 1;
        String s = String.valueOf(num);
        for(int i = 1;i < s.length();i++){
            if(s.charAt(i-1) == '1' || (s.charAt(i-1) == '2'&&s.charAt(i) <= '5') )
                cnt = f1 + f2;
            else cnt = f1;
            f2 = f1;
            f1 = cnt;
        }
        return cnt;
    }
}

• 递归

class Solution {
    public int translateNum(int num) {
        int cnt = 1;
        if(num == 0) return 1;
        int res = num%100;
        if(res/10 == 1 || (res/10 == 2 && res%10 <= 5)) return translateNum(num/10) + translateNum(num/100);
        return translateNum(num/10);
    }
}

• 把数字翻译成字符串