剑指offer面试题46(java版):把数字翻译成字符串

朱雀 2023-07-07 08:39 2阅读 0赞

### [welcome to my blog][] ###

## 剑指offer面试题46(java版):把数字翻译成字符串 ##

### 题目描述 ###

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成
    “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
    
    
    
    示例 1:
    
    输入: 12258
    输出: 5
    解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

####  ####

class Solution { 
        public int translateNum(int num) { 
            String s = String.valueOf(num);
            // dp[i]表示前i个字符可以翻译出来的结果的数量
            // dp[i] = dp[i-1] + s.substring(i-2,i)<=25 ? dp[i-2] : 0
            int n = s.length();
            int[] dp = new int[n+1];
            //这个初始化...
            dp[0] = 1;
            for(int i=1; i<=n; i++){ 
                dp[i] += dp[i-1];
                if(i-2>=0 && s.substring(i-2,i).compareTo("25")<=0 && s.substring(i-2,i).compareTo("10")>=0){ 
                    dp[i] += dp[i-2];
                }
            }
            return dp[n];
        }
    }

class Solution { 
        public int translateNum(int num) { 
            String s = String.valueOf(num);
            return core(s, 0);
        }
    
        private int core(String s, int i){ 
            int n = s.length();
            if(i==n){ 
                return 1;
            }
            if(i>n){ 
                return 0;
            }
            int res = 0;
            res += core(s, i+1);
            if(i+1<n && (s.substring(i,i+2).compareTo("25")<=0 && s.substring(i,i+2).compareTo("10")>=0)){ 
                res += core(s, i+2);
            }
            return res;
        }
    }

#### 第一次做; 动态规划; 核心: 1) dp\[i\]表示考虑前i个数时, 不同的翻译数量 2) 写dp循环主体时才知道dp\[0\]需要初始化为0, 具体地, i==2时过一遍循环就知道了 ####

class Solution { 
        public int translateNum(int num) { 
            //input check
            if(num<0)
                return 0;
            char[] chs = String.valueOf(num).toCharArray();
            int n = chs.length;
            /* dp[i]表示以chs[i]结尾的不同的翻译数量 dp[i]表示考虑前i个数时的不同的翻译数量 f(i) = f(i-1) + flag*f(i-2) 如果chs[i-1]chs[i]构成的十进制数在[10,25]范围上, 那么flag==1, 否则flag==0 最开始分析的时候卡在了chs[i-1]chs[i]组合时仍想着和dp[i-1]有什么联系, 其实此时应该考虑和dp[i-2]有什么关系, 这样就明了了 */
            int[] dp = new int[n+1];
            dp[0]=1; //写动态规划主体循环时才知道dp[0]要初始化为1, 比如案例num=12, 过一遍循环就知道了
            dp[1]=1;
            for(int i=2; i<=n; i++){ 
                //单独翻译chs[i-1]
                dp[i] = dp[i-1];
                //同时翻译chs[i-2] chs[i-1]
                // if(i-2>=0){ 
                int tmp = Integer.parseInt(new StringBuilder().append(chs[i-2]).append(chs[i-1]).toString());
                if(tmp>=10 && tmp<=25)
                    dp[i] = dp[i] + dp[i-2];
                // }
            }
            return dp[n];
        }
    }

#### 第一次做; 递归, 核心:1)设递归函数f(i)表示以chs\[i\]开头的不同的翻译数量; 2) 使用memo数组记录已处理过的结果, 避免重复子问题的计算 ####

class Solution { 
        public int translateNum(int num) { 
            //input check
            if(num<0)
                return 0;
            char[] chs = String.valueOf(num).toCharArray();
            int[] memo = new int[chs.length];
            int res = core(memo, chs, 0);
            return res;
        }
        
        //递归函数逻辑: 计算以chs[i]开始的不同的翻译数量
        private int core(int[] memo, char[] chs, int i){ 
            //base case
            if(i==chs.length){ 
                return 1;
            }
            if(memo[i]>0)
                return memo[i];
            //
            int res = 0;
            char ch = chs[i];
            if(ch>='0' && ch<='9')
                res += core(memo, chs, i+1);
            if(i+1<chs.length){ 
                int tmp = Integer.parseInt(new StringBuilder().append(chs[i]).append(chs[i+1]).toString());
                if(tmp>=10 && tmp<=25)
                    res += core(memo, chs, i+2);
            }
            memo[i] = res;
            return res;
            
        }
    }

#### 第一次做; 递归, 核心: 设递归函数f(i)表示以索引i对应元素开头, 有f(i)种不同的翻译; 缺点: 递归中有很多重复子问题, 比如说num=12345, 处理1时, 还剩2345, 接着处理2, 此时还剩345; 如果一开始处理12, 那么剩345, 这样出现了两次345, 重复处理 ####

class Solution { 
        public int translateNum(int num) { 
            //input check
            if(num<0)
                return 0;
            char[] chs = String.valueOf(num).toCharArray();
            int res = core(chs, 0);
            return res;
        }
        
        //(第一次的思考, 没想清楚递归函数的整体功能)递归函数逻辑: 当前元素自己翻译, 当前元素和下一个元素一块翻译
        //递归函数逻辑: 计算以chs[i]开始的不同的翻译数量
        private int core(char[] chs, int i){ 
            //base case
            if(i==chs.length){ 
                return 1;
            }
            //
            int res = 0;
            char ch = chs[i];
            if(ch>='0' && ch<='9')
                res += core(chs, i+1);
            if(i+1<chs.length){ 
                int tmp = Integer.parseInt(new StringBuilder().append(chs[i]).append(chs[i+1]).toString());
                if(tmp>=10 && tmp<=25)
                    res += core(chs, i+2);
            }
            return res;
            
        }
    }

#### [力扣优秀题解][Link 1] substring()和compareTo()用的很好, 两个两位数比较, 其字典序就是正常比较的结果 ####

![format_png][]

[welcome to my blog]: https://littlehaes.com
[Link 1]: https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/di-gui-by-gfu-2/
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS83MGJiYmYxYzNmZTRkYzVkN2Y1MWU0MDMyOTI2ODhiMC94bWxub3RlLzc4NjM5MDQ2RjM2QzRCNzFCRTNDRkI0Q0E4RUEwOTM3LzYyNTEx?x-oss-process=image/format,png