网站前台登陆页面怎么改,个人博客系统的设计与实现,萧山区建设工程质量监督站网站,合同范本的网站摘要
剑指 Offer 46. 把数字翻译成字符串
一、递归算法解析
给定一个数字#xff0c;我们按照如下规则把它翻译为字符串#xff1a;0 翻译成 “a” #xff0c;1 翻译成 “b”#xff0c;……#xff0c;11 翻译成 “l”#xff0c;……#xff0c;25 翻译成 “z”。…摘要
剑指 Offer 46. 把数字翻译成字符串
一、递归算法解析
给定一个数字我们按照如下规则把它翻译为字符串0 翻译成 “a” 1 翻译成 “b”……11 翻译成 “l”……25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。 定义递归函数
dfs 函数求「当前指针位置到末尾的数字」的翻译方法数。节点的状态用指针表示dfs 入口传 0。如果指针 和 指针1 对应的两位数在[10,25]内则可以直译有两种选择 翻译1个数指针走一步递归调用返回出剩余数字的翻译方法数。 翻译2个数指针走两步递归调用返回出剩余数字的翻译方法数。 二者相加就是当前数字串的翻译方法数。如果指针 和 指针1 对应的两位数不在[10, 25]内则无法直译只有一个选择 翻译1个数指针走一步递归调用 dfs返回出剩余子串的翻译方法数。
package recursion;/*** Classname JZ46把数字翻译成字符串* Description TODO* Date 2023/3/7 22:08* Created by xjl*/
public class JZ46把数字翻译成字符串 {public int translateNum(int num) {char[] chars String.valueOf(num).toCharArray();int index 0;return next(chars, index);}/*** description 就是可能等于的一个数或者两个字母组合一个数字* param: chars* param: index* date: 2023/3/7 22:08* return: int* author: xjl*/private int next(char[] chars, int index) {if (index chars.length - 1) {return 1;}int one next(chars, index 1);int two 0;if (index chars.length - 1 ((chars[index] - 0) * 10 (chars[index 1] - 0) 9 (chars[index] - 0) * 10 (chars[index 1] - 0) 26)) {two next(chars, index 2);}return one two;}
}复杂度分析
时间复杂O(2^n)。每个节点都要遍历栈的深度nn是数字字符个数。空间复杂度: O(n)。栈的深度n n是数字字符个数。
博文参考
《leetcode》
