牛客经典101题题解集--堆/栈/队列
目录
栈
用两个栈实现队列
题目
分析
代码
java
python
包含min函数的栈
题目
分析
代码
java
python
有效括号序列
题目
分析
代码
java
python
表达式求值
题目
分析
代码
java
python
队列
滑动窗口的最大值
题目
分析
代码
java
python
数据流中的中位数
题目
分析
代码
java
python
堆
最小的k个数
题目
分析
代码
java
python
寻找第k大
题目
分析
代码
java
python
栈
用两个栈实现队列
题目
用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。
数据范围： 𝑛≤1000n≤1000
要求：存储n个元素的空间复杂度为 𝑂(𝑛)O(n) ，插入与删除的时间复杂度都是 𝑂(1)O(1)
示例1
输入：["PSH1","PSH2","POP","POP"]
返回值：1,2
说明："PSH1":代表将1插入队列尾部 "PSH2":代表将2插入队列尾部 "POP“:代表删除一个元素，先进先出=>返回1 "POP“:代表删除一个元素，先进先出=>返回2
示例2
输入：["PSH2","POP","PSH1","POP"]
返回值：2,1
分析
栈是先进后出，队列是先进先出，所以我们这里想到用两个栈来模拟队列。
一个用来输入数据，一个用来输出数据。
代码
java
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()){ return stack2.pop(); } while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } return stack2.pop(); } }python
# -*- coding:utf-8 -*- class Solution: def __init__(self): self.stack1 = [] self.stack2 = [] def push(self, node): # write code here self.stack1.append(node) def pop(self): # return xx if self.stack2: return self.stack2.pop() while self.stack1: self.stack2.append(self.stack1.pop()) return self.stack2.pop()包含min函数的栈
题目
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。
此栈包含的方法有：
push(value):将value压入栈中
pop():弹出栈顶元素
top():获取栈顶元素
min():获取栈中最小元素
数据范围：操作数量满足 0≤𝑛≤300 0≤n≤300 ，输入的元素满足 ∣𝑣𝑎𝑙∣≤10000 ∣val∣≤10000
进阶：栈的各个操作的时间复杂度是 𝑂(1) 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
示例1
输入： ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
返回值：-1,2,1,-1
分析
这个难的地方在于找到最小值。那么可以使用两个栈。在放入第一个元素的时候都放进去，然后继续在第一个栈中放入元素，如果当前元素小于第二个的栈顶元素，那么就压入
进栈的时候必须是stack2.peek()>=node，如果没有等于的话，对于：2 2，第二个2不会再压入，而弹出最小值以后栈变成空了，实际上弹出一次以后他的最小值还是2
代码
java
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.peek()>=node){ stack2.push(node); } } public void pop() { if(stack1.isEmpty()){ return ; } int a=stack1.pop(); if(stack2.peek()==a){ stack2.pop(); } } public int top() { return stack1.peek(); } public int min() { return stack2.peek(); } }python
# -*- coding:utf-8 -*- class Solution: stack1=[] stack2=[] def push(self, node): # write code here self.stack1.append(node) if not self.stack2 or self.stack2[-1]>=node: self.stack2.append(node) def pop(self): # write code here if not self.stack1: return a=self.stack1.pop() if self.stack2[-1]==a: self.stack2.pop() def top(self): # write code here return self.stack1[-1] return def min(self): # write code here return self.stack2[-1]有效括号序列
题目
给出一个仅包含字符仅由括号字符 ‘[’‘[’、‘]’‘]’、‘(’‘(’、‘)’‘)’、‘{’‘{’、‘}’‘}’ 的括号序列字符串 𝑠s（0≦∣𝑠∣≦1040≦∣s∣≦104），你需要判断给出的括号序列字符串 𝑠s 是否是有效的括号序列。
有效括号序列的定义如下：
∙ ∙空序列是有效括号序列；
∙ ∙如果 𝐴A 是有效括号序列，则 (A)、[A] 和 A都是有效括号序列；
∙ ∙如果 𝐴A 和 𝐵B 都是有效括号序列，则它们的拼接 𝐴𝐵AB 也是有效括号序列。
如果括号序列字符串 𝑠 是有效的括号序列，返回一个布尔值 true；否则返回一个布尔值 false。
示例1
输入："["
返回值：false
示例2
输入："[]"
返回值：true
备注：要求：空间复杂度 𝑂(𝑛)，时间复杂度 𝑂(𝑛)。
分析
用栈来实现，如果是左括号，那么压右括号入栈中，如果左括号不等于右括号，那么return fasle，如果循环结束栈中元素不为0，也return false
代码
java
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return bool布尔型 */ public boolean isValid (String s) { // write code here 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.isEmpty() || stack.peek()!=s.charAt(i)){ return false; }else{ stack.pop(); } } return stack.isEmpty(); } }python
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param s string字符串 # @return bool布尔型 # class Solution: def isValid(self , s: str) -> bool: # write code here stack=[] for i in range(len(s)): if s[i]=='(': stack.append(')') elif s[i]=='[': stack.append(']') elif s[i]=='{': stack.append('}') elif not stack or stack[-1]!=s[i]: return False else: stack.pop() return False if stack else True表达式求值
题目
请写一个整数计算器，支持加减乘三种运算和括号。
数据范围：0≤∣𝑠∣≤100，保证计算结果始终在整型范围内
要求：空间复杂度： 𝑂(𝑛)，时间复杂度 𝑂(𝑛)
示例1
输入："1+2"
返回值：3
示例2
输入："(2*(3-4))*5"
返回值：-10
复制
示例3
输入："3+2*3*4-1"
返回值：26
分析
定义两栈，一个存数字，一个存符号
代码
java
import java.util.*; public class Solution { public int solve (String s) { int n = s.length(); return dfs(s.toCharArray(), 0, n - 1); } public int dfs(char[] s, int L, int R) { Deque<Integer> nums = new ArrayDeque<>(); Deque<Integer> ops = new ArrayDeque<>(); int[] prior = new int[128]; prior['+'] = prior['-'] = 1; prior['*'] = prior['/'] = 2; nums.push(0); // 处理负数开头 for (int i = L; i <= R; i++) { int c = s[i]; if (c >= '0' && c <= '9') { // 数字 int x = c - '0'; while (i + 1 <= R && s[i+1] >= '0' && s[i+1] <= '9') { x = x * 10 + s[++i] - '0'; } nums.push(x); } else if (c == '+' || c == '-' || c == '*' || c == '/') { // 运算符 calc(nums, ops, prior, c); } else if (c == '(') { // 括号，递归 int j = i + 1, level = 1; while (level > 0) { if (s[j] == '(') level++; else if (s[j] == ')') level--; j++; } nums.push(dfs(s, i + 1, j - 2)); i = j - 1; } } calc(nums, ops, prior, '+'); // 把剩下的全部算完 return nums.pop(); } public void calc(Deque<Integer> nums, Deque<Integer> ops, int[] prior, int c) { while (!ops.isEmpty() && nums.size() > 1 && prior[ops.peek()] >= prior[c]) { int op = ops.pop(); int y = nums.pop(); int x = nums.pop(); if (op == '+') x += y; else if (op == '-') x -= y; else if (op == '*') x *= y; else if (op == '/') x /= y; nums.push(x); } ops.push(c); } }python
class Solution: def solve(self , s: str) -> int: return self.dfs(s, 0, len(s) - 1) def dfs(self, s, L, R): nums = [] ops = [] prior = {'+':1, '-':1, '*':2, '/':2} nums.append(0) # 处理负数开头 i = L while i <= R: if s[i].isdigit(): x = 0 while i <= R and s[i].isdigit(): x = x * 10 + int(s[i]) i += 1 nums.append(x) continue c = s[i] if c in "+-*/": self.calc(nums, ops, prior, c) i += 1 elif c == '(': j = i + 1 level = 1 while level > 0: if s[j] == '(': level += 1 elif s[j] == ')': level -= 1 j += 1 val = self.dfs(s, i+1, j-2) nums.append(val) i = j - 1 else: i += 1 self.calc(nums, ops, prior, '+') return nums.pop() def calc(self, nums, ops, prior, c): while ops and prior[ops[-1]] >= prior[c]: op = ops.pop() y = nums.pop() x = nums.pop() if op == '+': x += y elif op == '-': x -= y elif op == '*': x *= y elif op == '/': x = int(x / y) nums.append(x) ops.append(c)队列
滑动窗口的最大值
题目
给定一个长度为 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≤𝑛≤10000，0≤𝑠𝑖𝑧𝑒≤10000，数组中每个元素的值满足 ∣𝑣𝑎𝑙∣≤10000
要求：空间复杂度 𝑂(𝑛)，时间复杂度 𝑂(𝑛)
示例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
返回值：[]
分析
Deque是两端都能进和出的操作
peekFirst()看最左边第一个元素（队头）只拿出来看一眼，不删除
②peekLast()看最右边最后一个元素（队尾）只看不删
2. 删除（看完就删掉） remove /poll 系列
③removeFirst()删掉最左边第一个元素
④removeLast()删掉最右边最后一个元素
3. add 系列
⑤addLast(x)从队尾右边加元素
⑥addFirst(x)从队头左边加元素
代码
java
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param num int整型一维数组 * @param size int整型 * @return int整型ArrayList */ public ArrayList<Integer> maxInWindows (int[] num, int size) { // write code here ArrayList<Integer> res=new ArrayList<>(); // write code here if(num.length==0 ||size==0){ return res; } Deque <Integer> que=new LinkedList<>(); for(int j=0,i=1-size;j<num.length;i++,j++){ if(i>0 && que.peekFirst()==num[i-1]){ que.removeFirst(); } while(!que.isEmpty() && que.peekLast()<=num[j]){ que.removeLast(); } que.addLast(num[j]); if(i>=0){ res.add(que.peekFirst()); } } return res; } }python
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param num int整型一维数组 # @param size int整型 # @return int整型一维数组 # import collections class Solution: def maxInWindows(self , num: List[int], size: int) -> List[int]: result=[] if len(num)==0 or size==0: return result # write code here que=collections.deque() for j in range(len(num)): i=j-size+1 if i>0 and que[0]==num[i-1]: que.popleft() while que and que[-1]<=num[j]: que.pop() que.append(num[j]) if i>=0: result.append(que[0]) return result数据流中的中位数
题目
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
数据范围：数据流中数个数满足 1≤𝑛≤1000 ，大小满足 1≤𝑣𝑎𝑙≤1000
进阶： 空间复杂度 𝑂(𝑛) ， 时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑛)
示例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 "
分析
设置两个队列：
a是从小到大，b是从大到小，a是较大的后半部分，b是较小的前半部分
代码
java
import java.util.*; public class Solution { Queue<Integer> a=new PriorityQueue<>();//由小到大 Queue<Integer> b=new PriorityQueue<>((a,b) ->b-a);//由大到小 public void Insert(Integer num) { if(a.size()!=b.size()){ a.add(num); b.add(a.poll()); }else{ b.add(num); a.add(b.poll()); } } public Double GetMedian() { if(a.size()==b.size()){ return (a.peek()+b.peek())/2.0; }else{ return a.peek()*1.0; } } }python
# -*- coding:utf-8 -*- from heapq import * class Solution: def __init__(self): self.A=[] self.B=[] def Insert(self, num): # write code here if len(self.A) != len(self.B): heappush(self.A, num) heappush(self.B, -heappop(self.A)) else: heappush(self.B, -num) heappush(self.A, -heappop(self.B)) def GetMedian(self): # write code here return self.A[0] if len(self.A) != len(self.B) else (self.A[0] - self.B[0]) / 2.0python只有较小堆没有较大堆，所以取负号，然后在最后结果的时候再取回来
堆
最小的k个数
题目
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：0≤𝑘,𝑛≤10000，数组中每个数的大小0≤𝑣𝑎𝑙≤1000
要求：空间复杂度 𝑂(𝑛)，时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑘)
示例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]
分析
利用小顶堆，最小的在尖尖上
小顶堆 ：从小到大 (a, b) -> a - b 大顶堆： 从大到小 (a, b) -> b - a
代码
java
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param input int整型一维数组 * @param k int整型 * @return int整型ArrayList */ public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) { // write code here ArrayList<Integer> res=new ArrayList<>(); PriorityQueue<Integer> p=new PriorityQueue<>((a,b) ->a-b); for(int i:input){ p.add(i); } for(int i=0;i<k;i++){ res.add(p.poll()); } return res; } }python
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param input int整型一维数组 # @param k int整型 # @return int整型一维数组 # import heapq class Solution: def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]: # write code here # 结果列表 res = [] # Python 小顶堆（默认就是小顶堆，和Java (a,b)->a-b 等价） heapq.heapify(input) # 直接把数组转成堆，效率更高 # 取出前k个最小的数 for _ in range(k): res.append(heapq.heappop(input)) return respython默认的堆就是小顶堆
寻找第k大
题目
有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
要求：时间复杂度 𝑂(𝑛𝑙𝑜𝑔𝑛)，空间复杂度 𝑂(1)
数据范围：0≤𝑛≤1000， 1≤𝐾≤𝑛，数组中每个元素满足 0≤𝑣𝑎𝑙≤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
分析
首先要了解什么是快速排序：
快速排序在每一轮挑选一个基准函数，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。
代码
java
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param a int整型一维数组 * @param n int整型 * @param K int整型 * @return int整型 */ Random r=new Random(); public int findKth (int[] a, int n, int K) { // write code here int target = a.length - K;//找到第k大的下标 int start = 0, end = a.length - 1; int pivot = privot(a, start, end); while (pivot != target) { if (pivot > target) { end = pivot - 1; } else { start = pivot + 1; } pivot = privot(a, start, end); } return a[pivot]; } public int privot(int [] a,int start,int end){ int pri=r.nextInt(start-end+1)+start; swap(a,pri,end); int index=start-1; for(int i=start;i<=end;i++){ if(a[i]<a[end]){ swap(a,i,++index); } } swap(a,++index,end); return index; } public void swap(int[] a,int i,int j){ int temp=a[i]; a[i]=a[j]; a[j]=temp; } }python
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param a int整型一维数组 # @param n int整型 # @param K int整型 # @return int整型 # import random class Solution: def findKth(self , a: List[int], n: int, K: int) -> int: # write code here target=len(a)-K start = 0 end = len(a) - 1 # 核心：循环找，直到下标 == target while True: p = self.privot(a, start, end) # 基准下标 if p == target: return a[p] elif p > target: end = p - 1 # 去左边找 else: start = p + 1 # 去右边找 def privot(self,a:List[int],start:int,end:int)-> int: r=random.randint(start,end) a[r],a[end]=a[end],a[r] index=start-1 for i in range(start,end+1): if a[i]<a[end]: index+=1 a[index],a[i]=a[i],a[index] index+=1 a[index],a[end]=a[end],a[index] return index