1. 代码段小站首页
  2. 算法

剑指offer46-把数字翻译成字符串

彭晨涛 • • 算法 • 阅读 9

原题

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

示例1:

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

提示:

  • 0 <= num < 231

解法

思想

动态规划：

可以使用leetcode70-爬楼梯的思想，每次翻译一位数看成跳一步，翻译两位数看成跳两步，那么对于任意要跳的一个位置来说，例如12258中的8，由于最后两位是58不能翻译，也就是只能由1225跳过来，此时f(12258)==f(1225)，而对于1225，由于最后两位是25可以翻译，所以可以从12跳过来，也可以从122跳过来，此时f(1225) == f(12)+f(122)。将这两种情况一般化就能得出结论：

代码

class Solution {
    public int translateNum(int num) {
        if(num == 0) return 1;
        if(num < 10) return 1;
        int left = num%10;
        //去除最后一位数的last
        int last = num/=10;
        //计算出最后两位数的大小
        left = 10*(num%10)+left;
        //去除最后两位数的lastOfLast
        int lastOfLast = num /= 10;
        if(left>25||left<10) return translateNum(last);
        else return translateNum(last)+translateNum(lastOfLast);
    }
}

原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e5%89%91%e6%8c%87offer46-%e6%8a%8a%e6%95%b0%e5%ad%97%e7%bf%bb%e8%af%91%e6%88%90%e5%ad%97%e7%ac%a6%e4%b8%b2/

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年2月29日 22:40
下一篇 2020年3月1日 16:33

相关推荐

  • leetcode167-两数之和II-输入有序数组

    原题 给定一个已按照 升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值index1和index2，其中index1必须小于index2。 说明...

    彭晨涛 彭晨涛
    算法 2019年11月20日
    0150

  • leetcode77-组合

    原题 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [...

    彭晨涛 彭晨涛
    算法 2020年5月12日
    0430

  • leetcode200-岛屿数量

    原题 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水...

    彭晨涛 彭晨涛
    算法 2019年11月24日
    0130

  • leetcode66-加一

    原题 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以...

    彭晨涛 彭晨涛
    算法 2019年11月14日
    0130

  • leetcode999-车的可用捕获量

    原题 999. 车的可用捕获量 - 力扣（LeetCode） 解法 思想 这道题题目有点难理解，其实就是上下左右搜索，质量有点低了。 代码 class Solution { cha...

    彭晨涛 彭晨涛
    算法 2020年3月26日
    070
  • 二叉树中序遍历-折纸问题 算法

    二叉树中序遍历-折纸问题

    原题（来源牛客网） 请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯...

    彭晨涛 彭晨涛
    2020年4月27日
    02470

  • 程序员面试金典17.01-不用加号的加法

    原题（来源Leetcode） 设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。 示例: 输入: a = 1, b = 1 输出: 2 提示： a, b 均可能是负数或...

    彭晨涛 彭晨涛
    算法 2020年6月9日
    0560

  • leetcode561-数组拆分I

    原题 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从1 到 n 的 min(ai, b...

    彭晨涛 彭晨涛
    算法 2019年11月18日
    070
  • leetcode279-完全平方数 算法

    leetcode279-完全平方数

    原题 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出...

    彭晨涛 彭晨涛
    2019年12月11日
    0120

  • leetcode394-字符串解码

    原题 给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意...

    彭晨涛 彭晨涛
    算法 2019年12月13日
    080

发表回复

登录后才能评论