资兴市网站建设哪个好,铜陵58同城做网站,wordpress添加数据库文件夹,大连市营商环境建设局网站题目 规定1对应A、2对应B、3对应C…26对应Z#xff0c;那么一个数字字符串比如111#xff0c;就可以转化为#xff1a;“AAA”、“KA或AK”#xff0c;给定一个数字字符组成的字符串str#xff0c;返回有多少种转化结果。
解释一下#xff0c;字…题目 规定1对应A、2对应B、3对应C…26对应Z那么一个数字字符串比如111就可以转化为“AAA”、“KA或AK”给定一个数字字符组成的字符串str返回有多少种转化结果。
解释一下字符串111可以拆分成1-“1”-“1或者字符串11”-“1或者字符串1”-“11”所以有3种转化结果。
暴力递归 依然首先是暴力递归的思路将str转换成char[]共有两种转换方式。
自己单独转换不过有一点注意如果我当前字符是’0’的时候是不支持转化的因为没有对应字母支撑。两个字符拼接后转换同样也有一点主要注意因为是只有26个英文字母 所以两个字符拼接后不能以’0’字符开头并且相加后 27。
代码 代码中index chars.length时 return 1 是当 char[] 走完下面没字符之后返回的1代表是一种转换结果对当前转换结果的承认如果转换不成功中间过程中有0 或者 拼接完之后是 01或者拼接玩之后28这种没有字母对应的字符直接就会在过程中进行 return 0 public static int number(String str){if (str null || str.length() 0){return 0;}char[] chars str.toCharArray();//process()方法返回方法返回字符串转化结果return process(chars,0);}//从index位置开始转化index之前的不在意public static int process(char[] chars,int index){//如果走到了chars.length的位置说明走完了if (index chars.length){return 1;}//如果当前字符是0直接return 不往下走了。if (chars[index] 0){return 0;}//单独自己转换int ans process(chars,index 1);//拼接后面的转化先判断当前是不是最后一个字符并且满足转化条件if (index 1 chars.length (( chars[index] - 0) * 10 (chars[index 1] - 0) ) 27){ans process(chars,index 2);}return ans;}动态规划 根据可变参数index改动态规划因为只有一个可变参数所以是一个一维数组调用过程process是index 1 和 index 2所以是依赖后面根据暴力递归代码中base case index chars.length return 1可确定数组最后一个位置的值由后向前推导。
dp表组成根据暴力递归代码进行修改即可。
public static int dp(String str) {if (str null || str.length() 0) {return 0;}char[] strs str.toCharArray();int N strs.length;int[] dp new int[N 1];dp[N] 1;for (int i N - 1; i 0; i--) {if (strs[i] ! 0){int ans dp[i 1];if (i 1 N (dp[i] - 0) * 10 (dp[i 1] - 0) 27) {ans dp[i 2];}dp[i] ans;}}return dp[0];}
