本问题对应的 leetcode 原文链接:剑指 Offer 46. 把数字翻译成字符串

问题描述

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

示例 1:

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

提示:

  • 0 <= num < 2^31

解题思路

视频讲解直达: 本题视频讲解

代码实现

class Solution {
    public int translateNum(int num) {
        if(num <= 9){
            return 1;
        }
        char[] arr = String.valueOf(num).toCharArray();
        int n = arr.length;
        //int[] dp = new int[n + 1];
        // f(n) = f(n-1) + f(n-2)
        int a = 1;
        int b = 1;
        int c = 1;
        // 优化 a,b,c
        for(int i = 2; i <= n; i++){
            // 计算第i和第i-1个字符的组合
            int tmp = 10 * (arr[i-2] - '0') + (arr[i-1] - '0');
            if(tmp >= 10 && tmp <= 25){
                c = a + b;
            }else{
                c = b;
            }
            //迭代
            a = b;
            b = c;
        }

        return c;
    }
}

Python

class Solution(object):
    def translateNum(self, num):
        """
        :type num: int
        :rtype: int
        """
        if num <= 9:
            return 1
        arr = list(str(num))
        n = len(arr)
        a = b = c = 1
        for i in range(1, n):
            tmp = int(arr[i-1] + arr[i])
            if 10 <= tmp <= 25:
                c = a + b
            else:
                c = b
            a, b = b, c

        return c

C++

class Solution {
public:
    int translateNum(int num) {
        if (num <= 9) {
            return 1;
        }
        string str = to_string(num);
        int n = str.size();
        int a = 1, b = 1, c = 1;
        for (int i = 1; i < n; i++) {
            int tmp = stoi(str.substr(i-1, 2));
            if (tmp >= 10 && tmp <= 25) {
                c = a + b;
            } else {
                c = b;
            }
            a = b;
            b = c;
        }
        return c;
    }
};

Go

func translateNum(num int) int {
    if num <= 9 {
        return 1
    }
    str := strconv.Itoa(num)
    n := len(str)
    a, b, c := 1, 1, 1
    for i := 1; i < n; i++ {
        tmp, _ := strconv.Atoi(str[i-1 : i+1])
        if tmp >= 10 && tmp <= 25 {
            c = a + b
        } else {
            c = b
        }
        a, b = b, c
    }
    return c
}

JS

/**
 * @param {number} num
 * @return {number}
 */
var translateNum = function(num) {
    if (num <= 9) {
        return 1;
    }
    let arr = String(num).split('');
    let n = arr.length;
    let a = 1;
    let b = 1;
    let c = 1;

    for (let i = 2; i <= n; i++) {
        // 计算第 i 和第 i-1 个字符的组合
        let tmp = 10 * parseInt(arr[i - 2]) + parseInt(arr[i - 1]);
        if (tmp >= 10 && tmp <= 25) {
            c = a + b;
        } else {
            c = b;
        }
        // 迭代
        a = b;
        b = c;
    }

    return c;
};

发表回复

后才能评论