自律小屋

Appearance

当前页大纲

解题思路： ​

根据题意，可按照下图的思路，总结出 “递推公式” （即转移方程）。

Picture1.png

因此，此题可用动态规划解决，以下按照流程解题。

动态规划解析： ​

记数字 $num$ 第 $i$ 位数字为 $x_i$ ，数字 $num$ 的位数为 $n$ ； 例如： $num = 12258$ 的 $n = 5$ , $x_1 = 1$ 。

  • 状态定义： 设动态规划列表 $dp$ ，$dp[i]$ 代表以 $x_i$ 为结尾的数字的翻译方案数量。

  • 转移方程： 若 $x_i$ 和 $x_{i-1}$ 组成的两位数字可被整体翻译，则 $dp[i] = dp[i - 1] + dp[i - 2]$ ，否则 $dp[i] = dp[i - 1]$ 。

$$ dp[i] = \begin{cases} dp[i - 1] + dp[i - 2] & {, (10 x_{i-1} + x_i) \in [10,25]} \ dp[i - 1] & {, (10 x_{i-1} + x_i) \in [0, 10) \cup (25, 99]} \end{cases} $$

可被整体翻译的两位数区间分析： 当 $x_{i-1} = 0$ 时，组成的两位数无法被整体翻译（例如 $00, 01, 02, \cdots$ ），大于 $25$ 的两位数也无法被整体翻译（例如 $26, 27, \cdots$ ），因此区间为 $[10, 25]$ 。

  • 初始状态： $dp[0] = dp[1] = 1$ ，即 “无数字” 和 “第 $1$ 位数字” 的翻译方法数量均为 $1$ ；

  • 返回值： $dp[n]$ ，即此数字的翻译方案数量；

Q： 无数字情况 $dp[0] = 1$ 从何而来？ A： 当 $num$ 第 $1, 2$ 位的组成的数字 $\in [10,25]$ 时，显然应有 $2$ 种翻译方法，即 $dp[2] = dp[1] + dp[0] = 2$ ，而显然 $dp[1] = 1$ ，因此推出 $dp[0] = 1$ 。

方法一：字符串遍历 ​

  • 为方便获取数字的各位 $x_i$ ，考虑先将数字 $num$ 转化为字符串 $s$ ，通过遍历 $s$ 实现动态规划。
  • 通过字符串切片 $s[i - 2:i]$ 获取数字组合 $10 x_{i-1} + x_i$ ，通过对比字符串 ASCII 码判断字符串对应的数字区间。
  • 空间使用优化： 由于 $dp[i]$ 只与 $dp[i - 1]$ 有关，因此可使用两个变量 $a, b$ 分别记录 $dp[i]$ , $dp[i - 1]$ ，两变量交替前进即可。此方法可省去 $dp$ 列表使用的 $O(N)$ 的额外空间。

复杂度分析： ​

  • 时间复杂度 $O(N)$ ： $N$ 为字符串 $s$ 的长度（即数字 $num$ 的位数 $\log(num)$ ），其决定了循环次数。
  • 空间复杂度 $O(N)$ ： 字符串 $s$ 使用 $O(N)$ 大小的额外空间。

<Picture2.png,Picture3.png,Picture4.png,Picture5.png,Picture6.png,Picture7.png>

代码： ​

由于 Python 语言特性，可不使用临时变量 $tmp$ 和 $c$ ，若阅读不畅可转至第三栏代码。

Java
class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1, b = 1;
        for(int i = 2; i <= s.length(); i++) {
            String tmp = s.substring(i - 2, i);
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
}
C++
class Solution {
public:
    int translateNum(int num) {
        string s = to_string(num);
        int a = 1, b = 1, len = s.size();
        for(int i = 2; i <= len; i++) {
            string tmp = s.substr(i - 2, 2);
            int c = tmp.compare("10") >= 0 && tmp.compare("25") <= 0 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
};
Python
class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        a = b = 1
        for i in range(2, len(s) + 1):
            a, b = (a + b if "10" <= s[i - 2:i] <= "25" else a), a
        return a
Python
class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        a = b = 1
        for i in range(2, len(s) + 1):
            tmp = s[i - 2:i]
            c = a + b if "10" <= tmp <= "25" else a
            b = a
            a = c
        return a

此题的动态规划计算是 对称的 ，即 从左向右 遍历（从第 $dp[2]$ 计算至 $dp[n]$ ）和 从右向左 遍历（从第 $dp[n - 2]$ 计算至 $dp[0]$ ）所得方案数一致。从右向左遍历的代码如下所示。

Java
class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int a = 1, b = 1;
        for(int i = s.length() - 2; i > -1; i--) {
            String tmp = s.substring(i, i + 2);
            int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
}
C++
class Solution {
public:
    int translateNum(int num) {
        string s = to_string(num);
        int a = 1, b = 1, len = s.size();
        for(int i = len - 2; i > -1; i--) {
            string tmp = s.substr(i, 2);
            int c = tmp.compare("10") >= 0 && tmp.compare("25") <= 0 ? a + b : a;
            b = a;
            a = c;
        }
        return a;
    }
};
Python
class Solution:
    def translateNum(self, num: int) -> int:
        s = str(num)
        a = b = 1
        for i in range(len(s) - 2, -1, -1):
            a, b = (a + b if "10" <= s[i:i + 2] <= "25" else a), a
        return a

方法二：数字求余 ​

上述方法虽然已经节省了 $dp$ 列表的空间占用，但字符串 $s$ 仍使用了 $O(N)$ 大小的额外空间。

空间复杂度优化： ​

  • 利用求余运算 $num % 10$ 和求整运算 $num // 10$ ，可获取数字 $num$ 的各位数字（获取顺序为个位、十位、百位…）。
  • 运用 求余 和 求整 运算实现，可实现 从右向左 的动态规划计算。而根据上述动态规划 “对称性” ，可知从右向左计算是正确的。
  • 自此，字符串 $s$ 的空间占用也被省去，空间复杂度从 $O(N)$ 降至 $O(1)$ 。

复杂度分析： ​

  • 时间复杂度 $O(N)$ ： $N$ 为字符串 $s$ 的长度，即数字 $num$ 的位数 $\log(num)$ ，其决定了循环次数。
  • 空间复杂度 $O(1)$ ： 几个变量使用常数大小的额外空间。

<Picture8.png,Picture9.png,Picture10.png,Picture11.png,Picture12.png,Picture13.png,Picture14.png,Picture15.png,Picture16.png,Picture17.png,Picture18.png,Picture19.png,Picture20.png,Picture21.png>

代码： ​

由于 Python 语言特性，可不使用临时变量 $tmp$ 和 $c$ ，若阅读不畅可转至第三栏代码。

Java
class Solution {
    public int translateNum(int num) {
        int a = 1, b = 1, x, y = num % 10;
        while(num > 9) {
            num /= 10;
            x = num % 10;
            int tmp = 10 * x + y;
            int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
            b = a;
            a = c;
            y = x;
        }
        return a;
    }
}
C++
class Solution {
public:
    int translateNum(int num) {
        int a = 1, b = 1, x, y = num % 10;
        while(num > 9) {
            num /= 10;
            x = num % 10;
            int tmp = 10 * x + y;
            int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
            b = a;
            a = c;
            y = x;
        }
        return a;
    }
};
Python
class Solution:
    def translateNum(self, num: int) -> int:
        a = b = 1
        y = num % 10
        while num > 9:
            num //= 10
            x = num % 10
            a, b = (a + b if 10 <= 10 * x + y <= 25 else a), a
            y = x
        return a
Python
class Solution:
    def translateNum(self, num: int) -> int:
        a = b = 1
        y = num % 10
        while num > 9:
            num //= 10
            x = num % 10
            tmp = 10 * x + y
            c = a + b if 10 <= tmp <= 25 else a
            a, b = c, a
            y = x
        return a

MIT License.

Copyright © 2024 自律小屋