LeetCode题解91.decode-ways

题目地址

https://leetcode.com/problems/decode-ways/description/

题目描述

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

思路

这道题目和爬楼梯问题有异曲同工之妙。

这也是一道典型的动态规划题目。我们来思考：

• 对于一个数字来说[1,9]这九个数字能够被识别为一种编码方式
• 对于两个数字来说[10, 26]这几个数字能被识别为一种编码方式

我们考虑用dp[i]来切分子问题， 那么dp[i]表示的意思是当前字符串的以索引i结尾的子问题。
这样的话，我们最后只需要取dp[s.length] 就可以解决问题了。

关于递归公式，让我们先局部后整体。对于局部，我们遍历到一个元素的时候，
我们有两种方式来组成编码方式，第一种是这个元素本身（需要自身是[1,9]）,
第二种是它和前一个元素组成[10, 26]。 用伪代码来表示的话就是：
dp[i] = 以自身去编码（一位） + 以前面的元素和自身去编码（两位） .这显然是完备的，
这样我们通过层层推导就可以得到结果。

关键点解析

• 爬楼梯问题（我把这种题目统称为爬楼梯问题）

代码

/*
 * @lc app=leetcode id=91 lang=javascript
 *
 * [91] Decode Ways
 *
 * https://leetcode.com/problems/decode-ways/description/
 *
 * algorithms
 * Medium (21.93%)
 * Total Accepted:    254.4K
 * Total Submissions: 1.1M
 * Testcase Example:  '"12"'
 *
 * A message containing letters from A-Z is being encoded to numbers using the
 * following mapping:
 *
 *
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 *
 *
 * Given a non-empty string containing only digits, determine the total number
 * of ways to decode it.
 *
 * Example 1:
 *
 *
 * Input: "12"
 * Output: 2
 * Explanation: It could be decoded as "AB" (1 2) or "L" (12).
 *
 *
 * Example 2:
 *
 *
 * Input: "226"
 * Output: 3
 * Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2
 * 6).
 *
 */
/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function(s) {
  if (s == null || s.length == 0) {
    return 0;
  }
  const dp = Array(s.length + 1).fill(0);
  dp[0] = 1;
  dp[1] = s[0] !== "0" ? 1 : 0;
  for (let i = 2; i < s.length + 1; i++) {
     const one = +s.slice(i - 1, i);
     const two = +s.slice(i - 2, i);

    if (two >= 10 && two <= 26) {
      dp[i] = dp[i - 2];
    }

    if (one >= 1 && one <= 9) {
      dp[i] += dp[i - 1];
    }
  }

  return dp[dp.length - 1];
};

扩展

如果编码的范围不再是1-26，而是三位的话怎么办？

LeetCode题解计算机为什么是基于二进制的？

可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制

LeetCode题解统计城市的所有灯泡

这个是我刚毕业的时候，一个真实的面试题，这是一个开放题。题目描述：想办法，将一个城市的所有灯泡数量统计出来。题解：费米估算法1、如果某个城市常驻人口有1000万2、假设每5人居住在一套房里，每套房有灯泡5只，那么住宅灯泡共有1000万只3、假设公众场所每10人共享一只灯泡，那么共有100万只4、主要的这两者相加就得出了1100万只当然实际上这是估算的，具体应…

LeetCode题解黑白圆盘

一个圆盘被涂上了黑白二色，两种颜色各占一个半圆。圆盘以一个未知的速度、按一个未知的方向旋转。你有一种特殊的相机可以让你即时观察到圆上的一个点的颜色。你需要多少个相机才能确定圆盘旋转的方向?题解：可以用一个相机即可

LeetCode题解圆上任取三点构成锐角三角形的概率

来自字节跳动的一道几何题题解：1/4

LeetCode题解深度优先遍历和回溯的关系？

深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。