【Leecode】代码随想录栈和队列篇day12(应用）

逆波兰表达式求和

• 题目链接：逆波兰表达式求值
• 我的解法：使用if-else 在外判断运算还是储存，在内用switch-case判断是哪种运算

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> st = new Stack<Integer>();
        for(int i = 0; i < tokens.length; i++)
        {
            String str = tokens[i];
            if(str.equals("+") || str.equals("-") || str.equals("*")|| str.equals("/"))
            /*java字符串比较”==“是比较地址，”str.equals()“*/
            {
                //a str b
                int b = st.pop();
                int a = st.pop();
                switch(str.charAt(0)){
                    case '+': {st.push((a + b)); break;}
                    case '-': {st.push((a - b)); break;}
                    case '*': {st.push((a * b)); break;}
                    case '/': {st.push((a / b)); break;}
                }    
            }
            else{
                //System.out.println(str);
                st.push(Integer.parseInt(str));
            }
        }
        return st.peek();
    }

}

• 优化解法：更快速的解法其实是两个switch-case的判断组合加上使用数组模拟栈。
• 复杂度：时间复杂度$O(n)$，空间复杂度$O(n)$

总结：
字符串转为数字的方法Integer.parseInt(str)

滑动窗口最大值

java数据结构deque详解https://blog.csdn.net/devnn/article/details/82716447

• 题目链接：
• 我的解法：记忆模糊的使用双端队列维护窗口内有效最大值，但对于窗口滑动时弹出窗口外的最大值部分，一开始想存下标后来又想验证队头的值是否等于窗口头的值，后来两种解法都没有实现
• 正确解法：滑动窗口之最大元素
  Ⅰ结果数组中直接存储元素

class MyDeque {
    Deque<Integer> que = new LinkedList<>();
    void add(int val){
        while(!que.isEmpty() && que.getLast() < val)
        que.removeLast();//移除队尾元素

        que.offer(val);
    }

    void poll(int val){
        if(!que.isEmpty() && que.peek() == val)
            que.poll();//移除队首元素
    }

    int peek (){
        return que.peek();//取队首元素
    }

}
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
      int len = nums.length;
      if(k == 1) return nums;
      int[] res = new int[(len - k + 1)]; int idx = 0;
      MyDeque deque = new MyDeque();
      for(int i = 0; i < k; i++) deque.add(nums[i]);
      res[idx++] = deque.peek();//先加入前三个的起始答案
      for(int i = k; i < len; i++)
      {
            deque.poll(nums[i - k]);
            deque.add(nums[i]);
            res[idx++] = deque.peek();
      }
      return res;
    }
}

前k个高频元素

• 题目链接：前k个高频元素
• 正确解法：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }

        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}

• 时间复杂度: $O(nlogk)$，空间复杂度: $O(n)$