代码随想录day12 Java版

今天解决队列和栈的题，期待后面狠狠搞二叉树（之前面试被刺了TT)

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

这个题目跟前面的匹配括号思路一模一样，入栈后消消乐即可

代码实现的时候发服务器托管网现容器类使用toString后就是包含[]的数组，所以需要额外的StringBuilder来满足返回值的需求

class Solution {
    public String removeDuplicates(String s) {
        Deque stack = new LinkedList();
        for (int i = 0 ; i 

150. 逆波兰表达式求值

就是给后缀表达式求值，跟数据结构学的一样，如果是数字就压栈，是操作符就取出两个数出来计算，把结果压栈。

字符串转数字Integer.valueOf()

class Solution {
    public int evalRPN(String[] tokens) {
     Deque stack=new LinkedList();
     for(String s:tokens){
         if(s.equals("+")){
             stack.push(stack.pop()+stack.pop());
         }else if(s.equals("-")){ stack.push(-stack.pop()+stack.pop());}
         else if(s.equals("*")){ stack.push(stack.pop()*stack.pop());}
         else if(s.equals("/")){
             int in1=stack.pop();
             int in2=stack.pop();
             stack.push(in2/in1);

         }
         else{
             stack.push(Integer.valueOf(s));
         }
     }
     return stack.pop();
    }
}

239. 滑动窗口最大值

经典滑动窗口模型，这里直接用deque

在单调队列中存储数组索引来方便判断是否在滑动窗口里面，而单调服务器托管网队列在扫描时首先检查队头是否在窗口内，再保证之前的老元素大于新加入的元素，不然他们就没有利用价值了，全部弹出

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque q = new LinkedList();
        int[] res = new int[nums.length-k+1];
        int count = 0;

        for(int i = 0 ; i = k-1) res[count++] = nums[q.peek()]
        }
        return res;
    }
}

347.前 K 个高频元素

第一反应是用哈希表map，直接存储元素和对应的出现次数，再对map按值排序，但此时时间复杂度需要nlogn，不满足进阶要求

由于没必要对所有元素进行排序，一直维护前k个高频即可，在java中堆定义为优先级队列，本题使用的大顶堆代码如下：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map map = new HashMap();
        for(int i: nums) map.put(i,map.getOrDefault(i,0)+1);
        PriorityQueue pq = new PriorityQueue((x,y)->map.get(y)-map.get(x));
        for(int key : map.keySet()) pq.offer(key);
        
        int[] result = new int[k];
        while(k > 0){
            result[k - 1] = pq.poll();
            k--;
        }
        return result;
    }
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 面试官：来说说vue3是怎么处理内置的v-for、v-model等指令？

前言 最近有粉丝找到我，说被面试官给问懵了。 粉丝：面试官上来就问“一个vue文件是如何渲染成浏览器上面的真实DOM？”，当时还挺窃喜这题真简单。就简单说了一下先是编译成render函数、然后根据render函数生成虚拟DOM，最后就是根据虚拟DOM生成真实D…