面试题46.把数字翻译成字符串 Leetcode刷题心得收获

一、问题描述
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”
提示：
0 <= num <2 31 2^{31} 231
二、解题思路
方法一：递归回溯今天的每日一题难度还可以，今天完成的比以往都要早。首先要理解这道题的意思，给定一个数字，可以按位翻译成对应的字母，有多个翻译的意思是例如123这个数字，可以每次取一位翻译成abc，也可以第一次选两位，第二次选一位翻译成lc，也可以第一次取一位，第二次取两位翻译成aw。因此我们可以得到以下结论：
1）每次可以选择一位或两位数字翻译
2）当第一次选择的数字为0时不能再选第二个数字（没有0开头的两位数）
3）当第一次选择的数字>2时不能再选第二个数字（最高到25）
4）当第一次选择的数字为2时，第二次选择的数字不能大于5（最高到25）
因此我们可以像求排列组合那样使用递归回溯法，每次递归都选择一个或两个数字，根据以上的规则建立递归：
1）每次递归都做一个循环，表示取1位或取两位。
2）当取一位时，递归到下一次的循环，重复以上过程直到所有的数字都已经被遍历过，开始回溯。
3）回溯时，中止最后的递归跳回上一层，此时判断这一层递归中第一次取得的数字，如果是0或>2的数字，那么就没有必要再取下一位了，因此直接结束循环回溯到上一层；如果是0或1，就继续取下一位。
4）如果前一位是2且第二位是>5的数字，那么就没有办法翻译成一个字母，因此也要结束循环回溯到上一层。
5）如果第二位也符合要求，那么继续向下一层递归，重复以上过程。
6）直到回溯至第一层执行完毕得到所有的结果。
方法二：取模递归这个方法是看评论区一位大佬的解法，从给定的数字中每次取出后两位，可以通过模100的方式取得，如果这两位数字<=9或者>=26，说明不能作为一个整体进行翻译，因此假设去掉最后一位，翻译的种类数也不会发生改变，因为最后一位只能单独翻译，所以和原数字/10的结果相同；如果数字在10~26之间说明最后两位可以作为一个整体进行翻译，因此当这两位作为一个整体翻译时，翻译的种类数和原数字/100相同，当最后一位单独翻译时和原数字/10相同，因此这种情况下的翻译种类数为原数字/10+原数字/100.
三、代码
回溯递归：

class Solution { private int sum=0; //记录种类数 public int translateNum(int num) { char[] nums=String.valueOf(num).toCharArray(); //通过一个char数组进行遍历 getTranslate(nums,0); return sum; }public void getTranslate(char[] nums,int index){ if(index==nums.length){//index表示正在遍历数组的下标 sum++; return; } for(int i=0; i<2&&index2)break; //没有必要取下一位了 else index++; } if(i==1){//取两位 if(nums[index-1]=='2'&&nums[index]-'0'>=6){//这两位>=26 break; }else{ getTranslate(nums,index+1); } } } } }

【面试题46.把数字翻译成字符串】取模递归：

class Solution { public int translateNum(int num) { if (num<=9) {return 1; } //获取输入数字的余数，然后递归的计算翻译方法 int ba = num%100; //如果大于9或者大于26的时候，余数不能按照2位数字组合，比如56，只能拆分为5和6；反例25，可以拆分为2和5，也可以作为25一个整体进行翻译。 if (ba<=9||ba>=26) {return translateNum(num/10); } else{return translateNum(num/10)+translateNum(num/100); } } }

四、结果