1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 46 题] “把数字翻译成字符串”做题记录

[剑指 Offer 第 2 版第 46 题] “把数字翻译成字符串”做题记录

第 46 题:把数字翻译成字符串

传送门:把数字翻译成字符串

给定一个数字,我们按照如下规则把它翻译为字符串:

0 翻译成 “a”,1 翻译成 “b”,……,11 翻译成“l”,……,25 翻译成 “z”。

一个数字可能有多个翻译。例如 12258 有 5 种不同的翻译,它们分别是 “bccfi”、“bwfi”、“bczi”、“mcfi” 和 “mzi”。

请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

样例:

输入:"12258"

输出:5

思路:同 LeetCode 第 91 题 Decode Ways。使用动态规划。状态:dp[i] 表示 s[0,i] (包括 i ),一共有多少种翻译的方法。分类讨论:1、当前字符可以单独翻译;2、当前字符可以和前面一个字符一起翻译。dp[i] 就是以上二者之和。

Python 代码:

  class Solution:
        def getTranslationCount(self, s):
            """
            :type s: str
            :rtype: int
            """
            s = str(s)
            l = len(s)
            if l == 0:
                return 0
            dp = [None for _ in range(l)]

            # dp[i] 表示 s[0,i] ,包括 i ,一共有多少种翻译的方法

            dp[0] = 1
            for i in range(1, l):
                # 当前值至少是 dp[i-1],因为 s[i] 一定可以单独翻译
                cur = dp[i - 1]

                # 看一看 s[i-1,i] 是不是可以翻译
                if 9 < int(s[i - 1:i + 1]) < 26:
                    if i - 2 < 0:
                        # 12
                        cur += 1
                    else:
                        # 要考虑到数组下标越界问题
                        cur += dp[i - 2]
                dp[i] = cur
            return dp[l - 1]

LeetCode 第 91 题:解码方法

传送门:91. 解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码:

'A' -> 1 'B' -> 2 ... 'Z' -> 26

给定一个只包含数字的非空字符串,请计算解码方法的总数。

示例 1:

输入: &quot;12&quot; 输出: 2 解释: 它可以解码为 &quot;AB&quot;(1 2)或者 &quot;L&quot;(12)。

示例 2:

输入: &quot;226&quot; 输出: 3 解释: 它可以解码为 &quot;BZ&quot; (2 26), &quot;VF&quot; (22 6), 或者 &quot;BBF&quot; (2 2 6) 。

Python 代码:

  # 91、解码方法
    # 一条包含字母 A-Z 的消息通过以下方式进行了编码:
    #
    # 'A' -> 1
    # 'B' -> 2
    # ...
    # 'Z' -> 26
    # 给定一个只包含数字的非空字符串,请计算解码方法的总数。


    class Solution:

        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """

            l = len(s)
            if l == 0:
                return 0

            if l == 1:
                return 1 if s[0] != '0' else 0
            dp = [0 for _ in range(l)]
            dp[0] = 1 if s[0] != '0' else 0
            for i in range(1, l):
                if s[i] != '0':
                    # 如果不是 '0' ,那么 s[i] 就可以编码,所以 cur 就至少是  dp[i-1]
                    dp[i] += dp[i - 1]
                if 9 < int(s[i - 1:i + 1]) < 27:
                    # 可以和前面的数字组成一个编码
                    if i - 2 < 0:
                        # 12
                        dp[i] += 1
                    else:
                        dp[i] += dp[i - 2]
            return dp[l - 1]


    if __name__ == '__main__':
        test_str = '12'
        s = Solution()
        res = s.numDecodings(test_str)
        print(res)

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 46 题] “把数字翻译成字符串”做题记录

链接:https://www.javajike.com/article/3292.html

« [剑指 Offer 第 2 版第 45 题] “把数组排成最小的数”做题记录
[剑指 Offer 第 2 版第 47 题] “礼物的最大值”做题记录»

相关推荐

QR code