微信公众号:路人zhang
扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 算法 > 剑指offer > 剑指offer 46.把数字翻译成字符串
本文链接:https://www.mianshi.online/2763.html

题目描述

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

示例 1:

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

提示:

  • 0 <= num < 2^{31}

题解

(动态规划) O(n)

状态表示:f[i],表示将前 i 个数字翻译成字符串的方案数 状态计算

  1. 将当前数字翻译成单个字母,此时 f[i] 等于将前 i – 1 个数字翻译成字符串的方案数,f[i] = f[i - 1]
  2. 如果当前数字和前一个数字构成的两位数 val 满足 10 <= val <= 25,则可以将前一个数字和当前数字翻译成一个字母,此时 f[i] 等于将前 i – 2 个数字翻译成字符串的方案数,f[i] = f[i - 2]

边界

  1. f[0] = 1,0 个数字方案数为 1,可以通过 f[1] 推出,1 个数字的翻译方式只有一种(将当前数字翻译成单个字母),所以由 f[i] = f[i - 1]f[0] = 1
  2. f[n] 就是答案

注意:枚举字符串时 i 从 1 开始,所以下标应该往前移一位,即第 i 个字符 s[i – 1]。

时间复杂度

整个字符串被遍历一次,所以时间复杂度为 O(n)

空间复杂度

O(n)

C++ 代码

class Solution {
public:
    int translateNum(int num) {
        string s = to_string(num);
        int n = s.size();
        vector<int> f(n + 1);
        f[0] = 1;
        for (int i = 1; i <= n; i ++ ) {
            f[i] = f[i - 1];
            if (i >= 2) {
                int val = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
                if (val >= 10 && val <= 25)
                    f[i] += f[i - 2];
            }
        }
        return f[n];
    }
};

Java 代码

class Solution {
    public int translateNum(int num) {
        String s = String.valueOf(num);
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i ++ ) {
            f[i] = f[i - 1];
            if (i >= 2) {
                int val = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
                if (val >= 10 && val <= 25) {
                    f[i] += f[i - 2];
                }
            }
        }
        return f[n];
    }
}

Python 代码

class Solution:
    def translateNum(self, num):
        s = str(num)
        n = len(s)
        f = [0] * (n + 1)
        f[0] = 1
        for i in range(1, n + 1):
            f[i] = f[i - 1]
            if i >= 2:
                val = int(s[i - 2:i])
                if 10 <= val <= 25:
                    f[i] += f[i - 2]
        return f[n]

本文由读者提供Github地址:https://github.com/tonngw


点击面试手册,获取本站面试手册PDF完整版