JZ31 堆疊的壓入、彈出序列
描述
輸入兩個整數序列，第一個序串列示堆疊的壓入順序，請判斷第二個序列是否可能為該堆疊的彈出順序，假設壓入堆疊的所有數字均不相等，例如序列1,2,3,4,5是某堆疊的壓入順序，序列4,5,3,2,1是該壓堆疊序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓堆疊序列的彈出序列，
1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有數字均不相同
方法1 輔助堆疊（推薦使用）
思路：
題目要我們判斷兩個序列是否符合入堆疊出堆疊的次序，我們就可以用一個堆疊來模擬，對于入堆疊序列，只要堆疊為空，序列肯定要依次入堆疊，那什么時候出來呢？自然是遇到一個元素等于當前的出堆疊序列的元素，那我們就放棄入堆疊，讓它先出來，
//入堆疊：堆疊為慷訓者堆疊頂不等于出堆疊陣列
while (j < n && (q.isEmpty() || q.peek() != popA[i])) {
q.push(pushA[j]);
j++;
}
如果能按照這個次序將兩個序列都訪問完，那說明是可以匹配入堆疊出堆疊次序的，
具體做法：
step 1：準備一個輔助堆疊，兩個下標分別訪問兩個序列，
step 2：輔助堆疊為慷訓者堆疊頂不等于出堆疊陣列當前元素，就持續將入堆疊陣列加入堆疊中，
step 3：堆疊頂等于出堆疊陣列當前元素就出堆疊，
step 4：當入堆疊陣列訪問完，出堆疊陣列無法依次彈出，就是不匹配的，否則兩個序列都訪問完就是匹配的，
代碼
public boolean IsPopOrder(int[] pushA, int[] popA) {
Stack<Integer> q = new Stack<>();
int n = pushA.length;
//記錄進堆疊位置
int j = 0;
for (int i = 0; i < n; i++) {
while (j < n && (q.isEmpty() || q.peek() != popA[i])) {
q.push(pushA[j]);
j++;
}
if (q.peek() == popA[i]) q.pop();
else return false;
}
return true;
}
方法2 原地堆疊（擴展思路）
思路：
方法一我們使用了一個輔助堆疊來模擬，但是陣列本來就很類似堆疊啊，用下標表示堆疊頂，在方法一種push陣列前半部分入堆疊了，就沒用了，這部分空間我們就可以用來當成堆疊，原理還是同方法一一樣，只是這時我們遍歷push陣列的時候，用下標n表示堆疊空間，n的位置就是堆疊頂元素，
具體做法：
step 1：用下標n表示堆疊空間，用j表示出堆疊序列的下標，
step 2：遍歷每一個待入堆疊的元素，加入堆疊頂，即push陣列中n的位置，同時增加堆疊空間的大小，即n的大小，
step 3：當堆疊不為空即堆疊頂n大于等于0，且堆疊頂等于當前出堆疊序列，就出堆疊，同時縮小堆疊的空間，即減小n，
step 4：最后若是堆疊空間大小n為0，代表全部出堆疊完成，否則不匹配，
代碼
package mid.JZ31堆疊的壓入彈出序列;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int[] pushA, int[] popA) {
//初始化堆疊
int n = 0;
//出堆疊元素位置
int j = 0;
for (int i = 0; i < popA.length; i++) {
//當前push元素入堆疊
pushA[n] = pushA[i];
//出堆疊
while (n >= 0 && pushA[n] == popA[j]){
n--;
j++;
}
n++;
}
return n == 0;
}
/*public boolean IsPopOrder(int[] pushA, int[] popA) {
Stack<Integer> q = new Stack<>();
int n = pushA.length;
//記錄進堆疊位置
int j = 0;
for (int i = 0; i < n; i++) {
while (j < n && (q.isEmpty() || q.peek() != popA[i])) {
q.push(pushA[j]);
j++;
}
if (q.peek() == popA[i]) q.pop();
else return false;
}
return true;
}*/
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/539142.html
標籤：其他
下一篇：Spring回圈依賴