python每日一题【剑指 Offer 46. 把数字翻译成字符串】

day16-2022.11.10

题目信息来源
作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm
来源：力扣（LeetCode）

剑指 Offer 46. 把数字翻译成字符串

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

输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"```
1
2

题解

这个题和青蛙跳台阶很像，唯一区别就是跳两次台阶需要满足条件，即前一个数字和当前数字满足在10和25之间（包含10和25）。

注意字符串比较大小，是 '9'>'10'，字符串比较大小是先比较两个字符串的首位，首位相同比较下一位，而 10 的首位是 '1' 小于 '9'，所以 '9'>'10'。

class Solution:
    def translateNum(self, num: int) -> int:
        num = str(num)
        dp = [0]*(len(num)+1)
        dp[0] = 1
        for i in range(1, len(num)+1):
            if num[i-2]=='1' or (num[i-2]=='2' and num[i-1]<='5'):
                dp[i] = dp[i-1] + dp[i-2]
            else:
                dp[i] = dp[i-1]
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11

减少了一下内存的开销：

class Solution:
    def translateNum(self, num: int) -> int:
        if num<10:return 1
        num = str(num)
        dpi = 0
        dpi_1 = 1
        dpi_2 = 1
        for i in range(2, len(num)+1):
            if num[i-2]=='1' or (num[i-2]=='2' and num[i-1]<='5'):
                dpi = dpi_1 + dpi_2
            else:
                dpi = dpi_1
            dpi_2 = dpi_1
            dpi_1 = dpi
        return dpi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

本题其实从动态规划的角度去做是比较简单的，所以题目还设置了一个障碍是，如果从最高位到最低位遍历数字。上面的代码是直接用了 str() 进行了转换，而如果这样的转换受限应该怎么办？

在官方解释里：提供了数字取余取整的方法：

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

运用 求余 和 求整 运算实现，可实现 从右向左 的动态规划计算。而根据上述动态规划 “对称性” ，可知从右向左计算是正确的。