Java日记2018-05-15

第一题 把数字翻译成字符串

image.png

以12258为例分析，f(i)代表能翻译的字符串个数，i是字符串的位置，f(0）代表在1这个位置的字符串个数，向右递归，f(1)就代表在2这个位置的字符串个数，当然f(2)在第索引2也是2的位置。因为最大字母翻译是26，这样代表翻译时最多可以两位翻译，比如12这个数字，既可以以1,2来翻译，也可以以12来翻译。这样f(0)位置的字符串翻译个数其实是f(0)=f(1)+f(2)，前面也提到走两步时候是否成立应该以在0，以及1这个位置的数字来判断，如果索引0,1位置大于25那么f(2)其实就不存在。推而广之f(n)=f(n+1)+g(n,n+1)*f(n+2)，g(n,n+1)代表索引n,n+1位置的数字是否大于25。于是就可以有以下算法

public class TranslateNumbersToStrings {
    public static int trans(int num){
        if(num<0) return 0;
        if(num<10) return 1;
        return transcore(Integer.toString(num));
    }
    
    public static int transcore(String num) {
        int f1=0;
        int f2=1;
        int temp=0;
        int g=0;
        System.out.println("begin");
        for(int i=num.length()-2;i>=0;i--) {
            if(Integer.parseInt(num.charAt(i)+""+num.charAt(i+1))>25) {
                g=0;
            } else {
                g=1;
            }
            temp = f2;
            f2= f2+g*f1;
            f1 = temp;
        }
        return f2;
    }
    
    public static void main(String[] args) {
        System.out.println(trans(12258));
    }

}