1. 把数字翻译成字符串

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

  1. 示例 1:
  3. 输入: 12258
  4. 输出: 5
  5. 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
  8. 提示：
  10. 0 <= num < 2 31

草稿：

  • 5位数：进行两两组合的最多个数为 5/2 = 2
    • 2：5+1-4 = 2
    • 1：5-1 = 4
    • 0： 1

  • 剔除其中大于25的，得到最后的结果数总数

  • 6位数：进行两两组合的最多个数为 6/2 = 3

    • 3： 6+1-6 = 1
    • 2：6+1-4 = 3
    • 1：6-1 = 5
    • 0： 1
  • 剔除其中大于25的，得到最后的结果数总数

思路：

  • 数字长度length
  • 算出两两组合可能最多的个数n = length / 2
  • 通过n进行循环，算出所有组合方法的总数total
    • 按照草稿里总结的规律
  • 循环根据不同的组合方式进行切片，然后判断剔除不满足条件的
    • 最外层循环n-1次
      • 以（0,n2）进行字符串切片， 然后依次（1,2n+1）,（2,2*n+2）…
        • 切出来的字符串，继续进行又一层循环切片，间隔是2，切出来一个，就转化成int进行判断是否大于25，如果大于，则total-1
  • 最后的total即为返回值

两两组合时漏掉了一部分，并且这部分已经无法符合上述规律。

思路：

使用动态规划，发现规律：
image.png

class Solution {
    public int translateNum(int num) {
        // int 转为 String
        String str = String.valueOf(num);
        // 初始化时a表示num为空,b表示num只有1位
        int a = 1,b = 1;
        // c表示翻译到第i位的有效翻译次数
        int c = 1;
        // 12258
        for(int i=2;i<=str.length();i++){
            String ex = str.substring(i-2,i);
            c = ex.compareTo("10")>=0 && ex.compareTo("25")<=0 ? a+b : b;
            a = b;
            b = c;            
        }
        return c;
    }
}