算法练习（3）：牛客在线编程04 堆/栈/队列

怼烎@ 2023-10-14 08:42 48阅读 0赞

package jz.bm;
    
    import java.util.*;
    
    public class bm4 {
        
        /**
         * BM42 用两个栈实现队列
         */
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        public void push(int node) {
        
            stack1.push(node);
        }
        public int pop() {
        
            while (!stack1.isEmpty()) {
        
                stack2.push(stack1.pop());
            }
            int res = stack2.pop();
            while (!stack2.isEmpty()) {
        
                stack1.push(stack2.pop());
            }
            return res;
        }
    
        /**
         * BM43 包含min函数的栈
         */
        Stack<Integer> stack42 = new Stack<>();
        Stack<Integer> stack42min = new Stack<>();
        public void push42(int node) {
        
            stack42.push(node);
            if (stack42min.isEmpty()) {
        
                stack42min.push(node);
            } else {
        
                if (node < stack42min.peek()) {
        
                    stack42min.push(node);
                } else {
        
                    stack42min.push(stack42min.peek());
                }
            }
        }
        public void pop42() {
        
            stack42.pop();
            stack42min.pop();
        }
        public int top42() {
        
            return stack42.peek();
        }
        public int min42() {
        
            return stack42min.peek();
        }
    
        /**
         * BM44 有效括号序列
         */
        public boolean isValid (String s) {
        
            if (s.length() == 0) {
        
                return true;
            }
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
        
                if (s.charAt(i) == '(') {
        
                    stack.push(')');
                } else if (s.charAt(i) == '{') {
        
                    stack.push('}');
                } else if (s.charAt(i) == '[') {
        
                    stack.push(']');
                } else {
        
                    if (stack.size() != 0 && stack.peek() == s.charAt(i)) {
        
                        stack.pop();
                    } else {
        
                        stack.push(s.charAt(i));
                    }
                }
            }
            return stack.size() <= 0;
        }
    
        /**
         * BM45 滑动窗口的最大值
         */
        public ArrayList<Integer> maxInWindows (int[] num, int size) {
        
            ArrayList<Integer> res = new ArrayList<>();
            if (size > num.length || size == 0) {
        
                return res;
            }
            PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2 - o1);
            //初始化
            for (int i = 0; i < size; i++) {
        
                priorityQueue.add(num[i]);
            }
            res.add(priorityQueue.peek());
            for (int i = size; i < num.length; i++) {
        
                priorityQueue.remove(num[i - size]);
                priorityQueue.add(num[i]);
                res.add(priorityQueue.peek());
            }
            return res;
        }
    
        /**
         * BM46 最小的K个数
         */
        public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        
            ArrayList<Integer> res = new ArrayList<>();
            if (input.length == 0) {
        
                return res;
            }
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            for (int i = 0; i < input.length; i++) {
        
                queue.add(input[i]);
            }
            for (int i = 0; i < k; i++) {
        
                res.add(queue.peek());
                queue.poll();
            }
            return res;
        }
    
        /**
         * BM47 寻找第K大
         */
        public int findKth (int[] a, int n, int K) {
        
            PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
            for (int i = 0; i < n; i++) {
        
                queue.add(a[i]);
            }
            for (int i = 0; i < K - 1; i++) {
        
                queue.poll();
            }
            return queue.peek();
        }
    
        /**
         * BM48 数据流中的中位数
         */
        ArrayList<Integer> list48 = new ArrayList<>();
        public void Insert(Integer num) {
        
            if (list48.size() == 0) {
        
                list48.add(num);
            } else {
        
                //插入排序
                int j = 0;
                for (; j < list48.size(); j++) {
        
                    if (num < list48.get(j)) {
        
                        break;
                    }
                }
                list48.add(j, num);
            }
        }
    
        public Double GetMedian() {
        
            int n = list48.size();
            if (n % 2 == 0) {
        
                double a = list48.get(n / 2 - 1);
                double b = list48.get(n / 2);
                return (a + b) / 2.0;
            } else {
        
                return (double) list48.get(n / 2);
            }
        }
    
        /**
         * BM49 表达式求值
         */
        public int solve (String s) {
        
            return recursion(s, 0).get(0);
        }
    
        private ArrayList<Integer> recursion(String s, int index) {
        
            Stack<Integer> stack = new Stack<>();
            int num = 0; //每一个因子
            int i;
            char op = '+'; //默认为+，相当于 0 + 表达式
            for (i = index; i < s.length(); i++) {
        
                if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
        
                    num = num * 10 + s.charAt(i) - '0';
                    //不是最后一个字符，继续判断是否为数字
                    if (i != s.length() - 1) {
        
                        continue;
                    }
                }
                //遇到（将括号内当成一个数字
                if (s.charAt(i) == '(') {
        
                    ArrayList<Integer> res = recursion(s, i + 1);
                    num = res.get(0);
                    i = res.get(1);
                    if (i != s.length() - 1) {
        
                        continue;
                    }
                }
                //数字取完需要计算
                //当前数字前面的操作符
                switch (op) {
        
                    case '+' :
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        int temp = stack.pop();
                        stack.push(temp * num);
                        break;
                }
                num = 0;
                //遇到）结束当前表达式
                if (s.charAt(i) == ')') {
        
                    break;
                } else {
        
                    op = s.charAt(i);
                }
            }
            int sum = 0;
            while (!stack.isEmpty()) {
        
                sum += stack.pop();
            }
            //记录当前表达式的结果和在字符串的位置
            ArrayList<Integer> list = new ArrayList<>();
            list.add(sum);
            list.add(i);
            return list;
        }
    }