把数字翻译成字符串

发表于 更新于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

LeetCode每日一题，面试题46. 把数字翻译成字符串LCOF

先看题目描述

算法和思路

  • 这道题用动态规划就可以解决，一个个添加数字即可

  • 动态规划方程: res[0] = 1，若前两个数字可以组合成一个字母，res[1] = 2，若不能，res[1] = 1

    若新添加的数字和前一个数字能组合成一个字母，则 res[i] = res[i - 1] + res[i - 2]，若不能，res[i] = res[i - 1]，

  • 由于相邻两个数字才能组成一个字母，则当添加第 i 个数字时，若第 i 个数字不能与第 i - 1 个数字组成一个字母，则相当于在前 i - 1 个数字的翻译组合基础上加上第 i 个数字代表字母，此时 res[i] = res[i - 1]；若第 i 个数字能与第 i - 1 个数字组合成一个字母，则翻译有两种情况，一种是相当于在前 i - 1 个数字的翻译组合基础上加上第 i 个数字代表字母，另一种是相当于在前 i - 2 个数字的翻译组合基础上加上第 i - 1 个数字和第 i 个数字组合成的字母，此时 res[i] = res[i - 1] + res[i - 2]

  • 例：输入 12258，先添加 1，res[0] = 1，再添加 2 ，由于 1 和 2 能组合成一个字母，则 res[1] = 2，再添加 2，由于 2 和 2 能组合成一个字母，则 res[2] = res[0] + res[1] = 3，再添加 5，由于 2 和 5 能组成一个字母，则 res[3] = res[1] + res[2] = 5，再添加 8，由于 5 和 8 不能组成一个字母，则 res[4] = res[3] = 5，最终返回 res[4] 即可

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;

class Solution {
    public int translateNum(int num) {
        if (num < 10) return 1;
        String nums = String.valueOf(num);
        int[] res = new int[nums.length()];
        res[0] = 1;
        if (num/Math.pow(10, nums.length()-2) < 26) res[1] = 2;
        else res[1] = 1;
        for (int i = 2; i < nums.length(); i++) {
            int value = ((nums.charAt(i - 1) - '0')*10 + (nums.charAt(i)) - '0');
            if (value < 26 && value >= 10) res[i] = res[i - 1] + res[i - 2];
            else res[i] = res[i - 1];
        }
        return res[nums.length()-1];
    }
}

顺便纪念一下第一次成绩这么好