中国建设人才网信息网站,管家婆进销存管理系统,wordpress移动端顶部导航,在线做logo这道题有点像我之前写过的一道题有效的括号#xff08;不只是栈#xff09;-CSDN博客 但是比那道题要难#xff0c;但用的方法是一样的#xff0c;就是用栈的先进后出进行括号匹配#xff0c;所以有写过之前那道题#xff0c;这道题按照这个思路走我就写出了如下屎山代码… 这道题有点像我之前写过的一道题有效的括号不只是栈-CSDN博客 但是比那道题要难但用的方法是一样的就是用栈的先进后出进行括号匹配所以有写过之前那道题这道题按照这个思路走我就写出了如下屎山代码
class Solution {public String decodeString(String s) {int n s.length();StackCharacter stack new Stack();String ans ;for(int i 0;in;i){char c s.charAt(i);if(c ! ]){stack.push(c);}else{String tmp ;while(!stack.isEmpty()){char c1 stack.pop();if(c1 ! [){tmp c1 tmp;}else{int num stack.pop() -48;int m 1;while(!stack.isEmpty() stack.peek() 57){int mask (int)Math.pow(10,m);num num (int)(stack.pop() -48)*mask;m;}char[] charArr tmp.toCharArray(); for(int k 0;knum;k){for(int j0;jcharArr.length;j){stack.push(charArr[j]);}}break;}}}}while(!stack.isEmpty()){ans stack.pop() ans;}return ans;}
} 我这个就非常好理解遍历s的每个字符只要不是“]”就直接放如果是那么就从stack里面把字符拿出来拼接如果拿出来的这个字符是[,那么再把[前面的数字拿出来(可能是多位数)num然后把这个把这个拼接出来的字符串一位一位的放回stack放num遍遍历完了s所有的字符之后把stack里面的字符连起来就是ans返回ans即可。
比如“3[a2[c]]”一开始stack里面放的是3[a2[c然后遇到了],就把c拿出来把2*c放回去现在stack里面是3[acc然后又遇到了],把acc拿出来把3*acc放回去stack里面现在是accaccacc遍历完了返回accaccacc。
因为效率有点慢只超过了11%我就想能不能拿到括号里的字符串就不放回stack了于是我把放回stack那一部分改成了递归写了如下代码
class Solution {public String decodeString(String s) {if(!s.contains([)){return s;}int n s.length();StackCharacter stack new Stack();for(int i 0;in;i){char c s.charAt(i);if(c ! ]){stack.push(c);}else{String tmp ;while(!stack.isEmpty()){char c1 stack.pop();if(c1 ! [){tmp c1 tmp;}else{int num 0;int m 0;String p ;while(!stack.isEmpty() stack.peek() 57){int mask (int)Math.pow(10,m);num num (int)(stack.pop() -48)*mask;m;}p tmp;for(int k 0;knum-1;k){tmp p;}s s.substring(0,i-1-p.length()-m) tmp s.substring(i1,n);if(s.contains([)){return decodeString(s);}else{return s;}}}}}return s;}
}
比如3[a2[c]]stack里面是3[a2[c然后遇到了],于是拿出了cc,然后把s变成“3[a” “cc” ]也就是“3[acc]”。然后再判断“3[acc]”里面有没有“[”,如果没有说明全部括号都消掉了直接返回这个s即如果还有括号则递归调用decodeString(s)再消掉一个括号。算法没问题但是没软用依旧是超过11%。
看看题解做法吧。
题解的做法一和我第一种的思想是一样的就是从stack中拿出来字符串后乘以倍数又返回栈但是它的的效率超过了77%它相比于我就是一点优化它stack放的是String而我放的是char所以它遍历到一个字母字符后就把后面连串的字符拼接放进去。比如“100[leetcode]”,我是放了100个[l,e,e,t,c,o,d,e]而它放的是100个leetcode,无论是空间还是时间都效率更高以下是题解方法一代码
class Solution {int ptr;public String decodeString(String s) {LinkedListString stk new LinkedListString();ptr 0;while (ptr s.length()) {char cur s.charAt(ptr);if (Character.isDigit(cur)) {// 获取一个数字并进栈String digits getDigits(s);stk.addLast(digits);} else if (Character.isLetter(cur) || cur [) {// 获取一个字母并进栈stk.addLast(String.valueOf(s.charAt(ptr))); } else {ptr;LinkedListString sub new LinkedListString();while (![.equals(stk.peekLast())) {sub.addLast(stk.removeLast());}Collections.reverse(sub);// 左括号出栈stk.removeLast();// 此时栈顶为当前 sub 对应的字符串应该出现的次数int repTime Integer.parseInt(stk.removeLast());StringBuffer t new StringBuffer();String o getString(sub);// 构造字符串while (repTime-- 0) {t.append(o);}// 将构造好的字符串入栈stk.addLast(t.toString());}}return getString(stk);}public String getDigits(String s) {StringBuffer ret new StringBuffer();while (Character.isDigit(s.charAt(ptr))) {ret.append(s.charAt(ptr));}return ret.toString();}public String getString(LinkedListString v) {StringBuffer ret new StringBuffer();for (String s : v) {ret.append(s);}return ret.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() };}
}
