测试开辟备战秋招口试10-牛客刷题之堆/栈/队列

努力了那么多年,回头一望,险些满是漫长的挫折和煎熬。对于大多数人的一生来说,顺风顺水只是偶尔,挫折、不堪、焦急和迷茫才是主旋律。我们登上并非我们所选择的舞台,演出并非我们所选择的剧本。继续加油吧！
目次
1、用两个栈实现队列
2、 包罗min函数的栈
3、有用括号序列
4、滑动窗口的最大值
5、最小的K个数
6、探求第K大
7、数据流中的中位数

---

1、用两个栈实现队列

题目链接：用两个栈实现队列_牛客题霸_牛客网
思绪：元素全部入栈1，然后出栈入栈2，最后从栈2全部出栈。
Java版：

1. import java.util.Stack;
3. public class Solution {
4.     Stack<Integer> stack1 = new Stack<Integer>();
5.     Stack<Integer> stack2 = new Stack<Integer>();
6.    
7.     public void push(int node) {
8.        stack1.push(node) ;
9.     }
10.    
11.     public int pop() {
12.         if(stack2.isEmpty()){
13.             while(!stack1.isEmpty()){
14.                 stack2.add(stack1.pop()) ;
15.             }
16.         }
17.         return stack2.pop() ;
18.       
19.     }
20. }

复制代码

2、 包罗min函数的栈

题目链接：包罗min函数的栈_牛客题霸_牛客网
思绪：利用两个栈，一个栈用于维护入栈和出栈，取栈顶元素，另一个栈用于维护单调栈，也是取栈顶元素。
Java版:

1. import java.util.Stack;
3. public class Solution {
5.     Stack<Integer> s1 = new Stack<>() ;
6.     Stack<Integer> s2 = new Stack<>() ;
8.     public void push(int node) {
9.         s1.push(node) ;
10.         if(s2.isEmpty() || s2.peek() > node){
11.             s2.push(node) ;
12.         }else{
13.             s2.push(s2.peek()) ;
14.         }
15.     }
16.    
17.     public void pop() {
18.         s1.pop() ;
19.         s2.pop() ;
20.     }
21.    
22.     public int top() {
23.        return  s1.peek() ;
24.     }
25.    
26.     public int min() {
27.         return s2.peek() ;
28.     }
29. }

复制代码

3、有用括号序列

题目链接：有用括号序列_牛客题霸_牛客网
思绪：每次如果碰到左括号，就让右括号入栈，每次碰到右括号，出栈匹配。
Java版：
 

1. import java.util.*;
4. public class Solution {
5.     /**
6.      *
7.      * @param s string字符串
8.      * @return bool布尔型
9.      */
10.     public boolean isValid (String s) {
11.         // write code here
12.         Stack<Character> s1 = new Stack<>() ;
13.         for(int i=0; i<s.length(); i++){
14.             if(s.charAt(i) == '{'){
15.                 s1.add('}') ;
16.             }else if(s.charAt(i) == '('){
17.                 s1.add(')') ;
18.             }else if(s.charAt(i) == '['){
19.                 s1.add(']') ;
20.             }else if(s1.isEmpty() || s1.pop() != s.charAt(i)){
21.                 return false ;
22.             }
23.         }
24.         return s1.isEmpty() ;
25.     }
26. }

复制代码

4、滑动窗口的最大值

题目链接：滑动窗口的最大值_牛客题霸_牛客网
思绪：袒露罗列全部滑动窗口，依次比对全部窗口中值的巨细即可。
暴力版：

1. import java.util.*;
2. public class Solution {
3.     public ArrayList<Integer> maxInWindows(int [] num, int size) {
4.         ArrayList<Integer> arrayList = new ArrayList<>() ;
5.         if(num.length == 0 || size > num.length || size == 0){
6.             return arrayList ;
7.         }
8.         for(int i=0; i<num.length-size+1; i++){
9.             int max = num[i] ;
10.             for(int j=i+1; j<i+size; j++){
11.                 max = Math.max(max, num[j]) ;
12.             }
13.             arrayList.add(max) ;
14.         }
15.         return arrayList ;
17.     }
18. }

复制代码

思绪2：维护一个双端的单调队列，让每次背面入队的都比前面大，每一个新窗口，必要队列头部元素出队。

1. import java.util.*;
2. public class Solution {
3.     public ArrayList<Integer> maxInWindows(int [] num, int size) {
4.         //利用双端队列，每次尾部进入保证比之前的小，每次下一个窗口时，移除头部元素
5.         ArrayList<Integer> arrayList = new ArrayList<Integer>() ;
6.         ArrayDeque<Integer> arrayDeque = new ArrayDeque<Integer>() ;
7.         if(size==0 || num.length == 0 || size > num.length){
8.             return arrayList ;
9.         }
10.         for(int i=0; i<size; i++){
11.             while(!arrayDeque.isEmpty() && num[arrayDeque.getLast()] < num[i]){
12.                 arrayDeque.pollLast() ;
13.             }
14.             arrayDeque.addLast(i) ;
15.         }
17.         for(int i=size; i<num.length; i++){
18.             arrayList.add(num[arrayDeque.peekFirst()]) ;
19.             while(!arrayDeque.isEmpty() && num[arrayDeque.getLast()] < num[i]){
20.                 arrayDeque.pollLast() ;
21.             }
22.             while(!arrayDeque.isEmpty() &&  (i-size+1) > arrayDeque.peekFirst()){
23.                 arrayDeque.pollFirst() ;
24.             }
25.             arrayDeque.addLast(i) ;
26.         }
27.         arrayList.add(num[arrayDeque.peekFirst()]) ;
28.         return arrayList ;
30.     }
31. }

复制代码

5、最小的K个数

题目链接：最小的K个数_牛客题霸_牛客网
思绪：直接排序法。
Java版：

1. import java.util.*;
3. public class Solution {
4.     public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
5.         //直接排序法
6.         ArrayList<Integer> arr = new ArrayList<>() ;
7.         Arrays.sort(input) ;
8.         for(int i=0; i<k; i++){
9.             arr.add(input[i]) ;
10.         }
11.         return arr ;
12.     }
13. }

复制代码

思绪2：建立容量为k的大根堆，每次对比堆顶元素，如果当前元素小于堆顶元素，则更换。

1. import java.util.*;
3. public class Solution {
4.     public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
5.         //堆排序法，建立容量为k的优先队列构成的大根堆
6.       
7.         ArrayList<Integer> list = new ArrayList<>() ;
8.          if(input.length == 0 || k == 0){
9.             return list ;
10.          }
11.         PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->o2-o1) ;
12.         for(int i=0; i<input.length; i++){
13.             if(queue.size() < k){
14.                 queue.add(input[i]) ;
15.             }else{
16.                 if(input[i] < queue.peek()){
17.                     queue.poll() ;
18.                     queue.add(input[i]) ;
19.                 }
20.             }
21.         }
22.         while(!queue.isEmpty()){
23.             list.add(queue.peek()) ;
24.             queue.poll() ;
25.         }
26.         return list ;
27.     }
28. }

复制代码

6、探求第K大

题目链接：探求第K大_牛客题霸_牛客网
思绪：直接排序，然后返回倒数第K个就行了。
Java版：

1. import java.util.*;
3. public class Solution {
4.     public int findKth(int[] a, int n, int K) {
5.         // write code here
6.         Arrays.sort(a) ;
7.         return a[n - K] ;
8.     }
9. }

复制代码

7、数据流中的中位数

题目链接：数据流中的中位数_牛客题霸_牛客网
思绪：先排序，然后取中位数即可。
Java版：

2. import java.util.* ;
4. public class Solution {
5.     ArrayList<Integer> arrayList = new ArrayList<>() ;
6.     public void Insert(Integer num) {
7.         arrayList.add(num) ;
8.         Collections.sort(arrayList) ;
9.     }
11.     public Double GetMedian() {
12.         int n = arrayList.size() ;
13.         double result = (n%2==1)  ? (double)arrayList.get(n/2) : (double)(arrayList.get(n/2) + arrayList.get(n/2-1)) / 2 ;  
14.         return result ;
15.     }
16. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。