堆/栈/队列
BM42 用两个栈实现队列
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
// 入栈
public void push(int node) {
stack1.push(node);
}
// 出栈
public int pop() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
// 非法操作，返回-1
if (stack2.isEmpty()) return -1;
return stack2.pop();
}
}
BM43 包含min函数的栈
import java.util.Stack;
public class Solution {
Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> minStack = new Stack<Integer>();
public void push(int node) {
stack.push(node);
if (minStack.isEmpty()){// min栈为空
minStack.push(node);
return;
}
// min栈非空，则比较栈顶元素和当前元素，放入更小的
minStack.push(Math.min(minStack.peek(), node));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}
BM44 有效括号序列
public class Solution {
Stack<Character> stk = new Stack<Character>();
public boolean isValid (String s) {
for (char ch : s.toCharArray()) {// 左括号，直接入栈
if (ch == '(' || ch == '[' || ch == '{') {
stk.push(ch);
}else{// 右括号，则与栈顶匹配
if(stk.isEmpty()) return false;
char c = stk.pop();
if ((c == '(' && ch == ')') || (c == '[' && ch == ']') || (c == '{' && ch == '}')) continue;
else return false;
}
}
return stk.isEmpty();
}
}
BM45 滑动窗口的最大值
import java.util.*;
public class Solution {
public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> ans = new ArrayList<>();
int len = num.length;
// 窗口大于数组长度或窗口长度为0，返回空。
if(len == 0 || len < size || size == 0) return ans;
// 创建左右指针
int left = 0, right = size - 1;
// 寻找第一个窗口中的最大值
int max = maxValue(num, left, right);
ans.add(max);
// 移动窗口
while(++right < len){
if(num[right] > max){// 如果右边第一个值大于max,则其为最大值
max = num[right];// 更新最大值
ans.add(max);// 添加结果
left++;
}else if(num[left] == max){
// 如果前一个窗口的最大值为左边界的值，则需要重新更新计算最大值
max = maxValue(num, ++left, right);
ans.add(max);
}else{// 否则，最大值依旧在窗口中，无需重新计算
ans.add(max);
left++;
}
}
return ans;
}
// 计算窗口中的最大值
public int maxValue(int[] num, int left, int right){
int max = Integer.MIN_VALUE;// 记录当前最大值
// 寻找窗口中的最大值
for (int i = left; i <= right; i++) {
max = Math.max(max, num[i]);
}
return max;
}
}
BM46 最小的K个数
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> ans = new ArrayList<>();
if(k == 0 || input.length == 0) return ans;
PriorityQueue<Integer> pqueue = new PriorityQueue<Integer>(2, (a, b) -> (a - b));
for (int i = 0; i < input.length; i++) {
pqueue.add(input[i]);
}
for (int i = 0; i < k; i++) {
ans.add(pqueue.poll());
}
return ans;
}
}
BM47 寻找第K大
import java.util.*;
public class Solution {
// public int findKth(int[] nums, int n, int K) {
// int index = n - K;
// int left = 0, right = n - 1;
// while(left <= right){
// int part = partition(nums, left, right);
// if(part < index){// part左边的个数少于n-k个
// left = part + 1;
// }else if(part > index){// part左边的个数多于n-k个
// right = part - 1;
// }else{// part左边的个数等于n-k个
// return nums[part];
// }
// }
// return -1;
// }
// // 确定分区位置，该位置左边的元素均小于等于当前值，右边的均大于等于当前值
// public int partition(int[] nums, int left, int right){
// if (left == right) return left;
// int partValue = nums[left];
// int low = left, high = right + 1;
// while(true){
// while(nums[++low] < partValue){
// if(low == high) break;
// }
// while(nums[--high] > partValue){
// if(low == high) break;
// }
// if (low >= high) break;
// swap(nums, low, high);
// }
// swap(nums, left, high);
// return high;
// }
// public void swap(int[] nums, int a, int b){
// nums[a] = nums[a] ^ nums[b];
// nums[b] = nums[a] ^ nums[b];
// nums[a] = nums[a] ^ nums[b];
// }
// public void shuffle(int[] nums){
// int n = nums.length;
// Random rand = new Random();
// for(int i = 0; i < n; i++){
// int r = i + rand.nextInt(n - i);
// swap(nums, i, r);
// }
// }
public int findKth(int[] nums, int n, int k) {
int lo = 0, hi = nums.length - 1;
// 索引转化
k = nums.length - k;
while (lo <= hi) {
// 在 nums[lo..hi] 中选一个分界点
int p = partition(nums, lo, hi);
if (p < k) {
// 第 k 大的元素在 nums[p+1..hi] 中
lo = p + 1;
} else if (p > k) {
// 第 k 大的元素在 nums[lo..p-1] 中
hi = p - 1;
} else {
// 找到第 k 大元素
return nums[p];
}
}
return -1;
}
int partition(int[] nums, int lo, int hi) {
if (lo == hi) return lo;
// 将 nums[lo] 作为默认分界点 pivot
int pivot = nums[lo];
// j = hi + 1 因为 while 中会先执行 --
int i = lo, j = hi + 1;
while (true) {
// 保证 nums[lo..i] 都小于 pivot
while (nums[++i] < pivot) {
if (i == hi) break;
}
// 保证 nums[j..hi] 都大于 pivot
while (nums[--j] > pivot) {
if (j == lo) break;
}
if (i >= j) break;
// 如果走到这里，一定有：
// nums[i] > pivot && nums[j] < pivot
// 所以需要交换 nums[i] 和 nums[j]，
// 保证 nums[lo..i] < pivot < nums[j..hi]
swap(nums, i, j);
}
// 将 pivot 值交换到正确的位置
swap(nums, j, lo);
// 现在 nums[lo..j-1] < nums[j] < nums[j+1..hi]
return j;
}
// 交换数组中的两个元素
void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
BM48 数据流中的中位数
import java.util.*;
public class Solution {
private int cnt = 0;
private PriorityQueue<Integer> low = new PriorityQueue<>();
// 默认维护小顶堆
private PriorityQueue<Integer> high = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2.compareTo(o1);
}
});
public void Insert(Integer num) {
// 数量++
cnt++;
// 如果为奇数的话
if ((cnt & 1) == 1) {
// 由于奇数，需要存放在大顶堆上
// 但是呢，现在你不知道num与小顶堆的情况
// 小顶堆存放的是后半段大的数
// 如果当前值比小顶堆上的那个数更大
if (!low.isEmpty() && num > low.peek()) {
// 存进去
low.offer(num);
// 然后在将那个最小的吐出来
num = low.poll();
} // 最小的就放到大顶堆，因为它存放前半段
high.offer(num);
} else {
// 偶数的话，此时需要存放的是小的数
// 注意无论是大顶堆还是小顶堆，吐出数的前提是得有数
if (!high.isEmpty() && num < high.peek()) {
high.offer(num);
num = high.poll();
} // 大数被吐出，小顶堆插入
low.offer(num);
}
}
public Double GetMedian() {// 表明是偶数
double res = 0;
// 奇数
if ((cnt & 1) == 1) {
res = high.peek();
} else {
res = (high.peek() + low.peek()) / 2.0;
}
return res;
}
}
BM49 表达式求值
import java.util.*;
public class Solution {
// 使用 map 维护一个运算符优先级（其中加减法优先级相同，乘法有着更高的优先级）
Map<Character, Integer> map = new HashMap<Character, Integer>(){{
put('-', 1);
put('+', 1);
put('*', 2);
}};
public int solve(String s) {
// 将所有的空格去掉
s = s.replaceAll(" ", "");
char[] cs = s.toCharArray();
int n = s.length();
// 存放所有的数字
Deque<Integer> nums = new ArrayDeque<>();
// 为了防止第一个数为负数，先往 nums 加个 0
nums.addLast(0);
// 存放所有「非数字以外」的操作
Deque<Character> ops = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
char c = cs[i];
if (c == '(') {
ops.addLast(c);
} else if (c == ')') {
// 计算到最近一个左括号为止
while (!ops.isEmpty()) {
if (ops.peekLast() != '(') {
calc(nums, ops);
} else {
ops.pollLast();
break;
}
}
} else {
if (isNumber(c)) {
int u = 0;
int j = i;
// 将从 i 位置开始后面的连续数字整体取出，加入 nums
while (j < n && isNumber(cs[j])) u = u * 10 + (cs[j++] - '0');
nums.addLast(u);
i = j - 1;
} else {
if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
nums.addLast(0);
}
// 有一个新操作要入栈时，先把栈内可以算的都算了
// 只有满足「栈内运算符」比「当前运算符」优先级高/同等，才进行运算
while (!ops.isEmpty() && ops.peekLast() != '(') {
char prev = ops.peekLast();
if (map.get(prev) >= map.get(c)) {
calc(nums, ops);
} else {
break;
}
}
ops.addLast(c);
}
}
}
// 将剩余的计算完
while (!ops.isEmpty() && ops.peekLast() != '(') calc(nums, ops);
return nums.peekLast();
}
// 计算逻辑：从 nums 中取出两个操作数，从 ops 中取出运算符，然后根据运算符进行计算即可
void calc(Deque<Integer> nums, Deque<Character> ops) {
if (nums.isEmpty() || nums.size() < 2) return;
if (ops.isEmpty()) return;
int b = nums.pollLast(), a = nums.pollLast();
char op = ops.pollLast();
int ans = 0;
if (op == '+') ans = a + b;
else if (op == '-') ans = a - b;
else if (op == '*') ans = a * b;
nums.addLast(ans);
}
boolean isNumber(char c) {
return Character.isDigit(c);
}
}
