堆、栈、队列（牛客）
题目来自牛客题目库 算法篇面试必刷TOP101。
BM42 用两个栈实现队列(简单)
题目
用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。
数据范围：n≤1000
要求：存储n个元素的空间复杂度为 O(n) ，插入与删除的时间复杂度都是 O(1)
示例：
输入：["PSH1","PSH2","POP","POP"]
返回值：1,2
说明：
"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素，先进先出=>返回1
"POP“:代表删除一个元素，先进先出=>返回2
解法
import java.util.*;
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()) {
int node = stack1.pop();
stack2.push(node);
}
}
int node = stack2.pop();
return node;
}
}
BM43 包含min函数的栈(简单)
题目
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
此栈包含的方法有：
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素
数据范围：操作数量满足 0≤n≤300 ，输入的元素满足 ∣val∣≤10000 进阶：栈的各个操作的时间复杂度是 O(1)，空间复杂度是 O(n)
示例:
输入: ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
输出: -1,2,1,-1
解析:
"PSH-1"表示将-1压入栈中，栈中元素为-1
"PSH2"表示将2压入栈中，栈中元素为2，-1
“MIN”表示获取此时栈中最小元素==>返回-1
"TOP"表示获取栈顶元素==>返回2
"POP"表示弹出栈顶元素，弹出2，栈中元素为-1
"PSH1"表示将1压入栈中，栈中元素为1，-1
"TOP"表示获取栈顶元素==>返回1
“MIN”表示获取此时栈中最小元素==>返回-1
解法 双栈
两个栈，第一个栈正常出栈入栈，第二个栈最小值出栈入栈，且保证栈顶为当前最小值。push时第二个栈为空，则直接入第二个栈。第二个栈不为空，则判断入栈值是否小于栈顶值：如果小于栈顶值，该值入栈；如果不小于栈顶值，栈顶值入栈。这样可以保证在若干出栈和入栈操作后，第二个栈的栈顶值为第一个栈的最小值。
import java.util.*;
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public void push(int node) {
stack1.push(node);
if(stack2.isEmpty()) {
stack2.push(node);
}
else {
// 获取栈顶元素的方法peek()
if(node < stack2.peek()) {
stack2.push(node);
}
else {
stack2.push(stack2.peek());
}
}
}
public void pop() {
stack1.pop();
stack2.pop();
}
public int top() {
return stack1.peek();
}
public int min() {
return stack2.peek();
}
}
BM44 有效括号序列(简单)
题目
给出一个仅包含字符’(‘,’)’,’{‘,’}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列 括号必须以正确的顺序关闭，”()”和”()[]{}”都是合法的括号序列，但”(]”和”([)]”不合法。
数据范围：字符串长度 0≤n≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)
示例：
示例1：
输入："["
返回值：false
示例2：
输入："[]"
返回值：true
解法 栈
遇到左括号，入栈右括号。这样当遇到右括号时可以直接通过判断跟栈顶是否相等来判断括号是否匹配。
import java.util.*;
public class Solution {
public boolean isValid (String s) {
Stack<Character> stack = new Stack<>();
// 字符串的length()方法必须加括号，数组的length不加括号
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.isEmpty() || stack.pop() != s.charAt(i))
return false;
}
return stack.isEmpty();
}
}
BM45 滑动窗口的最大值(较难)(没看懂)
题目
给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
窗口大于数组长度或窗口长度为0的时候，返回空。
数据范围： 1≤n≤10000，0≤size≤10000，数组中每个元素的值满足 0∣val∣≤10000
要求：空间复杂度 O(n)，时间复杂度 O(n)
示例：
示例1：
输入：[2,3,4,2,6,2,5,1],3
返回值：[4,4,6,6,6,5]
示例2：
输入：[9,10,9,-7,-3,8,2,-6],5
返回值：[10,10,9,8]
示例3：
输入：[1,2,3,4],5
返回值：[]
解法
BM46 最小的K个数(中等)
题目
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：0≤k,n≤10000，数组中每个数的大小0≤val≤1000
要求：空间复杂度 O(n)，时间复杂度 O(nlogk)
示例：
示例1：
输入：[4,5,1,6,2,7,3,8],4
返回值：[1,2,3,4]
说明：返回最小的4个数即可，返回[1,3,2,4]也可以
示例2：
输入：[1],0
返回值：[]
示例3：
输入：[0,1,2,1,2],3
返回值：[0,1,1]
解法 大根堆
数据结构：大根堆和小根堆的声明和方法：
// 大根堆
PriorityQueue<Integer> q1 = new PriorityQueue<>((o1, o2)-> o2 - o1);
// 小根堆
PriorityQueue<Integer> q2 = new PriorityQueue<>((o1, o2)-> o1 - o2);
q1.add(10);
q1.peek();
q1.poll();
该题解法：
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2)-> o2 - o1);
if(k == 0 || input.length < k)
return res;
for(int i = 0; i < k; i++) {
queue.add(input[i]);
}
for(int i = k; i < input.length; i++) {
if(queue.peek() > input[i]) {
queue.poll();
queue.add(input[i]);
}
}
for(int i = 0; i < k; i++) {
res.add(queue.poll());
}
return res;
}
}
BM47 寻找第K大(中等)
题目
有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
给定一个整数数组 a , 同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
要求：时间复杂度 O(nlogn)，空间复杂度 O(1)
数据范围：0≤n≤1000， 1≤K≤n，数组中每个元素满足 0≤val≤10000000
示例：
示例1：
输入：[1,3,5,2,2],5,3
返回值：2
示例2：
输入：[10,10,9,9,8,7,5,6,4,3,4,2],12,3
返回值：9
说明：去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9
解法 快速排序、二分
- step 1：进行一次快排，大元素在左，小元素在右，得到的标杆j点.在此之前要使用随机数获取标杆元素，防止数据分布导致每次划分不能均衡。
- step 2：如果 j + 1 = k ，那么j点就是第K大。
- step 3：如果 j + 1 > k，则第k大的元素在左半段，更新high = j - 1，执行step 1。
- step 4：如果 j + 1 < k，则第k大的元素在右半段，更新low = j + 1, 再执行step 1.
import java.util.*;
public class Solution {
//交换函数
Random r = new Random();
public static void swap(int arr[], int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public int partition(int[] a, int low, int high, int k){
//随机快排划分
// r.nextInt()方法获取随机int值；快排选择的标杆的下标为x
int x = Math.abs(r.nextInt()) % (high - low + 1) + low;
// 将标杆的值移动到最左边
swap(a, low, x);
// 标杆的值为v
int v = a[low];
// 左右指针分别为i j
int i = low + 1;
int j = high;
while(true){
//小于标杆的在右
while(j >= low + 1 && a[j] < v)
j--;
//大于标杆的在左
while(i <= high && a[i] > v)
i++;
if(i > j)
break;
swap(a, i, j);
i++;
j--;
}
swap(a, low, j);
//从0开始，所以为第j+1大
if(j + 1 == k)
return a[j];
//继续划分
else if(j + 1 < k)
return partition(a, j + 1, high, k);
else
return partition(a, low, j - 1, k);
}
public int findKth(int[] a, int n, int K) {
return partition(a, 0, n - 1, K);
}
}
BM48 数据流中的中位数(中等)
题目
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
数据范围：数据流中数个数满足 1≤n≤1000 ，大小满足1≤val≤1000
进阶： 空间复杂度 O(n) ， 时间复杂度 O(nlogn)
示例：
示例1：
输入：[5,2,3,4,1,6,7,0,8]
返回值："5.00 3.50 3.00 3.50 3.00 3.50 4.00 3.50 4.00 "
说明：数据流里面不断吐出的是5,2,3...,则得到的平均数分别为5,(5+2)/2,3...
示例2：
输入：[1,1,1]
返回值："1.00 1.00 1.00 "
解法1 堆排序
大根堆存储较小的值（顶部最大），小根堆存储较大的值（顶部最小），平衡时令小根堆的节点数等于大根堆的节点数，或者小根堆的节点数比大根堆的多1，这样要么小根堆的顶是中位数，要么小根堆的顶和大根堆的顶的平均数是中位数。
import java.util.*;
public class Solution {
// 初始化小根堆
PriorityQueue<Integer> min = new PriorityQueue<>();
// 初始化大根堆
PriorityQueue<Integer> max = new PriorityQueue<>((x, y)->y - x);
public void Insert(Integer num) {
min.add(num);
max.add(min.poll());
if(min.size() < max.size()){
min.add(max.poll());
}
}
public Double GetMedian() {
if(min.size() > max.size())
return (double)min.peek();
else
return (double)(min.peek() + max.peek()) / 2;
}
}
解法2 插入排序
import java.util.*;
public class Solution {
ArrayList<Integer> arr = new ArrayList<>();
public void Insert(Integer num) {
if (arr.isEmpty())
arr.add(num);
else {
int i = 0;
//遍历找到插入点；ArrayList类的对象不能用length求长度，要用size()
for(; i < arr.size(); i++){
if(num <= arr.get(i))
break;
}
//插入相应位置
arr.add(i, num);
}
}
public Double GetMedian() {
int size = arr.size();
if(size % 2 == 0) {
double a = (double)(arr.get(size / 2));
double b = (double)(arr.get(size / 2 - 1));
return (a + b) / 2;
}
else {
return (double)(arr.get(size / 2));
}
}
}
BM49 表达式求值(中等)
题目
请写一个整数计算器，支持加减乘三种运算和括号。
数据范围：0≤∣s∣≤100，保证计算结果始终在整型范围内
要求：空间复杂度： O(n)，时间复杂度 O(n)
示例：
示例1：
输入："1+2"
返回值：3
示例2：
输入："(2*(3-4))*5"
返回值：-10
示例3：
输入："3+2*3*4-1"
返回值：26
解法 栈
- step 1：使用栈辅助处理优先级，默认符号为加号。
- step 2：遍历字符串，遇到数字，则将连续的数字字符部分转化为int型数字。
- step 3：遇到左括号，则将括号后的部分送入递归，处理子问题；遇到右括号代表已经到了这个子问题的结尾，结束继续遍历字符串，将子问题的加法部分相加为一个数字，返回。
- step 4：当遇到符号的时候如果是+，得到的数字正常入栈，如果是-，则将其相反数入栈，如果是*，则将栈中内容弹出与后一个元素相乘再入栈。
- step 5：最后将栈中剩余的所有元素，进行一次全部相加。
import java.util.*;
public class Solution {
public ArrayList<Integer> function(String s, int index){
Stack<Integer> stack = new Stack<Integer>();
int num = 0;
char op = '+';
int i;
for(i = index; i < s.length(); i++){
//数字转换成int数字
//判断是否为数字
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 = function(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> temp = new ArrayList<Integer>();
temp.add(sum);
temp.add(i);
return temp;
}
public int solve (String s) {
// res数组有两个元素，第一个是当前计算结果，第二个是下标
ArrayList<Integer> res = function(s, 0);
return res.get(0);
}
}