Skip to content

Latest commit

 

History

History
66 lines (53 loc) · 2.13 KB

把数字翻译成字符串.md

File metadata and controls

66 lines (53 loc) · 2.13 KB

题目描述

给定一个数字,我们按照如下规则翻译成字符串:0 翻译成“a”,1 翻译成“b”... 25 翻译成“z”。一个数字有多种翻译可能,例如 12258 一共有 5 种,分别是 bccfi,bwfi,bczi,mcfi,mzi。实现一个函数,用来计算一个数字有多少种不同的翻译方法。

测试用例

  • 功能测试(只有一位数字;包含多位数字)
  • 特殊输入测试(输入的数字字符串指针为空指针)

题目考点

  • 考察应聘者分析问题的能力。应聘者能够从问题中分析出递归的表达式[f(i)=f(i-1) + g(i,i-1)f(i-2)]是解决这个问题的关键。
  • 考察应聘者对递归及时间效率的理解。面试官期待应聘者能够用基于循环的代码(动态规划)来避免不必要的重复计算。

解题思路

动态规划

假设数组dp[i]表示从头到字符串的第i位(不是字符串的下标),一共有多少种解码方法的话

首先我们一定能从第i-1位的解码方法上继续解码。那么就是dp[i] += dp[i-1];

除此之外如果字符串的第i-1位和第i位能组成一个10到25的数字,说明我们可以是在第i-2位的解码方法上继续解码。那么就是dp[i] += dp[i-2];

自己解题

没有抽象出来,抽象能力太差!!

参考解题

/**
 * 把数字翻译成字符串
 *
 * @Author rex
 * 2018/8/29
 */
public class Solution {
    /**
     * 动态规划
     * @param s
     * @return
     */
    public int numDecodings(String s) {

      // 防止特殊输入
      if (s == null || s.length() == 0) {
          return 0;
      }
      // 存储动态规划中间值
      int[] dp = new int[s.length()+1];

      // 为了dp[2] += dp[0] 而设置
      dp[0] = 1;
      dp[1] = 1;

      for (int i = 2; i <= s.length(); i++) {
          // 1. 肯定会发生
          dp[i] += dp[i-1];
          // 2. 当前位与前一位可以组成一个数字时
          if (Integer.parseInt(s.substring(i-2,i)) >=0 && Integer.parseInt(s.substring(i-2,i)) <=25) {
              dp[i] += dp[i-2];
          }


      }
      return dp[s.length()];
    }
}

补充

动态规划