LC面试题46. 把数字翻译成字符串

题目：

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

 

示例 1:

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

提示：

0 <= num < 2^31

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题写到最后，结果不对，脑子比较混乱还没有发现，后来发现公式定义有问题。

应该是
f(i)=f(i-1)或者f(i)=f(i-1)+f(i-2)
但是我写的时候，感觉是
f(i)=f(i-1)+1或者f(i)=f(i-1)+f(i-2)+1
【就是想着他自己也要统计一次，其实是多余的】，公式改过来就OK了
结果还不错
执行用时 :
0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :
6.2 MB, 在所有 C++ 提交中击败了100.00%的用户

class Solution {
public:
    int pow1(int num){
        int res=1;
        for(int i=0;i<num;i++){
            res=res*10;
        }
        return res;
    }
    int translateNum(int num) {// 0-25
        if(num<0)
            return 0;
        if(num<=25){
            if(num>=10){
                return 2;
            }else{
                return 1;
            }
        }
        if(num<100)
            return 1;
        //以下，三位数以上情况,得知道位数 留首位
        double len=(double)to_string(num).length();
        // cout<<len<<endl;
        int a=num%(pow1(len-1));//取后面的数
        int b=num/(pow1(len-2));//取前两位
        int res=translateNum(a);
        // cout<<a<<" "<<b<<" "<<num<<endl;
        if(b<=25){
            res+=translateNum(num%(pow1(len-2)));
        }
        //递推关系式想清楚
        //f(i)=f(i-1)或者f(i)=f(i-1)+f(i-2),这里开始没有理清楚
        //写写画画得到 除的关系。善用/和%
        return res;
   

    }
};