首页 > 试题广场 >

解码

[编程题]解码
  • 热度指数:4253 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

有一种将字母编码成数字的方式:'a'->1, 'b->2', ... , 'z->26'。

现在给一串数字,给出有多少种可能的译码结果。




输入描述:
编码后数字串


输出描述:
可能的译码结果数
示例1

输入

12

输出

2

说明

2种可能的译码结果(”ab” 或”l”)
示例2

输入

31717126241541717

输出

192

说明

192种可能的译码结果
动态规划。
这里做题为了节约时间先不考虑节约内存的建立备忘录方法,直接递归。
边际为f(一位数) = 1, f(两位数) = 2或1(当超过26时为1)
f(str) = f(str切掉最后一位) + f(str切掉最后两位) ,str切掉最后两位小于26
f(str) = f(str切掉最后一位) ,str切掉最后两位大于26
function f(str) {
str = str.toString() // 参数转成字符串
let arr = str.split('')
if (arr.length === 1) // 参数只有一位,那么返回的种类就一种
return 1
}
if (arr.length === 2) { // 参数字符串两位位,那种类就取决于这个两位数的大小
if (parseInt(arr[0] + arr[1]) <= 26) {
return 2 // 小于等于26就能转化为一个字母,那么就有两种字母对应方式
} else {
return 1 // 大于26就能转化为一个字母,那么只有一种字母对应方式
}
}
let arr1 = arr.concat() // 防止数组的引用传递,这里拷贝一份
arr1.pop() // 去掉后一位
let str1 = arr1.join('')
let arr2 = arr.concat()
if (parseInt(arr2.slice(-2).join('')) > 26) { // 判断被去掉的两位数是否大于26
return f(str1) // 递归,种类数仅有f(str切掉后一位)
} else {
arr2.pop()
arr2.pop()
let str2 = arr2.join('')
return f(str1) + f(str2)// 递归,种类数有f(str切掉后一位) + f(str切掉后2位)种
}
}

编辑于 2018-09-03 20:22:42 回复(1)
function jiema(num) {                  
  return jie1(String(num),0)                
}                
function jie1(num,i) {                  
 if(i>=num.length) {                  
   return 1                  
 }                  
 if(Number(num[i]) === 0) {              
   return 0                  
 }                  
 if(num[i+1] && Number(num[i])!==0 && (Number(num[i])*10 + Number(num[i+1]))<=26) {                  
   return jie1(num,i+1) +jie1(num,i+2)                 
 } else{                  
   return jie1(num,i+1)                 
 }                 
} 
最后出现了80%的通过率,好像复杂度过高

编辑于 2018-08-20 09:33:00 回复(2)