AC笔记 | Leetcode 0394 —— 辅助栈
394. 字符串解码（中等）
使用辅助栈
根据题意一共有四种情况：
- 数字
- 遇到数字需要对数字从字符变为正确的数字，并入num
- 字符
- 遇到字符，使用StringBuffer类的res对象进行追加
- [
- 遇到
[，需要将num和res分别入栈nums和str - 并且将num置0，将res置空
- 遇到
- ]
- 从nums栈中弹出栈顶元素multi，从str栈中弹出栈顶元素sub
- 将sub放入一个字符串缓存subf中
- 将res重复multi次，之后追加打牌subf之后
- 将subf赋值给res
代码示例
public static String decodeString(String s) {
LinkedList<Integer> nums = new LinkedList<>();
LinkedList<String> str = new LinkedList<>();
int num = 0;
StringBuffer res = new StringBuffer();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 四种可能
if (c=='[') {
nums.addLast(num);
str.addLast(res.toString());
num = 0;
res = new StringBuffer();
} else if (c>='0'&&c<='9') {
num = num*10+Integer.valueOf(c-'0');
} else if (c==']'){
StringBuffer subf = new StringBuffer();
int multi = nums.pollLast();
String sub = str.pollLast();
subf.append(sub);
for (int j = 0; j < multi; j++) {
subf.append(res);
}
res = subf;
} else {
res.append(c);
}
}
return res.toString();
}
总结：
很显然这道题看答案了，按理来说从数据结构和逻辑都不是很难。
主要出现的问题是 [abc2[ab]ac]
我是将 [abc2[ab 均入栈，然后遇到 ]出栈到 2，得到答案 abab 后，自己混乱了，其实还是可以做下去的
比如把栈作为string栈，abc入栈，遇到 2 也入栈，ab 再入栈，遇到 ] 才出栈组合