欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法-栈和队列

程序员文章站 2022-03-13 10:37:35
...

LeetCode_20 判断括号是否合法

Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
Input: “()[]{}”
Output: true
Input: “{[]}”
Output: true

新建一个栈,然后遍历字符串,如果遇到左括号,直接压入栈中;如果遇到右括号,则弹出一个栈顶元素,将二者进行匹配,如果二者不匹配,直接返回false;如果匹配,则继续遍历。遍历结束之后,判断栈内元素是否为空,如果为空,则说明括号是合法的。
代码:
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        for (Character c :s.toCharArray()){
            if (!map.containsKey(c)){
                stack.push(c);
            }else {
                if (stack.isEmpty() || map.get(c) != stack.pop()){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

LeetCode_225 使用队列实现栈结构

Implement the following operations of a stack using queues.
push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
empty() – Return whether the stack is empty.

使用两个队列,一个队列queue用于存放元素和取元素,另一个队列tmp用于临时存放元素。当执行push方法时,需要把queue中的元素取出临时放在tmp队列中,然后把需要push的元素放入queue中,再将tmp队列中的元素放回queue中。

数据结构与算法-栈和队列

执行pop方法时,只需调用queue队列的poll方法取出队列头的元素。执行top方法时,调用queue队列的peek方法返回队列头元素。执行empty方法需判断queue是否为空。
代码:
class MyStack {
        LinkedList<Integer> queue;
        LinkedList<Integer> tmp;
        /** Initialize your data structure here. */
        public MyStack() {
            queue = new LinkedList<Integer>();
            tmp = new LinkedList<Integer>();
        }

        /** Push element x onto stack. */
        public void push(int x) {
            while (!queue.isEmpty()){
                tmp.offer(queue.poll());
            }
            queue.offer(x);
            while (!tmp.isEmpty()){
                queue.offer(tmp.poll());
            }
        }

        /** Removes the element on top of the stack and returns that element. */
        public int pop() {
           return queue.poll();
        }

        /** Get the top element. */
        public int top() {
            return queue.peek();
        }

        /** Returns whether the stack is empty. */
        public boolean empty() {
            return queue.isEmpty() && tmp.isEmpty();
        }
    }

LeetCode_232 使用栈实现队列

Implement the following operations of a queue using stacks.
push(x) – Push element x to the back of queue.
pop() – Removes the element from in front of queue.
peek() – Get the front element.
empty() – Return whether the queue is empty.

使用两个栈pushStack和popStack,执行push方法时,直接把元素push到pushStack;执行pop和peek方法时,如果popStack中有元素,直接执行popStack的pop或peek;如果popStack中没有元素,把pushStack中的元素一次性全倒入popStack,然后再执行popStack的pop或peek。
代码:
    class MyQueue {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        /** Initialize your data structure here. */
        public MyQueue() {

        }

        /** Push element x to the back of queue. */
        public void push(int x) {
            stack1.push(x);
        }

        /** Removes the element from in front of queue and returns that element. */
        public int pop() {
            if (stack2.isEmpty()){
                while (!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }

        /** Get the front element. */
        public int peek() {
            if (stack2.isEmpty()){
                while (!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.peek();
        }

        /** Returns whether the queue is empty. */
        public boolean empty() {
            return stack1.isEmpty()&&stack2.isEmpty();
        }
    }

LeetCode_239 滑动窗口的最大值

给定一个数组,有一个k大小的窗口从数组最左滑动到最右,窗口每向右滑动一个位置,返回窗口中k个元素的最大值。

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
Example:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]

代码:
class Solution {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0){
            return nums;
        }
        //用于保存结果的数组,长度为nums.length - k + 1
        int[] res = new int[nums.length - k + 1];
        //双端队列,里面存放数组下标,队头元素对应的数组值是窗口滑动中的最大值
        LinkedList<Integer> queue = new LinkedList<>();
        //res结果数组下标
        int count = 0;
        //遍历数组
        for (int i=0; i<nums.length; i++){
            //如果队尾元素对应的数组值小于数组当前值,则取出队尾元素
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
                queue.pollLast();
            }
            //把当前数组下标加入队尾
            queue.addLast(i);
            //数组当前下标与队头元素的差值等于k时,说明队头元素已过期,需要移除
            if (i >= queue.peekFirst() + k){
                queue.pollFirst();
            }
            //当前数组下标遍历到k-1时,开始保存结果,结果值是队头元素对应的数组值
            if (i >= k-1){
                res[count++] = nums[queue.peekFirst()];
            }
        }
        return res;
    }
}

LeetCode_703 返回数据流中第K大的元素

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Example:
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8

建立一个由k个元素组成的小根堆,堆顶的元素就是k个元素中的最小值,也就是第k大的元素,当往小根堆中添加元素时,如果需要添加的元素大于堆顶元素,则移除堆顶元素,然后加入新元素,并调整堆结构,再返回堆顶值。可以使用默认的PriorityQueue作为小根堆。如果需要大根堆,则使用PriorityQueue带有Comparator的构造方法即可。
代码:
class KthLargest {
    private int k;
    private PriorityQueue<Integer> queue;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        queue = new PriorityQueue<>(k);
        for (int n : nums){
            add(n);
        }
    }

    public int add(int val) {
        if (queue.size() < k){
            queue.offer(val);
        }else if (queue.peek() <val){
            queue.poll();
            queue.offer(val);
        }
        return queue.peek();
    }
}