💡 解题思路
- 📝 确定输入与输出
- 🔍 分析复杂度
- 🔨 复杂题目拆分 :严谨且完整 地拆分为更小的可以解决的子问题(栈和队列的功能,栈和队列的应用场景)–(多总结)
- 💭 选择处理逻辑: 根据拆分后的子问题,总结并选择合适的问题处理思路(栈和队列的转换逻辑)
- 🔎 检查特殊情况:边界条件和特殊情况
- 🏁 返回结果
class MyQueue {
private Stack<Integer> inStack;
private Stack<Integer> outStack;
public MyQueue() {
inStack = new Stack<>();
outStack = new Stack<>();
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
moveInToOutStack();
return outStack.pop();
}
public int peek() {
moveInToOutStack();
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.isEmpty();
}
private void moveInToOutStack() {
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
}
}
class MyStack {
private Queue<Integer> mainQueue;
private Queue<Integer> auxiliaryQueue;
public MyStack() {
mainQueue = new LinkedList<>();
auxiliaryQueue = new LinkedList<>();
}
public void push(int x) {
mainQueue.offer(x);
}
public int pop() {
while(mainQueue.size() > 1) {
auxiliaryQueue.offer(mainQueue.poll());
}
int num = mainQueue.poll();
Queue<Integer> temp = mainQueue;
mainQueue = auxiliaryQueue;
auxiliaryQueue = temp;
return num;
}
public int top() {
while(mainQueue.size() > 1) {
auxiliaryQueue.offer(mainQueue.poll());
}
int num = mainQueue.poll();
auxiliaryQueue.offer(num);
Queue<Integer> temp = mainQueue;
mainQueue = auxiliaryQueue;
auxiliaryQueue = temp;
return num;
}
public boolean empty() {
return mainQueue.isEmpty();
}
}
class Solution {
public static boolean isValid(String s) {
HashMap<Character, Character> map = new HashMap<>();
map.put(')','(');
map.put('}','{');
map.put(']','[');
Stack<Character> queueStack = new Stack<>();
int len = s.length();
if (len % 2 != 0) return false;
for (int i = 0; i < len; i++) {
char ch = s.charAt(i);
if (!map.containsKey(ch)) queueStack.push(ch);
else {
if (queueStack.isEmpty() || queueStack.pop() != map.get(ch)) return false;
}
}
return queueStack.isEmpty();
}
}
1047. 删除字符串中的所有相邻重复项 (可以用栈,下面用的双指针)
class Solution {
public static String removeDuplicates(String s) {
int j = -1;
int len = s.length();
char[] chars = s.toCharArray();
for (int i = 0; i < len; i++) {
if (j >= 0 && chars[i] == chars[j]) {
j--;
} else {
j++;
chars[j] = chars[i];
}
}
return String.copyValueOf(chars, 0, j+1);
}
}