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

相关推荐

  • 剑指offer44-数字序列中某一位的数字

    原题（来源Leetcode） 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位...

    彭晨涛 彭晨涛
    算法 2020年6月15日
    02020

  • leetcode435-无重叠区间

    原题 给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。 注意: 可以认为区间的终点总是大于它的起点。 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没...

    彭晨涛 彭晨涛
    算法 2020年2月18日
    02270
  • leetcode234-回文链表 算法

    leetcode234-回文链表

    原题 请判断一个链表是否为回文链表。 示例1： 输入： 1->2 输出： false 示例2： 输入： 1->2->2->1 输出： true 进阶: 你能否用 O(n) 时间复杂...

    彭晨涛 彭晨涛
    2019年12月16日
    080

  • leetcode1413-逐步求和得到正数的最小值

    原题 给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。 你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums...

    彭晨涛 彭晨涛
    算法 2020年6月21日
    01870

  • leetcode260-只出现一次的数字III

    原题 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。 示例： 输入: [1,2,1,3,2,5] 输出: [3,5...

    彭晨涛 彭晨涛
    算法 2020年4月28日
    0110

  • leetcode83-删除排序链表中的重复元素

    今天打算多刷几道算法题 原题 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。 示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->...

    彭晨涛 彭晨涛
    算法 2020年6月16日
    0910

  • leetcode121-买卖股票的最佳时机

    原题 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。 注意你不能在...

    彭晨涛 彭晨涛
    算法 2020年3月9日
    080

  • leetcode278-第一个错误的版本

    原题 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。 假...

    彭晨涛 彭晨涛
    算法 2020年1月2日
    050

  • leetcode560-和为K的子数组

    原题 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1: 输入: nums = [1,1,1], k = 2 输出: 2 , [1,1]...

    彭晨涛 彭晨涛
    算法 2020年5月15日
    0410

  • leetcode347-前K个高频元素

    原题 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。 示例1： 输入： nums = [1,1,1,2,2,3], k = 2 输出： [1,2] 示例2： 输入： n...

    彭晨涛 彭晨涛
    算法 2019年12月28日
    0130

发表回复

登录后才能评论