一个ip地址上可以做几个网站,建设网站收费明细,黄骅市大学有哪些,网站建设对促进部门工作的益处【问题描述】[中等]
给定一个经过编码的字符串#xff0c;返回它解码后的字符串。编码规则为: k[encoded_string]#xff0c;表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的#xff1b;输入字符串中没有额外的空…【问题描述】[中等]
给定一个经过编码的字符串返回它解码后的字符串。编码规则为: k[encoded_string]表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的输入字符串中没有额外的空格且输入的方括号总是符合格式要求的。此外你可以认为原始数据不包含数字所有的数字只表示重复的次数 k 例如不会出现像 3a 或 2[4] 的输入。示例:s 3[a]2[bc], 返回 aaabcbc.
s 3[a2[c]], 返回 accaccacc.
s 2[abc]3[cd]ef, 返回 abcabccdcdcdef.
【解答思路】
1. 辅助栈法 时间复杂度O(N) 空间复杂度O(N) public String decodeString(String s) {StringBuilder res new StringBuilder();int multi 0 ; LinkedListInteger stack_multi new LinkedList();LinkedListString stack_res new LinkedList();for(Character c: s.toCharArray()){if(c [){stack_multi.addLast(multi);stack_res.addLast(res.toString());multi 0;res new StringBuilder();}else if(c ]){StringBuilder tmp new StringBuilder();int cur_multi stack_multi.removeLast();for(int i 0;icur_multi;i){tmp.append(res);}res new StringBuilder(stack_res.removeLast()tmp);}else if(c 0 c9){//次数大于10时需要累计multi multi *10 Integer.parseInt(c);}else{res.append(c);}}return res.toString();}2. 递归法 时间复杂度O(N) 空间复杂度O(N)
class Solution {//空间换时间同时避免递归传这种不会改变的参数//String.charAt()会多一个越界的判断其实这里不转为数组也可以个人习惯char[] ss;public String decodeString(String s) {this.ss s.toCharArray();return dfs(0)[0];}private String[] dfs(int i) {int nums 0;StringBuilder res new StringBuilder();while (i ss.length) {//是数字因为不一定只有个位所以需要进位计算if (Character.isDigit(ss[i])) {nums nums * 10 (ss[i] - 0);//如果是[就是重复字符串的开始位置} else if (ss[i] [) {//因为可能会嵌套n[字符串]所以需要进入递归String[] temp dfs(i 1); //这里是16行//将指针移动到结尾的]位置中间的内容在下面的while中已经填充完毕i Integer.parseInt(temp[0]);//根据nums循环填充目标字符串while (nums 0) {res.append(temp[1]);nums--;}//如果是]说明已经输出完成其实只在进入递归后有效第一次调用dfs的栈帧永远不会走进这个判断} else if (ss[i] ]) {//此处为什么是i呢因为这层return到的是递归方法调用处即返回至16行所在不可能返回到初次调用的位置//所以需要记录]出现的位置至于为什么不1是因为走完16行所在的代码块会走到34行return new String[]{String.valueOf(i), res.toString()};//类似于2[abc]3[cd]ef中的ef没有循环次数可以直接填充} else {res.append(ss[i]);}//移动指针i; //这里是34行}return new String[]{res.toString()};}
}class Solution {public String decodeString(String s) {return dfs(s, 0)[0];}private String[] dfs(String s, int i) {StringBuilder res new StringBuilder();int multi 0;while(i s.length()) {if(s.charAt(i) 0 s.charAt(i) 9) multi multi * 10 Integer.parseInt(String.valueOf(s.charAt(i))); else if(s.charAt(i) [) {String[] tmp dfs(s, i 1);i Integer.parseInt(tmp[0]);while(multi 0) {res.append(tmp[1]);multi--;}}else if(s.charAt(i) ]) return new String[] { String.valueOf(i), res.toString() };else res.append(String.valueOf(s.charAt(i)));i;}return new String[] { res.toString() };}
}
【总结】
1.为什么用LinkedList不用Stack
基于 Vector 实现的栈 Stack底层是数组 扩容开销大 Java并不推荐使用java.util.stack来进行栈的操作而是推荐使用一个双端队列deque 详情链接https://www.cnblogs.com/cosmos-wong/p/11845934.html
2.细节
2.1 转字符串 1、toString需要保证调用这个方法的类、方法、变量不为null否则会报空指针。
2、String.valueOf。这个方法在使用的时候是有些特殊的。一般情况下如果是确定类型的null传入返回的是字符串“null”而如果直接传入null则会发生错误。
3、(String) 字符串类型强转。需要保证的是类型可以转成String类型。 2.2 、2.3 应用于提取字符串中的数字字符转整形 2.2 字符转整型 Integer.parseInt(c );2.3 字符串中某字符转整型 Integer.parseInt(String.valueOf(s.charAt(i))); 3.括号匹配 栈栈栈
4.包装类的用法 转载链接https://leetcode-cn.com/problems/decode-string/solution/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/ 参考链接https://blog.csdn.net/yangzhaomuma/article/details/51173138
