代码随想三刷栈与队列篇

232.用栈实现队列

题目

链接

代码

class MyQueue {
    Deque<Integer> in;//只接受元素
    Deque<Integer> out;//输出元素，这里的元素没有了，才
    public MyQueue() {
        in  = new LinkedList();
        out  = new LinkedList();
    }
    
    public void push(int x) {
        in.addLast(x);
    }
    
    public int pop() {
        reserve();
        return out.removeLast();
    }
    
    public int peek() {
        reserve();
        return out.getLast();
    }
    
    public boolean empty() {
        return in.isEmpty()&&out.isEmpty();
    }
    //拿元素之前，需要把in移到out里，相当于反转。
    private void reserve(){
        //如果out栈中有，则不能反转
        if(!out.isEmpty()){
            return;
        }
        while(!in.isEmpty()){
            out.addLast(in.removeLast());
        }
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

225. 用队列实现栈

题目

链接

代码

class MyStack {
    Deque<Integer> in1;//缓存1
    Deque<Integer> in2;//缓存2
    boolean flag1;//默认暂存到1中
    public MyStack() {
        in1 = new LinkedList();
        in2 = new LinkedList();
        flag1 = true;
    }
    
    public void push(int x) {
        if(flag1){
            in1.addLast(x);
        }else{
            in2.addLast(x);
        }
    }
    
    public int pop() {
        reverse();
        int result=flag1?in1.removeFirst():in2.removeFirst();
        flag1 = !flag1;
        return result;
    }
    
    public int top() {
        reverse();
        return flag1?in1.getFirst():in2.getFirst();
    }
    //让缓存里只有最新一个值
    private void reverse(){
        if(flag1){//1做缓存
            while(in1.size()>1){
                in2.addLast(in1.removeFirst());
            }
        }else{//2做缓存
            while(in2.size()>1){
                in1.addLast(in2.removeFirst());
            }
        }
    }
    
    public boolean empty() {
        return in1.isEmpty()&&in2.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

20. 有效的括号

题目

链接

代码

class Solution {
    public boolean isValid(String s) {
        char[] arr = s.toCharArray();
        Deque<Character> stack = new LinkedList();

        for(int i = 0;i<arr.length;i++){
            char temp = arr[i];
            if(temp=='('||temp=='{'||temp=='['){
                stack.addLast(temp);
            }else {
                if(stack.isEmpty()){
                    return false;
                }
                char st = stack.removeLast();
                if(temp == ')'&&st!='('){    
                    return false;
                }else if(temp == '}'&&st!='{'){
                    return false;
                }else if(temp == ']'&&st!='['){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

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

题目

链接

代码

class Solution {
    public String removeDuplicates(String s) {
        char[] arrS = s.toCharArray();
        Deque<Character> stack = new LinkedList();
        for(int i=0;i<arrS.length;i++){
            if(stack.isEmpty()){
                stack.addLast(arrS[i]);
            }else{
                char t = stack.getLast();
                if(t==arrS[i]){
                    stack.removeLast();
                }else{
                    stack.addLast(arrS[i]);
                }
            }
        }
        char[] result = new char[stack.size()];
        for(int i=0;i<result.length;i++){
            result[i] = stack.removeFirst();
        }
        return String.valueOf(result);
    }
}

150. 逆波兰表达式求值

题目

链接

代码

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList();
        for(int i =0;i<tokens.length;i++){
            int num2 = -1;
            int num1 = -1;
            if("+".equals(tokens[i])){
                num2 = stack.removeLast();
                num1 = stack.removeLast();
                stack.addLast(num1+num2);
            }else if("-".equals(tokens[i])){
                num2 = stack.removeLast();
                num1 = stack.removeLast();
                stack.addLast(num1-num2);
            }else if("*".equals(tokens[i])){
                num2 = stack.removeLast();
                num1 = stack.removeLast();
                stack.addLast(num1*num2);
            }else if("/".equals(tokens[i])){
                num2 = stack.removeLast();
                num1 = stack.removeLast();
                stack.addLast(num1/num2);
            }else{
                stack.addLast(Integer.valueOf(tokens[i]));
            }
        }
        return stack.removeLast();
    }
}

239. 滑动窗口最大值

题目

链接

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> queue = new LinkedList();//存下标
        List<Integer> result = new ArrayList();
        for(int i = 0;i<nums.length;i++){
            if(queue.isEmpty()){//如果为空直接加
                queue.addLast(i);
            }else{
                if(nums[queue.getLast()]>nums[i]){//小的直接加
                    queue.addLast(i);
                }else{
                    while(!queue.isEmpty()&&nums[queue.getLast()]<=nums[i]){
                        queue.removeLast();
                    }
                    queue.addLast(i);
                }
            }
            while(!queue.isEmpty()&&queue.getFirst()<i-k+1){
                queue.removeFirst();
            }

            if(i<k-1){//不需要记录 前k-1个不需要记录最大值
                continue;
            }
            result.add(nums[queue.getFirst()]);
        }
        int[] reArr = new int[result.size()];
        for(int i = 0;i<reArr.length;i++){
            reArr[i] = result.get(i);
        }


        return reArr;
    }
}

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.put(
                nums[i]
                ,map.getOrDefault(nums[i],0)+1
            );
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>( (e1,e2)->e2[1]-e1[1]);
        for(var va : map.entrySet()){
            pq.add(new int[]{va.getKey(),va.getValue()});
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) { //依次从队头弹出k个,就是出现频率前k高的元素
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}