前沿知识

关于栈也可用

LinkedList<Integer> A = new LinkedList<Integer>();
A.addLast(value);
int a = A.removeLast();

• 栈：Deque<Integer> stack = new LinkedList<>();，push，pop
• 栈：ArrayDeque<Character> stack= new ArrayDeque<>();，ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
• 双端队列：Deque<Integer> deque = new LinkedList<>();，offerLast，peekLast，pollLast等
• 优先队列：

// 使用数组格式进行优先队列
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>(){
    public int compare(int[] a, int[] b){
        // 降序，大根堆
        // 对于value进行排序
        return a[1] - b[1];
    }
});

• 集合的初始化： map.put(nums[i],map.getOrDefault(nums[i],0) + 1);

哈希集合的遍历：

for(Map.Entry<Integer,Integer> entry:map.entrySet()){
int num = entry.getKey(), count = entry.getValue();

// 如果遍历，key或者value：
for(Integer key:map.keySet())

字符转换为数字：Integer.valueOf(s)
数字转换为字符：String.valueOf(n)

232. 用栈实现队列（简单）

题目：leetcode：232. 用栈实现队列

思路如下：

要实现队列的功能，将所有【入栈】的数据放到【出栈】中，输出【出栈】pop即可

class MyQueue {
//创建两个【出栈】【入栈】
Stack<Integer>stkin;
Stack<Integer>stkout;

    //通过初始化构造参数，建立对象
    public MyQueue() {
        stkin=new Stack<>();
        stkout=new Stack<>();
    }
    
    //【入栈】函数专门放入栈的数据
    public void push(int x) {
        stkin.push(x);
    }
    
    //要实现队列的功能，将所有【入栈】的数据放到【出栈】中，输出【出栈】pop即可
    public int pop() {
        //判断【出栈】有无数据
        //如果【出栈】有数据，直接返回【出栈】的pop即可
        //如果【出栈】无数据，则继续将【入栈】的数据都放到【出栈】，最后返回【出栈】数据即可
        if(stkout.isEmpty()){
            while(!stkin.isEmpty()){
                stkout.push(stkin.pop());
            }
        }
        return stkout.pop();
    }
    
    //因为数据可能没有【出栈】就要查询队列的头节点，所以这部分数据，也要进行入栈出栈的操作
    public int peek() {
        //判断【出栈】有无数据
        //如果【出栈】有数据，直接返回【出栈】的pop即可
        //如果【出栈】无数据，则继续将【入栈】的数据都放到【出栈】，最后返回【出栈】数据即可
        if(stkout.isEmpty()){
            while(!stkin.isEmpty()){
                stkout.push(stkin.pop());
            }
        }
        return stkout.peek();
    }
    
    //为空的条件是两个栈都为空，函数为isEmpty()
    public boolean empty() {
        return stkin.isEmpty()&stkout.isEmpty();

    }
}

另一道题目：
剑指 Offer 09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

下面的的代码模块中多一个判断条件

class CQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;
    
    public CQueue() {
        stack1 = new LinkedList<Integer>();
        stack2 = new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }

        //因为源源不断的数据，如果2还是为空，没有添加进去，则返回为-1
        if(stack2.isEmpty()){
            return -1;
        }else return stack2.pop();
      
    }
}

225. 用队列实现栈（简单）

题目：leetcode：225. 用队列实现栈

使用两个队列的思想：

// 队列1用来操作，之后队列1与2进行对换，队列2 来判断栈顶 栈元素，以及出栈

class MyStack {
    // 队列的初始化
    Queue<Integer>queue1;
    Queue<Integer>queue2;
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    public void push(int x) {
        queue1.offer(x);
        while(!queue2.isEmpty()){
            queue1.offer(queue2.poll());
        }

        // 之后1与2进行交换
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    public int pop() {
        return queue2.poll();
    }
    
    public int top() {
        return queue2.peek();
    }
    
    public boolean empty() {
        return queue2.isEmpty();
    }
}

使用一个队列实现栈：

class MyStack {
    // 队列的初始化
    Queue<Integer>queue;
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    public void push(int x) {
        // 此n为 在入栈之前 都要将其重新出入一遍
        int n = queue.size();
        queue.offer(x);

        for(int i = 0;i < n;i++){
            // 队列的出栈 为poll
            queue.offer(queue.poll());
        }
    }
    
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

20. 有效的括号（简单）

题目：leetcode：20. 有效的括号

class Solution {
    public boolean isValid(String s) {
        Map<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');

        Deque<Character> stack = new LinkedList<>();
        for(int i = 0; i < s.length();i++){
            //如果包含这个有括号，则要相应的把左括号去除，判断是否跟peek相等
            if(map.containsKey(s.charAt(i))){
                if(stack.isEmpty() || map.get(s.charAt(i)) != stack.peek()){
                    return false;
                }
                stack.pop();
            }else{
                //如果没有包含这个右括号，则要把左括号进栈，相对应的当前的符号  也就是左括号
                stack.push(s.charAt(i));
            }
        }

        //如果stack还有东西，说明不是有效的括号
        return stack.isEmpty();
    }
}

以下不使用map结构，直接进行比较：

class Solution {
    public boolean isValid(String s) {
         // 不使用map结构，直接进行比较
        Deque<Character> stack = new LinkedList<>();
        for(int i = 0; i < s.length();i++){
            // 单个字符 无法使用equals进行比较判断
            if(s.charAt(i) == '('){
                stack.push(')');
            }else if(s.charAt(i) == '{'){
                stack.push('}');
            }else if(s.charAt(i) == '['){
                stack.push(']');
                // 如果栈为空，或者对应的peek 不相等，则直接返回false
            }else if (stack.isEmpty() ||  stack.peek() != s.charAt(i) ){
                return false;
            }else {
                // 右边的括号配对成功，就会将其右括号出栈
                stack.pop();
            }
        }

        return stack.isEmpty();
    }
}

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

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

直接用栈的格式进行输出：

class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> deque = new LinkedList<>();

        for(int i = 0 ;i < s.length();i++){
            if(!deque.isEmpty() && deque.peek() == s.charAt(i)){
                deque.pop();
            }else {
                deque.push(s.charAt(i));
            }
        }

        String str = "";
        while(!deque.isEmpty()){
            // 加上之前的str ，对应进行输出
            str = deque.pop() + str;
        }
        return str;
    }
}

使用字符串 做类似栈的功能：

class Solution {
    public String removeDuplicates(String s) {
        StringBuffer sb = new StringBuffer();

        // 定义top 模仿数组的下标元素 或者是 栈的top指针
        int top = -1;
        for(int i = 0 ;i < s.length();i++){
            char c = s.charAt(i);
            // 如果top大于等于0 而且两者相等，则对应进行出栈！
            if(top >= 0 && sb.charAt(top) == c){
                // 此处删除的是字符串最后的一个元素
                sb.deleteCharAt(top);
                top--;
            }else {
                sb.append(c);
                top++;
            }
        }

        // 返回的类型为toString
        return sb.toString();
    }
}

150. 逆波兰表达式求值（中等）

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

栈的思想，中序遍历

class Solution {
    public int evalRPN(String[] tokens) {
        // 栈
        Deque<Integer> stack = new LinkedList<>();
        // 遍历的形式 对应模拟算法判断
        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. 滑动窗口最大值（困难）*

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

使用优先队列存储滑动窗口的值，但窗口会移动，对应窗口滑动需要对应判断最大值（将最大值在区间外的对应删除即可）

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int []> queue = new PriorityQueue<>(new Comparator<>(){
            public int compare(int []a,int b[]){
                if(a[0] == b[0]){
                    // 相等的时候，是最新的i排在前面
                    return b[1] - a[1];
                }
                // 不相等的时候 是降序排列
                return b[0] - a[0];
            }
        });
   
        for(int i = 0;i < k;i++){
            queue.add(new int[]{nums[i],i});
        }

        int[] res = new int [nums.length - k +1];
        // 存入第一个窗口的最大值
        res[0] = queue.peek()[0];

        // 遍历后续窗口的最大值，从k开始 
        for(int i = k;i < nums.length;i++){
            queue.add(new int[]{nums[i],i});
            // 判断最大值是否在区间外，如果是区间外，则进行出栈
            while(queue.peek()[1] <= i - k ){
                queue.poll();
            }
            // 对应的华东窗口最左边的值 赋值
            res[i - k + 1] = queue.peek()[0];
        }

        return res;
    }
}

维护一个单调队列，而且是滑动窗口
双端队列的思想：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0 ; i < k ;i++){
            // 每次有新的元素之后 如果大于，就把新的队尾元素给剔除
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
                deque.pollLast();
            }
            // 否则进入到队尾元素
            deque.offerLast(i);
        }

        int[] res = new int [n - k + 1];
        // 存储队头元素，因为队头元素一定最大 （一开始进入的时候就只有大于才能进入，否则会被剔除）
        res[0] = nums[deque.peekFirst()];
        for(int i = k;i < n;i++){
            while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]){
                deque.pollLast();
            }
            deque.offerLast(i);
            
            // 将其队头元素最大 且在区间外的，都把队头元素剔除
            while(deque.peekFirst() <= i - k){
                deque.pollFirst();
            }
            res[i - k + 1] = nums[deque.peekFirst()];

        }
        return res;
    }
}

347. 前 K 个高频元素（中等）*

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

不用堆的逻辑模拟算法：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            // 查看是否存在，通过map.containsKey
            if(!map.containsKey(nums[i])){
                map.put(nums[i],1);
            }else{
                map.put(nums[i],map.get(nums[i]) + 1);
            }
        }

        int max = Integer.MIN_VALUE;
        // 注意hashmap的遍历
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue() > max){
                max = entry.getValue();
            }
        }

        int []res = new int[k];
        while(k > 0){
            for(Map.Entry<Integer,Integer> entry:map.entrySet()){
                if(entry.getValue() == max){
                    // 此处数组 为k-1
                    res[k - 1] = entry.getKey();
                    k--;
                }
            }
            // 最大的数值往下降的判断
            max--;
        }

        return res;
    }
}

增加map集合的判断
还可以使用如下方式：getOrDefault

for (int num : nums) {
	map.put(num, map.getOrDefault(num, 0) + 1);
}

另外一种思路写法，使用优先队列（本身就有堆的思想）

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

        // 这个用法记住
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer a, Integer b){
                // 降序，大根堆
                return map.get(a) - map.get(b);
            }
        });


        for(Integer key:map.keySet()){
            if(queue.size() < k){
                queue.add(key);
            }else if (map.get(key) > map.get(queue.peek())){
                queue.poll();
                queue.add(key);
            }
        }

        int []res = new int[k];
        int index = 0;
        while(!queue.isEmpty()){
            res[index++] = queue.poll();
        }
        return res;
    }
}

另外一种更加简易的写法：

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

        // 对应的优先队列只设置value即可
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->map.get(o2)-map.get(o1));
        
        // 直接把所有值都存，弹出优先队列的前k个即可
        for(Integer Key:map.keySet()){      
            queue.add(Key);
        }

        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            res[i] = queue.poll();
        }
        return res;
    }
}

和上面的代码思路差不多，但有所差别：

存入优先队列上面代码的思路是只有value
下面的思路是key以及value的数组

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

        // 使用数组格式进行优先队列
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                // 降序，大根堆
                // 对于value进行排序
                return a[1] - b[1];
            }
        });

        // map集合遍历
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            int num = entry.getKey(), count = entry.getValue();
            if(queue.size() < k){
                queue.add(new int[]{num, count});
                // 如果当前值的value小于 优先队列的peek的value（本身存进优先队列就是key value）
            }else if (count > queue.peek()[1]){
                queue.poll();
                queue.add(new int[]{num, count});
            }
        }

        int []res = new int[k];
        int index = 0;
        while(!queue.isEmpty()){
            res[index++] = queue.poll()[0];
        }
        return res;
    }
}