【牛客】NC116把数字翻译成字符串
浏览 58 | 评论 0 | 字数 1436
TTQ
2022年04月25日
  • 原题链接:https://www.nowcoder.com/practice/046a55e6cd274cffb88fc32dba695668

    描述

    有一种将字母编码成数字的方式:'a'->1, 'b->2', ... , 'z->26'。
    我们把一个字符串编码成一串数字,再考虑逆向编译成字符串。 由于没有分隔符,数字编码成字母可能有多种编译结果,例如 11 既可以看做是两个'a' 也可以看做是一个 'k' 。但 10 只可能是 'j' ,因为 0 不能编译成任何结果。 现在给一串数字,返回有多少种可能的译码结果

    思路

    容易看出翻译数字存在两种情况:只翻译一位或翻译两位,对于只翻译一位的情况,如果存在0,则无法单独翻译;那么对于翻译两位的情况,当第一位为0时无法翻译。
    接着从整体视角来看:如果存在0,那么它的前面必须是1或2,否则无法翻译,直接返回0。
    然后我们先从简单情况考虑,如2221,容易看到可以以2 2 2 1翻译,对于前两位可以组成22翻译,即22 2 1
    对于第二、第三位也可以组成22翻译,即XX 22 2 1;对于第三、第四位可以组成21翻译,即XXX 21
    那么我们可以发现:首先可以确定一种最细翻译方式,接着从第三位开始组合前两位检查它们是否能够被翻译,如果能翻译,那么就可以将前两位作为一组进行翻译,便将dp[i]=dp[i-1]+dp[i-2],否则dp[i]=dp[i-1]

    代码

    function solve(nums) {
      if (nums == "0") {
        // nums为0时直接返回0
        return 0;
      }
      if (nums == "10" || nums == "20") {
        // nums为10或20时只有1种翻译方式
        return 1;
      }
      // 先遍历一遍判断有0的地方前面是不是1或2,如果不是1或2则无法翻译,返回0
      for (let i = 1; i < nums.length; i++) {
        if (nums[i] == "0") if (nums[i - 1] != "1" && nums[i - 1] != "2") return 0;
      }
      // 初始化dp数组
      let dp = new Array(nums.length + 1);
      dp[0] = dp[1] = 1;
    
      for (let i = 2; i <= nums.length; i++) {
        if (
          // 11-19||21-26时dp[i]=dp[i-1]+dp[i-2]
          (nums[i - 2] == "1" && nums[i - 1] != "0") ||
          (nums[i - 2] == "2" && nums[i - 1] > 0 && nums[i - 1] < 7)
        )
          dp[i] = dp[i - 1] + dp[i - 2];
        else dp[i] = dp[i - 1];
      }
      return dp[nums.length];
    }
    本文作者:TTQ
    本文链接:https://blog.ponder.fun/archives/152.html
    最后修改时间:2022-04-25 17:27:08
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    与本文无关评论请发留言板。请不要水评论,谢谢。
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论