46. 把数字翻译成字符串【难】

2024-09-04 04:12
文章标签 字符串 数字 46 翻译成

本文主要是介绍46. 把数字翻译成字符串【难】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9846.%20%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/README.md

面试题 46. 把数字翻译成字符串

题目描述

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

 

示例 1:

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

 

提示:

  • 0 <= num < 231

解法

方法一:记忆化搜索

我们先将数字 num 转为字符串 s s s,字符串 s s s 的长度记为 n n n

然后我们设计一个函数 d f s ( i ) dfs(i) dfs(i),表示从第 i i i 位数字开始的不同翻译的数目。那么答案就是 d f s ( 0 ) dfs(0) dfs(0)

函数 d f s ( i ) dfs(i) dfs(i) 的计算如下:

  • 如果 i ≥ n − 1 i \ge n - 1 in1,说明已经翻译到最后一个数字,只有一种翻译方法,返回 1 1 1
  • 否则,我们可以选择翻译第 i i i 位数字,此时翻译方法数目为 d f s ( i + 1 ) dfs(i + 1) dfs(i+1)如果第 i i i 位数字和第 i + 1 i + 1 i+1 位数字可以组成一个有效的字符(即 s [ i ] = = 1 s[i] == 1 s[i]==1 或者 ( s [ i ] = = 2 s[i] == 2 s[i]==2 s [ i + 1 ] < 6 s[i + 1] \lt 6 s[i+1]<6)),那么我们还可以选择翻译第 i i i 和第 i + 1 i + 1 i+1 位数字,此时翻译方法数目为 d f s ( i + 2 ) dfs(i + 2) dfs(i+2)。因此 d f s ( i ) = d f s ( i + 1 ) + d f s ( i + 2 ) dfs(i) = dfs(i+1) + dfs(i+2) dfs(i)=dfs(i+1)+dfs(i+2)

过程中我们可以使用记忆化搜索,将已经计算过的 d f s ( i ) dfs(i) dfs(i) 的值存储起来,避免重复计算。

时间复杂度 O ( log ⁡ n u m ) O(\log num) O(lognum),空间复杂度 O ( log ⁡ n u m ) O(\log num) O(lognum)。其中 n u m num num 为给定的数字。

Python3
class Solution:def translateNum(self, num: int) -> int:@cachedef dfs(i):if i >= n - 1: #第i-1位数字往后只有一种翻译方式return 1ans = dfs(i + 1)if s[i] == "1" or (s[i] == "2" and s[i + 1] < "6"):#核心:当有两位数字且不大于26时,就会出现两种翻译方式,从而翻译种数dfs(i)=dfs(i+1)+dfs(i+1)ans += dfs(i + 2)return anss = str(num)n = len(s)return dfs(0)
Java
class Solution {private int n;private char[] s;private Integer[] f;public int translateNum(int num) {s = String.valueOf(num).toCharArray();n = s.length;f = new Integer[n];return dfs(0);}private int dfs(int i) {if (i >= n - 1) {return 1;}if (f[i] != null) {return f[i];}int ans = dfs(i + 1);if (s[i] == '1' || (s[i] == '2' && s[i + 1] < '6')) {ans += dfs(i + 2);}return f[i] = ans;}
}
C++
class Solution {
public:int translateNum(int num) {string s = to_string(num);int n = s.size();int f[12]{};function<int(int)> dfs = [&](int i) -> int {if (i >= n - 1) {return 1;}if (f[i]) {return f[i];}int ans = dfs(i + 1);if (s[i] == '1' || (s[i] == '2' && s[i + 1] < '6')) {ans += dfs(i + 2);}return f[i] = ans;};return dfs(0);}
};
Go
func translateNum(num int) int {s := strconv.Itoa(num)n := len(s)f := [12]int{}var dfs func(int) intdfs = func(i int) int {if i >= n-1 {return 1}if f[i] != 0 {return f[i]}ans := dfs(i + 1)if s[i] == '1' || (s[i] == '2' && s[i+1] < '6') {ans += dfs(i + 2)}f[i] = ansreturn ans}return dfs(0)
}
TypeScript
function translateNum(num: number): number {const s = num.toString();const n = s.length;const f = new Array(n).fill(0);const dfs = (i: number): number => {if (i >= n - 1) {return 1;}if (f[i]) {return f[i];}let ans = dfs(i + 1);if (s[i] === '1' || (s[i] === '2' && s[i + 1] < '6')) {ans += dfs(i + 2);}f[i] = ans;return ans;};return dfs(0);
}
Rust
impl Solution {pub fn translate_num(num: i32) -> i32 {let mut a = 1;let mut b = 1;let str = num.to_string();for i in 0..str.len() - 1 {let c = a + b;a = b;let num = str[i..i + 2].parse::<i32>().unwrap();if num >= 10 && num < 26 {b = c;}}b}
}
JavaScript
/*** @param {number} num* @return {number}*/
var translateNum = function (num) {const s = num.toString();const n = s.length;const f = new Array(n).fill(0);const dfs = i => {if (i >= n - 1) {return 1;}if (f[i]) {return f[i];}let ans = dfs(i + 1);if (s[i] === '1' || (s[i] === '2' && s[i + 1] < '6')) {ans += dfs(i + 2);}f[i] = ans;return ans;};return dfs(0);
};
C#
public class Solution {public int TranslateNum(int num) {var s = num.ToString();int n = s.Length;int a = 1, b = 1;for (int i = 1; i < n; ++i) {int c = b;if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] < '6')) {c += a;}a = b;b = c;}return b;}
}
Swift
class Solution {private var n: Int = 0private var s: [Character] = []private var memo: [Int?] = []func translateNum(_ num: Int) -> Int {s = Array(String(num))n = s.countmemo = [Int?](repeating: nil, count: n)return dfs(0)}private func dfs(_ i: Int) -> Int {if i >= n - 1 {return 1}if let cachedResult = memo[i] {return cachedResult}var ans = dfs(i + 1)if s[i] == "1" || (s[i] == "2" && s[i + 1] < "6") {ans += dfs(i + 2)}memo[i] = ansreturn ans}
}

方法二:动态规划

我们可以将方法一中的记忆化搜索改为动态规划。

定义 f [ i ] f[i] f[i] 表示前 i i i 个数字的不同翻译的数目,那么答案就是 f [ n ] f[n] f[n]。初始化 f [ 0 ] = 1 f[0] = 1 f[0]=1, f [ 1 ] = 1 f[1] = 1 f[1]=1

我们可以从前往后计算 f [ i ] f[i] f[i] 的值,对于每个 i i i,我们可以选择翻译第 i i i 个数字,此时翻译方法数目为 f [ i − 1 ] f[i - 1] f[i1];如果第 i − 1 i-1 i1 个数字和第 i i i 个数字可以组成一个有效的字符(即 s [ i − 1 ] = = 1 s[i - 1] == 1 s[i1]==1 或者 s [ i − 1 ] = = 2 s[i - 1] == 2 s[i1]==2 s [ i ] < 6 s[i] \lt 6 s[i]<6),那么我们还可以选择翻译第 i − 1 i - 1 i1 和第 i i i 个数字,此时翻译方法数目为 f [ i − 2 ] f[i - 2] f[i2]。因此 f [ i ] = f [ i − 1 ] + f [ i − 2 ] f[i] = f[i-1] + f[i-2] f[i]=f[i1]+f[i2]

由于 f [ i ] f[i] f[i] 只与 f [ i − 1 ] f[i - 1] f[i1] f [ i − 2 ] f[i - 2] f[i2] 有关,因此我们可以只用两个变量来存储 f [ i − 1 ] f[i - 1] f[i1] f [ i − 2 ] f[i - 2] f[i2] 的值,从而省去数组 f f f 的空间。

时间复杂度 O ( log ⁡ n u m ) O(\log num) O(lognum),空间复杂度 O ( log ⁡ n u m ) O(\log num) O(lognum)。其中 n u m num num 为给定的数字。

Python3
class Solution:def translateNum(self, num: int) -> int:s = str(num)n = len(s)a = b = 1for i in range(2, n+1):c = bif s[i - 2] == '1' or (s[i - 2] == '2' and s[i-1] < '6'):#注意:第i个数字对应第i-1位c += aa, b = b, creturn b
Java
class Solution {public int translateNum(int num) {char[] s = String.valueOf(num).toCharArray();int n = s.length;int a = 1, b = 1;for (int i = 1; i < n; ++i) {int c = b;if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] < '6')) {c += a;}a = b;b = c;}return b;}
}
C++
class Solution {
public:int translateNum(int num) {string s = to_string(num);int n = s.size();int a = 1, b = 1;for (int i = 1; i < n; ++i) {int c = b;if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] < '6')) {c += a;}a = b;b = c;}return b;}
};
Go
func translateNum(num int) int {s := strconv.Itoa(num)n := len(s)a, b := 1, 1for i := 1; i < n; i++ {c := bif s[i-1] == '1' || (s[i-1] == '2' && s[i] < '6') {c += a}a, b = b, c}return b
}
TypeScript
function translateNum(num: number): number {const s = num.toString();const n = s.length;let a = 1;let b = 1;for (let i = 1; i < n; ++i) {let c = b;if (s[i - 1] === '1' || (s[i - 1] === '2' && s[i] < '6')) {c += a;}a = b;b = c;}return b;
}
Rust
impl Solution {fn dfs(s: &String, i: usize, res: &mut i32) {if i >= s.len() {return;}let val = s[i - 1..=i].parse::<i32>().unwrap();if val >= 10 && val <= 25 {*res += 1;Self::dfs(s, i + 2, res);}Self::dfs(s, i + 1, res);}pub fn translate_num(num: i32) -> i32 {let s = num.to_string();let mut res = 1;Self::dfs(&s, 1, &mut res);res}
}
JavaScript
/*** @param {number} num* @return {number}*/
var translateNum = function (num) {const s = num.toString();const n = s.length;let a = 1;let b = 1;for (let i = 1; i < n; ++i) {let c = b;if (s[i - 1] === '1' || (s[i - 1] === '2' && s[i] < '6')) {c += a;}a = b;b = c;}return b;
};

这篇关于46. 把数字翻译成字符串【难】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1134965

相关文章

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

C和指针:字符串

字符串、字符和字节 字符串基础 字符串就是一串零个或多个字符,并且以一个位模式为全0的NUL字节结尾。 字符串长度就是字符串中字符数。 size_t strlen( char const *string ); string为指针常量(const修饰string),指向的string是常量不能修改。size_t是无符号数,定义在stddef.h。 #include <stddef.h>

PHP字符串全排列

方法一: $str = 'abc';$a =str_split($str);perm($a, 0, count($a)-1);function perm(&$ar, $k, $m) {if($k == $m){ echo join('',$ar), PHP_EOL;}else {for($i=$k; $i<=$m; $i++) {swap($ar[$k], $ar[$i]);perm($ar

PHP7扩展开发之字符串处理

前言 这次,我们来看看字符串在PHP扩展里面如何处理。 示例代码如下: <?phpfunction str_concat($prefix, $string) {$len = strlen($prefix);$substr = substr($string, 0, $len);if ($substr != $prefix) {return $prefix." ".$string;} else

AIGC6: 走进腾讯数字盛会

图中是一个程序员,去参加一个技术盛会。AI大潮下,五颜六色,各种不确定。 背景 AI对各行各业的冲击越来越大,身处职场的我也能清晰的感受到。 我所在的行业为全球客服外包行业。 业务模式为: 为国际跨境公司提供不同地区不同语言的客服外包解决方案,除了人力,还有软件系统。 软件系统主要是提供了客服跟客人的渠道沟通和工单管理,内部管理跟甲方的合同对接,绩效评估,BI数据透视。 客服跟客人

十一、C语言:字符串函数

目录 一、strlen 二、strcpy 三、strcat  四、strcmp 五、strstr 六、strtok 七、strerror 一、strlen 注意:strlen()函数的返回值是size_t,两个size_t相减仍为无符号数 int main(){char arr[10] = "abc";char brr[10] = "abc123";if (strl

NC 把数字翻译成字符串

系列文章目录 文章目录 系列文章目录前言 前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你的码吧。 描述 有一种将字母编码成数字的方式:‘a’->1, ‘b->2’, … , ‘z->26’。 现在给一串数字,返回有多少种可能的译码结果 import java.u

34465A-61/2 数字万用表(六位半)

34465A-61/2 数字万用表(六位半) 文章目录 34465A-61/2 数字万用表(六位半)前言一、测DC/AC电压二、测DC/AC电流四、测电阻五、测电容六、测二极管七、保存截图流程 前言 1、6位半数字万用表通常具有200,000个计数器,可以显示最大为199999的数值。相比普通数字万用表,6位半万用表具有更高的测量分辨率和更高的测量准确度,适用于精度比较高的测