算法跟练第十弹——栈与队列

跟着代码随想录刷题的第十天。

代码随想录链接：代码随想录

part01 逆波兰表达式求值

题目链接：150. 逆波兰表达式求值

代码：

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();int num;int a;int b;for(String i:tokens){if(isInt(i)){num = Integer.parseInt(i);stack.push(num);}else{b = stack.pop();a = stack.pop();int result = cal(i,a,b);stack.push(result);}}return stack.pop();}public boolean isInt(String s){//用正则表达式String b = "^-?\\d+$";return s.matches(b);}public int cal(String s,int a,int b){int result;switch(s){case "+":result = a+b;break;case "-":result = a-b;break;case "*":result = a*b;break;default:result = a/b;}return result;}
}

题解：只要遇到符号，就弹出前两个数并且进行运算，再把运算的结果存进去

代码随想录的解法：

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> stack = new LinkedList();for (String s : tokens) {if ("+".equals(s)) {        // leetcode 内置jdk的问题，不能使用==判断字符串是否相等stack.push(stack.pop() + stack.pop());      // 注意 - 和/ 需要特殊处理} else if ("-".equals(s)) {stack.push(-stack.pop() + stack.pop());} else if ("*".equals(s)) {stack.push(stack.pop() * stack.pop());} else if ("/".equals(s)) {int temp1 = stack.pop();int temp2 = stack.pop();stack.push(temp2 / temp1);} else {stack.push(Integer.valueOf(s));}}return stack.pop();}
}

对比了一下，我多了判断字符串数组里面的数是不是整数的步骤

part02 滑动窗口最大值

题目链接：239. 滑动窗口最大值

代码：

class MyQueue{Deque<Integer> queue = new LinkedList<>();public void poll(int val){if(!queue.isEmpty()&&val==queue.peek()){queue.poll();}}public void add(int val){while(!queue.isEmpty()&&val>queue.getLast()){queue.removeLast();}queue.add(val);}public int peek(){return queue.peek();}
}class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums.length==1)return nums;MyQueue queue = new MyQueue();int len = nums.length-k+1;int[] result = new int[len];int cnt = 0;for(int i = 0;i<k;i++){queue.add(nums[i]);}result[cnt++] = queue.peek();for(int i = k;i<nums.length;i++){queue.poll(nums[i-k]);queue.add(nums[i]);result[cnt++] = queue.peek();}return result;}
}

题解：本题是自定义了一个单调队列，只在队列中保留可能成为最大值的数值。当一个数值进入到队列中时，若是前面所有值都比它小，就全部弹出。

part03 前 K 个高频元素

题目链接：347.前 K 个高频元素

代码：

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

题解：先用HashMap将元素和出现频率存储起来，再用小根堆将出现频率按顺序保留，最后输出。

归纳：

将字符串转转换成整数：

int num = Integer.parseInt(i);

LinkedList

• 获取链表最后一个元素

a.getLast();

• 移除链表最后一个元素

a.moveLast();

Map遍历

Map.Entry<Integer, Integer> entry : map.entrySet()

优先级队列的比较器

new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1])

这里使用了 PriorityQueue 的构造函数，并传入了一个 Lambda 表达式 作为比较器（Comparator）。

比较器的作用是定义队列中元素的优先级规则。

Lambda 表达式 (pair1, pair2) -> pair1[1] - pair2[1]
pair1 和 pair2 是两个 int[] 类型的元素（即两个整数数组）。

pair1[1] 和 pair2[1] 分别表示这两个数组的第二个元素（索引为 1 的元素）。

pair1[1] - pair2[1] 是一个比较逻辑：

• 如果 pair1[1] < pair2[1]，结果为负数，表示 pair1 的优先级高于 pair2。

• 如果 pair1[1] == pair2[1]，结果为 0，表示两者优先级相同。

• 如果 pair1[1] > pair2[1]，结果为正数，表示 pair1 的优先级低于 pair2。