Algorithm-Guide/code/46.java at master · Xunzhuo/Algorithm-Guide · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
class Solution {
    public int translateNum(int num) {
        if(num<0)

        {
            return 0;

        }

        if(num<10)

        {
            return 1;

        }

        int n=num,k=0;

        while(n!=0)

        {
            k++;

            n/=10;

        }

        k--;

        int dp[] = new int[k+1];

        dp[0]=1;

        StringBuilder sb = new StringBuilder();

        for(int i=k;i>=0;i--)

        {
            int x = (int)((num/Math.pow(10,i))%10);

            //  System.out.println(x);

            sb.append(x);

        }

        //System.out.println(k+" "+sb);

        if(k>=1)

        {
            if(sb.charAt(0)=='1'||(sb.charAt(0)=='2'&&sb.charAt(1)<'6'))

                dp[1]=2;

            else

                dp[1]=1;

        }

        else

        {
            dp[1] = 1;

        }

        for(int i=2;i<=k;i++)

        {
            if(i>1)

            {
                if(sb.charAt(i-1)=='0'||sb.charAt(i-1)>'2')

                {
                    dp[i] = dp[i-1];

                }

                else if(sb.charAt(i-1)=='2'&&sb.charAt(i)>='6')

                {
                    dp[i] = dp[i-1];

                }

                else

                {
                    dp[i] = dp[i-2]+dp[i-1];

                }

            }

        }

        return dp[k];

    }

}