宁波网站建设服务,企业建设网站的优势,广州黄埔做网站公司,开一个个人网站多少钱剑指 Offer 46. 把数字翻译成字符串
中等
588
相关企业
给定一个数字#xff0c;我们按照如下规则把它翻译为字符串#xff1a;0 翻译成 “a” #xff0c;1 翻译成 “b”#xff0c;……#xff0c;11 翻译成 “l”#xff0c;……#xff0c;25 翻译成 “z”。一个数字…剑指 Offer 46. 把数字翻译成字符串
中等
588
相关企业
给定一个数字我们按照如下规则把它翻译为字符串0 翻译成 “a” 1 翻译成 “b”……11 翻译成 “l”……25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。示例 1:输入: 12258
输出: 5
解释: 12258有5种不同的翻译分别是bccfi, bwfi, bczi, mcfi和mzi下面是我自己的思路这应该算是深度优先搜索了…… 没有对比就没有伤害我佩服大佬们的思路。 这其实可看作经典的青蛙跳台问题 可以跳一层对应翻译一个数字到字符 也可以跳两层对应在满足一定条件下翻译两个数字到字符。
class Solution {int count;public int translateNum(int num) {// 26 letterscount0;char[] str String.valueOf(num).toCharArray();pro(str,0);return count;}public void pro(char[] str, int index){if(indexstr.length){count;return;}else if(indexstr.length){return;}// case 1: one charpro(str,index1);// case 2: two charsif(index1str.length isValid(str,index)){pro(str,index2);}}public boolean isValid(char[] str, int index){if(str[index]1){return true;}else if(str[index]2){if(str[index1]0 str[index1]5){return true;}else{return false;}}return false;}
}下面是参考过大佬们的解题思路后自己写的动态规划解法
class Solution {public int translateNum(int num) {//dp, dp[i], str[..i] #plansString s String.valueOf(num);char[] strs.toCharArray();if(str.length1){return 1;}int[] dp new int[str.length];dp[0]1;if( s.substring(0,2).compareTo(10)0 s.substring(0,2).compareTo(25)0){dp[1]2;}else{dp[1]dp[0];}for(int i2;idp.length;i){if(s.substring(i-1,i1).compareTo(10)0 s.substring(i-1,i1).compareTo(25)0){dp[i]dp[i-1]dp[i-2];}else{dp[i]dp[i-1];}}return dp[dp.length-1];}
}最后借鉴一下大佬们的代码 空间压缩后的动态规划原因是考虑到计算dp[i]时只使用到dp[i-1],dp[i-2]。 上图来自力扣K神。
class Solution {public int translateNum(int num) {String s String.valueOf(num);int a1; // pre , dp[0]int b1;// pre pre, dp[-1]for(int i1;is.length();i){String temp s.substring(i-1,i1);// [i-1,i]int c temp.compareTo(10)0 temp.compareTo(25)0 ?ab:a;// a: dp[i-1], b: dp[i-2]// move forward,preparation for next iterationba;ac;}return a;}
}
