155. 最小栈
https://leetcode.cn/problems/min-stack/description/?envType=study-plan-v2&envId=top-100-liked
class MinStack {
Deque<Integer> deque;
PriorityQueue<Integer> priorityQueue;
public MinStack() {
deque = new LinkedList<>();
priorityQueue = new PriorityQueue<>();
}
public void push(int val) {
deque.addLast(val);
priorityQueue.add(val);
}
public void pop() {
Integer i = deque.pollLast();
priorityQueue.remove(i);
}
public int top() {
return deque.peekLast();
}
public int getMin() {
return priorityQueue.peek();
}
}
总结:用优先级队列查min
394. 字符串解码
https://leetcode.cn/problems/decode-string/description/?envType=study-plan-v2&envId=top-100-liked
public String decodeString(String s) {
// 准备两个栈,一个存放数字,一个存放字符串
// 遍历有四种情况
// 1. 如果是数字,将数字转换成整型数字待处理
// 2. 如果是字符,将字符添加到临时字符串待处理
// 3. 如果是'[',将当前数字和临时字符串添加到各自的栈中
// 4. 如果是']',将数字和字符从各自的栈中取出,然后拼接成新的临时字符串
// 创建数字栈、字符串栈、临时数字和临时字符串
Deque<Integer> stack_nums = new ArrayDeque<>();
Deque<StringBuilder> stack_words = new ArrayDeque<>();
StringBuilder curString = new StringBuilder();
int curNum = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)){
curNum = curNum * 10 + c - '0';
}else if (Character.isLetter(c)){
curString.append(c);
}else if (c == '['){
stack_nums.push(curNum);
curNum = 0;
stack_words.push(curString);
curString = new StringBuilder();
}else {
StringBuilder temStr = stack_words.pop();
int cnt = stack_nums.pop();
for (int j = 0; j < cnt; j++) {
temStr.append(curString);
}
curString = temStr;
}
}
return curString.toString();
}
总结:思路就是维护两个栈,用来存数字和字符串,字符串栈里是StringBuilder,维护两个变量,一个去计算。 数字栈存的是算好的数字,字符串栈存的是之前的字符串,需要拿出来跟当前的字符串拼接(拼接n次)
标签:155,int,LeetCodeHot100,public,curString,394,字符串,new,stack From: https://www.cnblogs.com/jeasonGo/p/18092418