题目链接

把数字翻译成字符串

题目描述

注意

• 最终返回的是一个数字有多少种不同的翻译方法
• 字符串中的字符可能由一个或两个数字组成
• 数字能组成字符的范围是0~25

解答思路

• 先将数字中的每个数字添加进一个数组中
• 利用动态规划计算出不同数字数量翻译成字符串的翻译方法

代码

class Solution {
    public int translateNum(int num) {
        int tmp = num;

        // 数字长度
        int len = 0;
        while(tmp != 0) {
            len++;
            tmp = tmp / 10;
        }

        // 将数字存入到数组中
        int[] num1 = new int[len];
        for(int i = 0; i < len; i++) {
            num1[i] = num / (int) Math.pow(10, len - i - 1);
            num = num % (int) Math.pow(10, len - i - 1);         
        }
        
        int a = 1;
        int b = 1;
        int sum = 1;
        for(int i = 1; i < len; i++) {
            // 如果当前数字和上一个数字可以组成一个字符
            if(num1[i - 1] == 1 || (num1[i - 1] == 2 && num1[i] < 6)) {
                sum = a + b;
            }else {
                sum = b;
            }
            a = b;
            b = sum;
        }
        return sum;
    }
}

关键点

• 将数字中的每个数字添加进一个数组中
• 理解动态规划的思想，计算n个数字翻译成字符串的方法是：
  如果第n个数字能够和第n-1个数字组成一个字符，则其翻译方法有f(n - 1) + f(n - 2)种；否则其翻译方法只有f(n - 1)种.
• 两个数字组成一个字符时，其值必须在10~25之间