46. 把数字翻译成字符串
发布日期:2021-06-29 01:04:11
浏览次数:2
分类:技术文章
本文共 984 字,大约阅读时间需要 3 分钟。
文章目录
剑指 Offer 46. 把数字翻译成字符串
给定一个数字,我们按照如下规则把它翻译为字符串:0
翻译成“a”
,1
翻译成“b”
,……,11
翻译成 “l”
,……,25
翻译成 “z”
。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5 解释: 12258有5种不同的翻译,分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”
提示:
0 <= num < 2^31
解题思路
动态规划:
状态表示:dp[i]
表示前i
个数字有多少种翻译方法,则dp[n]
便表示前n
个数字有多少中翻译方法,即结果。
状态转移:
- 当把第
i
个数字单独翻译成一个字符时,相当于第i
个数字已经固定翻译成什么了,则整个数字串有dp[i - 1]
种翻译方法 - 当把第
i - 2
和第i-1
个数字合在一起翻译成一个字符时,则整个数字串有dp[i - 2]
种翻译方法,但此时应满足第i - 2
和第i-1
个数字合在一起能翻译成一个字符,即他们两个组成的数字在[10,25]
范围内才行。
Java代码
class Solution { public int translateNum(int num) { String s = num + ""; char[] chs = s.toCharArray(); int[] dp = new int[chs.length + 1];//前i个字符有多少种翻译方法 dp[0] = 1; dp[1] = 1; for(int i = 2;i <= chs.length;i++){ dp[i] = dp[i - 1]; int n = (chs[i - 2] - '0') * 10 + (chs[i - 1] - '0'); if(10 <= n && n <=25 ){ dp[i] += dp[i -2]; } } return dp[chs.length]; }}
转载地址:https://blog.csdn.net/YouMing_Li/article/details/114595214 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月10日 20时11分36秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Python爬虫+数据分析:了解北京Python开发的现状
2019-04-29
为什么要用Python来处理数据分析
2019-04-29
黑科技,老司机放码开车用Python等QQ邮箱发邮件
2019-04-29
python获取知乎问题答案并转换为MarkDown文件
2019-04-29
这十个小贴士可以让你的Python代码写的更加优雅
2019-04-29
Python爬取当当、京东、亚马逊图书信息代码实例
2019-04-29
Python爬虫抓取智联招聘(基础版)
2019-04-29
Python爬虫爬取智联招聘(进阶版)
2019-04-29
python爬虫:爬取拉勾网职位并分析
2019-04-29
Python爬虫+数据分析,2019年你想看的A股牛市都在这里了!
2019-04-29
Python爬虫工具:必会用的 6 款 Chrome 插件
2019-04-29
如何从海量抖音视频上找高颜值小姐姐,难吗!直到我发现了这个Python库
2019-04-29
让Python给你讲笑话、段子,一个有趣的Python案例
2019-04-29
用Python数据分析选购手机,双十一刚过你选对了嘛
2019-04-29
Python数据分析 I 全国旅游景点分析案例,哪里好玩一目了然
2019-04-29
九大神招,让Python里数据分析神器Jupyter,完美升华
2019-04-29
几行Python代码,轻松获取美股阿里巴巴的交易数据
2019-04-29
网传天猫双十一数据造假?利用Python对其进行预测分析
2019-04-29
Python文字转换语音,让你的文字会「说话」,抠脚大汉秒变撒娇萌妹
2019-04-29
天气变冷了,给你的爱人制作一个天气提醒小助手
2019-04-29