Summary
- Stack and Queue
- 用栈实现队列 232. Implement Queue using Stacks 💚
- 用队列实现栈 225. Implement Stack using Queues 💚
- 有效的括号 20. Valid Parentheses 💚
- 删除字符串中的所有相邻重复项 1047. Remove All Adjacent Duplicates In String 💚
- 逆波兰表达式求值 150. Evaluate Reverse Polish Notation 🧡
- 滑动窗口最大值 239. Sliding Window Maximum ❤️
- 前 K 个高频元素 347. Top K Frequent Elements 🧡
- 补充
9.1 StringBuilder
9.2 java单引号双引号
9.3 ==和equals
9.4 PriorityQueue
1. Stack and Queue
Stack: LIFO(last in first out)
Queue: FIFO (first in first out)
| input | output | lookpeek | empty | |
|---|---|---|---|---|
| stack | push() | pop() | peek() | isEmpty() |
| queue | offer() | poll() | peek() | isEmpty() |
stack and queue
2. 用栈实现队列 232. Implement Queue using Stacks 💚
使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈 。
在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。
stack -> queue
一个输入栈，一个输出栈。
class MyQueue {
Stack<Integer> stackIn;
Stack<Integer> stackOut;
/** Initialize your data structure here. */
public MyQueue() {
stackIn = new Stack<>(); // 负责进栈
stackOut = new Stack<>(); // 负责出栈
}
/** Push element x to the back of queue. */
public void push(int x) {
stackIn.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
dumpstackIn();
return stackOut.pop();
}
/** Get the front element. */
public int peek() {
dumpstackIn();
return stackOut.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stackIn.isEmpty() && stackOut.isEmpty();
}
// 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
private void dumpstackIn(){
if (!stackOut.isEmpty()) return;
while (!stackIn.isEmpty()){
stackOut.push(stackIn.pop());
}
}
}
3. 用队列实现栈 225. Implement Stack using Queues 💚
可以用一个queue实现stack：
一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。
class MyStack {
Queue<Integer> queue;
public MyStack() {
queue = new LinkedList<>();
}
//每 offer 一个数（A）进来，都重新排列，把这个数（A）放到队列的队首
public void push(int x) {
queue.offer(x);
int size = queue.size();
//移动除了 A 的其它数
while (size-- > 1)
queue.offer(queue.poll());
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
4. 有效的括号 20. Valid Parentheses 💚
由于栈结构的特殊性，非常适合做对称匹配类的题目。
首先要弄清楚，字符串里的括号不匹配有几种情况。
- 字符串里左方向的括号多余了 ，所以不匹配。
- 括号没有多余，但是 括号的类型没有匹配上。
-
字符串里右方向的括号多余了，所以不匹配。
three cases
解决方案：
- 已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false
- 遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false
- 遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false
但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
char[] ch = s.toCharArray();
for(int i = 0; i < ch.length; i++){
if(ch[i] == '('){
stack.push(')');
}else if(ch[i] == '{'){
stack.push('}');
}else if(ch[i] == '['){
stack.push(']');
}else if (stack.isEmpty() || stack.pop() != ch[i]) {
return false;
}
}
return stack.isEmpty();
}
}
5. 删除字符串中的所有相邻重复项 1047. Remove All Adjacent Duplicates In String 💚
用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。
消除
Class Solution{
public String removeDuplicates(String S) {
Stack<Character> stk=new Stack<>();
for(int i=0;i<S.length();i++) {
if(!stk.isEmpty()&&stk.peek()==S.charAt(i)) stk.pop();
else stk.push(S.charAt(i));
}
StringBuilder sb=new StringBuilder();
while(!stk.isEmpty()) sb.append(stk.pop());
return sb.reverse().toString();
}
}
6. 逆波兰表达式求值 150. Evaluate Reverse Polish Notation 🧡
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
-
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
逆波兰数
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < tokens.length; i++){
if("+".equals(tokens[i])){
stack.push(stack.pop() + stack.pop());
}else if("-".equals(tokens[i])){
stack.push(-stack.pop() + stack.pop());//要分清，先出栈的是被减的
}else if("*".equals(tokens[i])){
stack.push(stack.pop() * stack.pop());
}else if("/".equals(tokens[i])){
int temp1 = stack.pop();
int temp2 = stack.pop();
stack.push(temp2 / temp1);
//除法要使用临时变量，因为先出栈的是被除的
}else{
stack.push(Integer.valueOf(tokens[i]));
}
}
return stack.pop();
}
}
⚠️：leetcode 内置jdk的问题，不能使用==判断字符串是否相
判断运算符号，要用双引号
7. 滑动窗口最大值 239. Sliding Window Maximum ❤️
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
LinkedList<Integer> deque = new LinkedList<>();
int n = nums.length;
int[] res = new int[n - k + 1];
int idx = 0;
for(int i = 0; i < n; i++) {
// 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点
// 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出
while(!deque.isEmpty() && deque.peek() < i - k + 1){
deque.poll();
}
// 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offer(i);
// 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了
if(i >= k - 1){
res[idx] = nums[deque.peek()];
idx++;
}
}
return res;
}
}
详见：滑动窗口
8. 前 K 个高频元素 347. Top K Frequent Elements 🧡
这道题目主要涉及到如下三块内容：
- 要统计元素出现频率 --HashMap
- 对频率排序 -- 然可以使用一种 容器适配器就是优先级队列。其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。而且优先级队列内部元素是自动依照元素的权值排列。PriorityQueue利用堆完成对元素的排序，这个堆是complete binary tree（完全二叉树）
- 找出前K个高频元素--output priority queue
前K个高频元素
class Solution {
//解法1：基于大顶堆实现
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();//key为数组元素值,val为对应出现次数
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
//在优先队列中存储二元组(num,cnt),cnt表示元素值num在数组中的出现次数
//出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair2[1]-pair1[1]);
for(Map.Entry<Integer,Integer> entry:map.entrySet()){//大顶堆需要对所有元素进行排序
pq.add(new int[]{entry.getKey(),entry.getValue()});
}
int[] ans = new int[k];
for(int i=0;i<k;i++){//依次从队头弹出k个,就是出现频率前k高的元素
ans[i] = pq.poll()[0];
}
return ans;
}
}
9. 补充
9.1 StringBuilder
StringBuilder 类的对象能够被多次的修改，并且不产生新的未使用对象。
| 方法 | 描述 |
|---|---|
| append() | 将指定的字符串追加到此字符序列 |
| reverse() | 将此字符序列用其反转形式取代 |
| delete(int start, int end) | 移除此序列的子字符串中的字符 |
| insert(int offset, int i) | 将 int 参数的字符串表示形式插入此序列中。 |
| replace(int start, int end, String str) | 使用给定 String 中的字符替换此序列的子字符串中的字符 |
9.2 java单引号双引号
- 单引号是Char类型，只能存储一个字符。
- 双引号是String类型，可以存储0个或多个字符,其实string类型就是char类型的数组表现形式。
9.3 ==和equals
- == 比较的是变量(栈)内存中存放的对象的(堆)内存地址，用来判断两个对象的地址是否相同，即是否是指相同一个对象。
- equals用来比较的是两个对象的内容是否相等，由于所有的类都是继承自java.lang.Object类的，所以适用于所有对象，如果没有对该方法进行覆盖的话，调用的仍然是Object类中的方法，而Object中的equals方法返回的却是==的判断。可以重写比较方法。
9.4 PriorityQueue
PriorityQueue 就是heap。该优先级使得队列始终按照自然顺序进行排序，队列的头部为最小值。
//构建小根堆min-heap
PriorityQueue small=new PriorityQueue<>();
//构建大根堆max-heap
PriorityQueue pq = new PriorityQueue((a, b) -> b - a);
