题目(难度:中等):
给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
输入: 12258
输出: 5
解释: 12258有5种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
2 | 2 | 0 | 5 |
---|---|---|---|
1 | 1+1->2 | 2+1->3 | 3 |
无论如何只要输入的不是空默认都会有一种结果
那我们先申明一个空的数组,用于存放对应指针指到当前字符串位置是存在的结果数
从索引为 1 即第二个字母开始遍历,如果这个字母和之前的字母组合起来满足:
/**
* @param {number} num
* @return {number}
*/
var translateNum = function (num) {
var Arr = String(num).split('')
var _result = []
for (var i = 1; i < Arr.length; i++) {
var itemNum = _result[i] || 1
// 前一个字母为0其实数据不变 需要忽略
if (Number(Arr[i - 1]) && Number(Arr[i - 1] + '' + Arr[i]) <= 25) {
_result[i + 1] = itemNum + (_result[i - 1] || 1)
} else {
_result[i + 1] = itemNum
}
}
return num.length ? _result[Arr.length] || 1 : 0
}
例如:输入 1402
每一位单独翻译,即 [1, 4, 0, 2][1,4,0,2],翻译的结果是 beac
然后我们考虑组合某些连续的两位:
如果第 i−1 位和第 i 位组成的数字在 10 到 25 之间,可以把这两位连起来翻译
我们可以用)f(i) 表示以第 i 位结尾的前缀串翻译的方案数,考虑第 i 位单独翻译和与前一位连接起来再翻译对 f(i) 的贡献。单独翻译对 f(i) 的贡献为 f(i−1);如果第 i−1 位存在,并且第 i−1 位和第 i 位形成的数字 x 满足 10≤x≤25, 那么就可以把第 i−1 位和第 i 位连起来一起翻译,对 f(i) 的贡献为 f(i−2),否则为 0。我们可以列出这样的动态规划转移方程:f(i)=f(i−1)+f(i−2)[i−1≥0,10≤x≤25]
边界条件是 f(−1)=0,f(0)=1。方程中 [c] 的意思是 c 为真的时候 [c]=1,否则 [c]=0。
有了这个方程我们不难给出一个时间复杂度为 O(n),空间复杂度为 O(n) 的实现。考虑优化空间复杂度:这里的 f(i) 只和它的前两项 f(i−1) 和 f(i−2) 相关,我们可以运用「滚动数组」思想把 f 数组压缩成三个变量,这样空间复杂度就变成了 O(1)。
/**
* @param {number} num
* @return {number}
*/
var translateNum = function (num) {
var p = 0,
q = 0,
r = 1
for (var i = 0; i < String(num).length; ++i) {
p = q
q = r
r = 0
r += q
if (i == 0) {
continue
}
var pre = String(num).substring(i - 1, i + 1)
if (Number(pre) <= 25 && Number(pre) > 10) {
r += p
}
}
return r
}
/**
* @param {number} num
* @return {number}
*/
var translateNum = function (num) {
if (num < 10) return 1
return num % 100 < 10 || num % 100 > 25
? translateNum(parseInt(num / 10))
: translateNum(parseInt(num / 10)) + translateNum(num / 100)
}
自然而然,我们举例描述了终止情况和递推关系,可以想到用递归方式。
/**
* @param {number} num
* @return {number}
*/
var translateNum = function (num) {
if (num < 10) return 1
else if (num < 26) return 2
else if (num < 100) return 1
else {
var ans = 0
var a = 1
while (num / 10 >= a) a *= 10
ans = ans + translateNum(num % a)
a /= 10
if (num / a < 26) ans = ans + translateNum(num % a)
return ans
}
}