代码随想录五刷day5

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

---

在栈与队列系列中，我们强调栈与队列的基础，也是很多同学容易忽视的点。 使用抽象程度越高的语言，越容易忽视其底层实现，而C++相对来说是比较接近底层的语言。 我们用栈实现队列，用队列实现栈来掌握的栈与队列的基本操作。

一、力扣232. 用栈实现队列

class MyQueue {private Deque<Integer> d1;private Deque<Integer> d2;public MyQueue() {this.d1 = new LinkedList<>();this.d2 = new LinkedList<>();}public void push(int x) {d1.offerLast(x);}public int pop() {if(!d2.isEmpty()){return d2.pollLast();}while(!d1.isEmpty()){d2.offerLast(d1.pollLast());}return d2.pollLast();}public int peek() {if(!d2.isEmpty()){return d2.peekLast();}while(!d1.isEmpty()){d2.offerLast(d1.pollLast());}return d2.peekLast();}public boolean empty() {return d1.isEmpty() && d2.isEmpty();}
}

二、力扣225. 用队列实现栈

class MyStack {Deque<Integer> d1 = new LinkedList<>();Deque<Integer> d2 = new LinkedList<>();public MyStack() {}public void push(int x) {d1.offerLast(x);}public int pop() {if(!d1.isEmpty()){while(d1.size() > 1){d2.offerLast(d1.pollFirst());}return d1.pollFirst();}while(d2.size() > 1){d1.offerLast(d2.pollFirst());}return d2.pollFirst();}public int top() {if(!d1.isEmpty()){while(d1.size() > 1){d2.offerLast(d1.pollFirst());}return d1.peekFirst();}while(d2.size() > 1){d1.offerLast(d2.pollFirst());}int res = d2.pollFirst();d1.offerLast(res);return res;}public boolean empty() {return d1.isEmpty() && d2.isEmpty();}
}

三、力扣20. 有效的括号

class Solution {public boolean isValid(String s) {Deque<Character> deq = new LinkedList<>();for(char c : s.toCharArray()){if(c == '[' || c == '(' || c == '{'){deq.offerLast(c);}else{if(deq.isEmpty()){return false;}char t = deq.pollLast();if(c == ')' && t != '('){return false;}if(c == ']' && t != '['){return false;}if(c == '}' && t != '{'){return false;}}}return deq.isEmpty();}
}

四、力扣1047. 删除字符串中的所有相邻重复项

class Solution {public String removeDuplicates(String s) {Deque<Character> deq = new LinkedList<>();for(char c : s.toCharArray()){if(deq.isEmpty()){deq.offerLast(c);continue;}if(deq.peekLast() == c){deq.pollLast();continue;}deq.offerLast(c);}StringBuilder sb = new StringBuilder();while(!deq.isEmpty()){sb.append(deq.pollFirst());}return sb.toString();}
}

五、力扣150. 逆波兰表达式求值

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> deq = new LinkedList<>();int l  = 0, r = 0;for(String s : tokens){if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){r = deq.pollLast();l = deq.pollLast();switch (s){case "+" : deq.offerLast(l + r);break;case "-" : deq.offerLast(l - r);break;case "*" : deq.offerLast(l * r);break;case "/" : deq.offerLast(l / r);break;}}else{System.out.println(s);deq.offerLast(Integer.parseInt(s));}}return deq.pollLast();}
}

六、力扣239. 滑动窗口最大值

滑动窗口中的最大值，首先维护一个单调队列，这题要求最大值，所以维护的是一个出队方向最大的一个单调队列，对于每一个元素来说，轮到他时，就要判断一下，队列头的元素是不是在窗口内的，不是的要抛出，然后就是维护队列的逻辑，判断队列是否非空，空的话直接加入，非空的话，从队尾方向，把小于当前元素的都抛出，最后把自己维护进去，然后是收集逻辑，因为是窗口的最大值，所以一开始，当前元素未移动到窗口的最后一个，不做收集

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {Deque<Integer> deq = new LinkedList<>();List<Integer> res = new ArrayList<>();for(int i = 0; i < nums.length; i ++){if(!deq.isEmpty() && deq.peekFirst() <= i-k){deq.pollFirst();}if(deq.isEmpty()){deq.offerLast(i);}else{while(!deq.isEmpty() && nums[i] > nums[deq.peekLast()]){deq.pollLast();}deq.offerLast(i);}if(i >= k-1){res.add(nums[deq.peekFirst()]);}}int[] array = res.stream().mapToInt(Integer::intValue).toArray();return array;}
}

七、力扣前 K 个高频元素

获取前K个高频元素，可以先用map收集各个元素的频率，然后使用优先级队列，大根堆进行收集，最后抛出前K个元素

class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>();int[] res = new int[k];for(int n : nums){map.put(n, map.getOrDefault(n,0) + 1);}PriorityQueue<int[]> pq = new PriorityQueue<>((x1,x2) -> x2[1] - x1[1]);for(Map.Entry<Integer,Integer> entry : map.entrySet()){pq.add(new int[]{entry.getKey(),entry.getValue()});}for(int i = 0; i < k; i ++){res[i] = pq.poll()[0];}return res;}
}