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

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;}
}