堆/栈/队列

ゞ浴缸里的玫瑰 2024-03-16 21:53 52阅读 0赞

## 1、 用两个栈实现队列 ##

Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
    
        public void push(int node) {
        
            stack1.push(node);
        }
    
        public int pop() {
        
            while (!stack2.isEmpty()) {
        
                return stack2.pop();
            }
            while (!stack1.isEmpty()) {
        
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }

## 2、 包含min函数的栈 ##

public void push(int node) {
        
            if (stackMin.isEmpty() || node < stackMin.peek()) {
        
                stackMin.push(node);
            } else {
        
                stackMin.push(stackMin.peek());
            }
            stack1.push(node);
        }
    
        public void pop() {
        
            stack1.pop();
            stackMin.pop();
        }
    
        public int top() {
        
            return stack1.peek();
        }
    
        public int min() {
        
            return stackMin.peek();
        }

## 3、有效括号序列 ##

public boolean isValid (String s) {
        
            Stack<Character> stack = new Stack();
            for (int i = 0; i < s.length(); i++) {
        
                char charTemp = s.charAt(i);
                if (charTemp == '(' ) {
        
                    stack.push(')');
                } else  if (charTemp == '{' ) {
        
                    stack.push('}');
                } else  if (charTemp == '[' ) {
        
                    stack.push(']');
                } else {
        
                    if (stack.isEmpty() || stack.pop() != charTemp) {
        
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }

## 4、滑动窗口的最大值 ##

public ArrayList<Integer> maxInWindows (int[] num, int size) {
        
        ArrayList<Integer> arrayRes = new ArrayList();
        if (num.length < size || size == 0) {
        
            return arrayRes;
        }
        ArrayDeque<Integer> arrayQue = new ArrayDeque<Integer>();
        for (int i = 0; i < size; i++) {
        
            while (!arrayQue.isEmpty() && num[arrayQue.peekLast()]  < num[i] ) {
        
                arrayQue.pollLast();
            }
            arrayQue.add(i);
        }
        arrayRes.add(num[arrayQue.peekFirst()]);
        // 1,2,3,4
        for (int i = size; i < num.length; i++) {
        
            if (arrayQue.peekFirst() < i - size + 1) {
        
                arrayQue.pollFirst();
            }
            while (!arrayQue.isEmpty() && num[arrayQue.peekLast()]  < num[i] ) {
        
                arrayQue.pollLast();
            }
            arrayQue.add(i);
            arrayRes.add(num[arrayQue.peekFirst()]);
        }
        return arrayRes;
    }

## 5、最小的K个数 ##

public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        
            ArrayList<Integer> resArray = new ArrayList();
            if(k==0){
        
                return resArray;
            }
            PriorityQueue<Integer> deque = new PriorityQueue<>((o1,o2)->o2.compareTo(o1));
            for(int i=0;i<k;i++){
        
                deque.add(input[i]);
            }
            for(int i=k;i<input.length;i++){
        
                if(input[i] < deque.peek()){
        
                    deque.poll();
                    deque.add(input[i]);
                }
            }
            while(!deque.isEmpty()){
        
               resArray.add(0,deque.poll());
            }
            return resArray;
        }

## 6 寻找第K大 ##

public int findKth (int[] a, int n, int K) {
        
            return findKth(a, 0, n - 1, K);
        }
    
        public int  findKth(int[] a, int l, int r, int K) {
        
            int index = quikSort(a, l, r);
            // 0,1,2,2,3,4
            if (a.length - index == K) {
        
                return a[index];
            } else if (a.length - index > K) {
        
                return findKth(a, index + 1, r, K);
            } else {
        
                return findKth(a, l, index - 1, K);
            }
        }
    
        private int quikSort(int[] a, int l, int r) {
        
            int temp = a[l];
            while (l < r) {
        
                while (l < r && a[r] >= temp) {
        
                    r--;
                }
                if (l == r) {
        
                    break;
                } else {
        
                    a[l++] = a[r];
                }
    
                while (l < r && a[l] < temp) {
        
                    l++;
                }
                if (l == r) {
        
                    break;
                } else {
        
                    a[r] = a[l];
                }
            }
            a[l] = temp;
            return l;
        }

## 7 数据流中的中位数 ##

private List<Integer> nums = new ArrayList();
    
        public void Insert(Integer num) {
        
            if (nums.size() == 0) {
        
                nums.add(num);
            } else {
        
                int i = 0;
                for (; i < nums.size(); i++) {
        
                    int numTemp = nums.get(i);
                    if (num < numTemp) {
        
                        break;
                    }
                }
                nums.add(i, num);
            }
        }
    
        public Double GetMedian() {
        
            if (nums.size() % 2 != 0) {
        
                int numMax = nums.get(nums.size() / 2);
                return Double.valueOf(numMax);
            } else {
        
                int numMax = nums.get(nums.size() / 2 -1) + nums.get(nums.size() / 2);
                return Double.valueOf((double)numMax / 2);
            }
        }

## 8 数据流中的中位数 ##

private static int index = 0;
    
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * 返回表达式的值
         * @param s string字符串 待计算的表达式
         * @return int整型
         */
        public int solve (String s) {
        
            // 示例 1+2 + (3*4*(1+2))
            char oper = '+';
            Stack<Integer> stack = new Stack();
            for (; index < s.length(); index++) {
        
                int intTemp = 0;
                if (s.charAt(index) - '0' > 0  && s.charAt(index) - '0' < 9) {
        
                    while (s.charAt(index) - '0' >= 0  && s.charAt(index) - '0' <= 9) {
        
                        intTemp = intTemp * 10 + s.charAt(index) - '0';
                        index++;
                        if (index == s.length()) {
        
                            break;
                        }
                    }
                    index --;
                } else if (s.charAt(index) == '(') {
        
                    index ++;
                    intTemp = solve(s);
                } else if (s.charAt(index) == ')') {
        
                    break;
                } else {
        
                    oper = s.charAt(index);
                    continue;
                }
                switch (oper) {
        
                    case '+':
                        stack.push(intTemp);
                        break;
                    case '-':
                        stack.push(-intTemp);
                        break;
                    case '*':
                        stack.push(intTemp * stack.pop());
                        break;
                }
            }
            int result = 0;
            while (!stack.isEmpty()) {
        
                result += stack.pop();
            }
            return result;
        }