演算法-堆疊佇列堆
簡介：演算法篇-堆疊佇列堆
不敢高聲語，恐驚天上人，
一、用兩個堆疊實作佇列
1、題目描述
用兩個堆疊來實作一個佇列，完成佇列的 Push 和 Pop 操作，
2、解題思路
in 堆疊用來處理入堆疊（push）操作，out 堆疊用來處理出堆疊（pop）操作，一個元素進入 in 堆疊之后，出堆疊的順序被反轉，當元素要出堆疊時，需要先進入 out 堆疊，此時元素出堆疊順序再一次被反轉，因此出堆疊順序就和最開始入堆疊順序是相同的，先進入的元素先退出，這就是佇列的順序，
3、代碼示例
1 import java.util.Stack;
2
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.empty()){
13 while(!stack1.empty()){
14 stack2.push(stack1.pop());
15 }
16 }
17 return stack2.pop();
18 }
19 }
View Code
二、包含main函式的堆疊
1、題目描述
實作一個包含 min() 函式的堆疊，該方法回傳當前堆疊中最小的值，
2、解題思路
使用一個額外的 minStack，堆疊頂元素為當前堆疊中最小的值，在對堆疊進行 push 入堆疊和 pop 出堆疊操作時，同樣需要對 minStack 進行入堆疊出堆疊操作，從而使 minStack 堆疊頂元素一直為當前堆疊中最小的值，在進行 push 操作時，需要比較入堆疊元素和當前堆疊中最小值，將值較小的元素 push 到 minStack 中，
3、代碼示例
1 import java.util.Stack;
2
3 public class Solution {
4 // 創建兩個堆疊：一個用于存放所有元素，一個用于存放每添加一個新元素之后的最小元素
5 Stack<Integer> total = new Stack<>();
6 Stack<Integer> mininum = new Stack<>();
7
8 // 若堆疊為空，則同時往兩個堆疊壓入元素，反之像mininum壓入元素-此時需要比較當前元素與堆疊頂元素的大小
9 public void push(int node) {
10 total.push(node);
11 if(mininum.isEmpty()){
12 mininum.push(node);
13 }else{
14 if(node < mininum.peek()){
15 mininum.push(node);
16 }else{
17 mininum.push(mininum.peek());
18 }
19 }
20 }
21
22 // 兩個堆疊的元素同時出堆疊
23 public void pop() {
24 total.pop();
25 mininum.pop();
26 }
27
28 // 回傳total 的堆疊頂元素
29 public int top() {
30 return total.peek();
31 }
32
33 // 回傳mininum 的堆疊頂元素
34 public int min() {
35 return mininum.peek();
36 }
37 }
View Code
三、堆疊的壓入彈出序列
1、題目描述
輸入兩個整數序列，第一個序串列示堆疊的壓入順序，請判斷第二個序列是否為該堆疊的彈出順序，假設壓入堆疊的所有數字均不相等，
例如序列 1,2,3,4,5 是某堆疊的壓入順序，序列 4,5,3,2,1 是該壓堆疊序列對應的一個彈出序列，但 4,3,5,1,2 就不可能是該壓堆疊序列的彈出序列，
2、解題思路
使用一個堆疊來模擬壓入彈出操作，每次入堆疊一個元素后，都要判斷一下堆疊頂元素是不是當前出堆疊序列 popSequence 的第一個元素，如果是的話則執行出堆疊操作并將 popSequence 往后移一位，繼續進行判斷，
3、代碼示例
1 import java.util.ArrayList;
2 import java.util.*;
3
4 public class Solution {
5 public boolean IsPopOrder(int [] pushA,int [] popA) {
6 Stack<Integer> stack = new Stack<Integer>();
7 int i = 0;
8 for(int temp : pushA){
9 stack.push(temp);
10 // peek() 回傳堆疊頂元素
11 while((!stack.isEmpty()) && stack.peek() == popA[i]){
12 stack.pop(); // 移除堆疊頂元素
13 i++;
14 }
15 }
16 return stack.isEmpty();
17 }
18 }
View Code
四、包含min函式的堆疊
1、題目描述
給定一個陣列，找出其中最小的K個數，例如陣列元素是4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4，如果K>陣列的長度，那么回傳一個空的陣列
2、解題思路
- 復雜度：O(NlogK) + O(K)
- 特別適合處理海量資料
維護一個大小為 K 的最小堆程序如下：使用大頂堆，在添加一個元素之后，如果大頂堆的大小大于 K，那么將大頂堆的堆頂元素去除，也就是將當前堆中值最大的元素去除，從而使得留在堆中的元素都比被去除的元素來得小，
應該使用大頂堆來維護最小堆，而不能直接創建一個小頂堆并設定一個大小，企圖讓小頂堆中的元素都是最小元素，
Java 的 PriorityQueue 實作了堆的能力，PriorityQueue 默認是小頂堆，可以在在初始化時使用 Lambda 運算式 (o1, o2) -> o2 - o1 來實作大頂堆，其它語言也有類似的堆資料結構，
3、代碼示例
1 import java.util.*;
2
3 public class Solution {
4
5 public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
6 ArrayList<Integer> list = new ArrayList<Integer>();
7 int length = input.length;
8 if(k > length || k < 0){
9 return list;
10 }
11
12 for(int i = 0; i < length - 1; i++){
13 for(int j = 0; j < length - i - 1; j++){
14 if(input[j] > input[j+1]){
15 int temp = input[j]; // 簡單排序
16 input[j] = input[j+1];
17 input[j+1] = temp;
18 }
19 }
20 }
21
22 for(int i = 0; i < k; i++){
23 list.add(input[i]); // 取最小的前K個數
24 }
25
26 return list;
27 }
28 }
View Code
五、資料流在的中位數
1、題目描述
如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值，如果從資料流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值，
2、代碼示例
1 import java.util.*;
2
3 public class Solution {
4
5 ArrayList<Integer> array = new ArrayList<>();
6
7 public void Insert(Integer num) {
8 array.add(num);
9 }
10
11 public Double GetMedian() {
12 Collections.sort(array); // 排序
13 int index = array.size() / 2;
14 if(array.size() % 2 != 0){ // 奇數直接取值
15 return (double)array.get(index);
16 }
17 // 偶數取平均值
18 return ((double)(array.get(index - 1)) + (double)array.get(index)) / 2;
19 }
20
21
22 }
View Code
六、字符流中第一個不重復的字符
1、題目描述
請實作一個函式用來找出字符流中第一個只出現一次的字符，例如，當從字符流中只讀出前兩個字符 "go" 時，第一個只出現一次的字符是 "g"，當從該字符流中讀出前六個字符“google" 時，第一個只出現一次的字符是 "l"，
2、解題思路
使用統計陣列來統計每個字符出現的次數，本題涉及到的字符為都為 ASCII 碼，因此使用一個大小為 128 的整型陣列就能完成次數統計任務，
使用佇列來存盤到達的字符，并在每次有新的字符從字符流到達時移除佇列頭部那些出現次數不再是一次的元素，因為佇列是先進先出順序，因此佇列頭部的元素為第一次只出現一次的字符，
3、代碼示例
1 public class Solution {
2 //Insert one char from stringstream
3 String stream = "";
4 int [] cache = new int[256];
5 public void Insert(char ch) {
6 stream += ch;
7 cache[ch]++;
8 }
9 //return the first appearence once char in current stringstream
10 public char FirstAppearingOnce() {
11 for(int i = 0; i < stream.length(); i++){
12 if(cache[stream.charAt(i)] == 1){
13 return stream.charAt(i);
14 }
15 }
16 return '#';
17 }
18 }
View Code
七、滑動視窗的最大值
1、題目描述
給定一個陣列和滑動視窗的大小，找出所有滑動視窗里數值的最大值，
例如，如果輸入陣列 {2, 3, 4, 2, 6, 2, 5, 1} 及滑動視窗的大小 3，那么一共存在 6 個滑動視窗，他們的最大值分別為 {4, 4, 6, 6, 6, 5}，
2、解題思路
維護一個大小為視窗大小的大頂堆，頂堆元素則為當前視窗的最大值，
假設視窗的大小為 M，陣列的長度為 N，在視窗向右移動時，需要先在堆中洗掉離開視窗的元素，并將新到達的元素添加到堆中，這兩個操作的時間復雜度都為 log2M，因此演算法的時間復雜度為 O(Nlog2M)，空間復雜度為 O(M)，
3、代碼示例
1 import java.util.*;
2
3 public class Solution {
4 public ArrayList<Integer> maxInWindows(int [] num, int size) {
5 ArrayList<Integer> result = new ArrayList<>();
6 if(num.length < size || 0 == size){
7 return result;
8 }
9 // deque容器為一個給定型別的元素進行線性處理，像向量一樣，它能夠快速地隨機訪問任一個元素，并且能夠高效地插入和洗掉容器的尾部元素
10 Deque<Integer> quque = new LinkedList<>();
11 // 初始化雙端佇列元素
12 for(int i = 0; i < size - 1; i++){
13 while(!quque.isEmpty() && num[quque.peekLast()] < num[i]){
14 quque.pollLast();
15 }
16 quque.add(i);
17 }
18
19 for(int i = size - 1; i < num.length; i++){
20 // 檢查佇列內容是否合法，判斷佇列頭部元素是否位于視窗內
21 while(!quque.isEmpty() && i - quque.peekFirst() + 1 > size){
22 quque.pollFirst();
23 }
24 // 從佇列尾部移除所有比當前值小的元素
25 while(!quque.isEmpty() && num[quque.peekLast()] < num[i]){
26 quque.pollLast();
27 }
28 quque.offerLast(i);
29 result.add(num[quque.peekFirst()]);
30 }
31 return result;
32 }
33 }
View Code
不敢高聲語
恐驚天上人
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/288735.html
標籤：Java