题目要求:
给定一个数字,按照如下规则翻译成字符串:0翻译成“a”,1翻译成“b”...25翻译成“z”。一个数字有多种翻译可能,例如12258一共有5种,分别是bccfi,bwfi,bczi,mcfi,mzi。实现一个函数,用来计算一个数字有多少种不同的翻译方法。
网站制作、成都网站制作的开发,更需要了解用户,从用户角度来建设网站,获得较好的用户体验。成都创新互联多年互联网经验,见的多,沟通容易、能帮助客户提出的运营建议。作为成都一家网络公司,打造的就是网站建设产品直销的概念。选择成都创新互联,不只是建站,我们把建站作为产品,不断的更新、完善,让每位来访用户感受到浩方产品的价值服务。
# -*- coding: utf-8 -*-
# @Time : 2019-07-10 21:13
# @Author : Jayce Wong
# @ProjectName : job
# @FileName : getTranslationCount.py
# @Blog : https://blog.51cto.com/jayce1111
# @Github : https://github.com/SysuJayce
def getTranslationCount(number):
"""
要将一个数字转化成一个字符串,由于这个数字有很多位,我们最直观的就是从头开始,一位一位地去转化。
比如给定12258. 我们可以先把1翻译成b,然后剩下2258;也可以先把12翻译成m,然后剩下258.。。
由此可见是一个递归问题,用递归的思路分析题目,用循环来解决问题(动态规划)
递推公式为:f(i) = f(i+1) + g(i, i+1) x f(i+2)
其中f(i)表示到下标为i的数字为止,共有多少种可能的翻译。之所以写成向前递推的公式,是因为如果我
们从前往后翻译,会出现很多重复的子问题,比如12258=1 | 2258,其中2258=2 | 258,而12258=12 | 258,
这样258就重复了。
所以我们从后往前翻译,就可以避免这样的重复子问题。
"""
def helper(s):
# 一个数字至少有一种翻译,因此可以先设置一个全为1的数组,长度对应数字的位数加一
counts = [1] * (len(s) + 1)
# 对于前面的n-1位
for i in range(len(s) - 2, -1, -1):
# 第i位至少有和第i+1位一样多的翻译数
count = counts[i + 1]
# 如果第i位和第i+1位可以组合成一个10-25的数字,那么g(i, i+1) = 1
# f(i) = f(i+1) + g(i, i+1) x f(i+2)
# 由于我们设置的数组长度是位数+1,因此这里i+2不可能越界
if 10 <= int(s[i: i + 2]) <= 25:
count += counts[i + 2]
counts[i] = count
return counts[0]
# 由于0对应a,25对应z,因此小于0的输入是无效的
if number < 0:
return 0
return helper(str(number))
网站标题:剑指offer:把数字翻译成字符串
文章源于:https://www.cdcxhl.com/article40/ghpceo.html
成都网站建设公司_创新互联,为您提供定制网站、品牌网站建设、网站制作、网站改版、动态网站、网站排名
声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联