代码随想录算法训练营第十一天| 150. 逆波兰表达式求值、239. 滑动窗口最大值、347.前 K 个高频元素

150. 逆波兰表达式求值

思路：遇到数字入栈，遇到字符，出栈中的两个数字，然后计算，得到的结果再入栈。

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack();for(String s : tokens){if ("+".equals(s)) {    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();}
}

 239. 滑动窗口最大值（难）

代码录思路：自己diy一个数据结构，其类似于双端队列。扫描前k个元素，入队时，先与队尾元素比较，若队尾元素比要添加的元素小，则将队尾元素排出（这可以保证队头位置的元素一直为最大元素）。当窗口后移时，要将窗口前边元素移出，则需要判断窗口移除元素是否为队头元素，若是，则移除队头元素，若不是，则代表已经移除。将窗口后边元素移入时调用入队操作即可。

class Myqueue{Deque<Integer> deque;public Myqueue(){deque = new LinkedList<>();}void add(int num){while(!deque.isEmpty() && num > deque.getLast()){deque.pollLast();}deque.add(num);}void delete(int num){if(!deque.isEmpty() && deque.getFirst() == num){deque.pollFirst();}}int getMax(){return deque.peek();}
}class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] res = new int[nums.length-k+1];Myqueue myqueue = new Myqueue();for(int i = 0;i < k;i++){myqueue.add(nums[i]);}res[0] = myqueue.getMax();for(int i = k; i < nums.length;i++){//先移除窗口头部元素；myqueue.delete(nums[i-k]);//加入下一个元素;myqueue.add(nums[i]);//获取最大值res[i-k+1] = myqueue.getMax();}return res;}
}

 347.前 K 个高频元素（难）

代码录思路：先用map记录元素及其出现的次数，然后用优先级队列（小顶堆），记录前k个高频元素。

代码中好多方法都不熟练

class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<Integer, Integer>();//遍历数组，得到每个元素出现的次数for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}PriorityQueue<int[]> pq = new PriorityQueue<>((value1,value2)->value1[1]-value2[1]);//获取出现次数最多的k个元素，放到pq中for(Map.Entry<Integer, Integer> value : map.entrySet() ) {if(pq.size() < k) {//元素少于k个时，直接加入pq.add(new int[] {value.getKey(),value.getValue()});}else {//元素大于k个时分情况if(value.getValue() > pq.peek()[1]) {//元素出现次数比队列中出现次数最少的多时，加入pq.poll();pq.add(new int[] {value.getKey(),value.getValue()});}}}int[] res = new int[k];for(int i = k-1;i>=0;i--) {res[i] = pq.poll()[0];}return res;}
}

鉴于作者水平有限，文章可能存在错误

如有指正，十分感谢