天天看點
傳回

算法 | 第3章 棧與隊列相關《程式員面試金典》

目錄

  • 前言
  • 0. *經驗總結
    • 0.1 程式員面試金典 P82
    • 0.2 Java常用資料結構API
    • 0.3 關于延遲移動
  • 1. 三合一 [easy]
    • 1.1 考慮點
    • 1.2 解法
      • 1.2.1 三指針法
      • 1.2.2 二維數組法（優）
      • 1.2.3 一維數組法
  • 2. 棧的最小值 [easy]
    • 2.1 考慮點
    • 2.2 解法
      • 2.2.1 循環周遊法
      • 2.2.2 主輔棧法（優）
  • 3. 堆盤子 [medium]
    • 3.1 考慮點
    • 3.2 解法
      • 3.2.1 單連結清單尋棧法
      • 3.2.2 二維連結清單法（優）
  • 4. 化棧為隊 [easy]
    • 4.1 考慮點
    • 4.2 解法
      • 4.2.1 雙棧法
      • 4.2.2 延遲移動法（優）
  • 5. 棧排序 [medium]
    • 5.1 考慮點
    • 5.2 解法
      • 5.2.1 單棧法
      • 5.2.2 根據插入值分離棧法（優）
  • 6. 動物收容所 [easy]
    • 6.1 考慮點
    • 6.2 解法
      • 6.2.1 單連結清單法
      • 6.2.2 雙隊列法（優）
  • 最後

本系列筆記主要記錄筆者刷《程式員面試金典》算法的一些想法與經驗總結，按專題分類，主要由兩部分構成：經驗值點和經典題目。其中重點放在經典題目上；

  • 棧 - 後進先出（LIFO）：
    • 棧無法在常數時間複雜度内通路第i個元素。但因為棧不需要在添加和删除時移動元素，可以在常數時間複雜度内完成此操作；
    • 對于遞歸算法：有時需要把臨時變量加入到棧中，在回溯時删除；
  • 隊列 - 先進先出（FIFO）：
    • 更新隊列第一個和最後一個節點容易出錯，要再三确認；
    • 隊列常用于廣度優先搜尋或緩存的實作；
    • 例如，在廣度優先搜尋中，可以使用隊列來存儲需要被處理的節點。每處理一個結點，就把其相鄰節點加入隊列尾部。這樣可以按照發現順序處理節點；
  • 需要注意的共同點：
    • 要理清下标的棧大小的差別；
    • 涉及棧和隊列的題目往往需要編寫好幾個方法，要理清楚前後邏輯；

詳細見以下文章：

Java | 個人總結的Java常用API手冊彙總

  • 有些時候我們需要通路棧底或者隊列底的資料，往往需要對資料次序進行反轉操作；
  • 我們可以每次都進行兩次反轉，因為要保證回到原來的樣子，這樣會産生大量重複操作；
  • 另一種做法是我們先對棧或隊列進行反轉，需要通路棧頂或隊列頂元素時才翻轉回來；
  • 第二種方法需要注意翻轉的時機；
  • 下面《4. 化棧為隊》和《5. 棧排序》都用到類似的思想；

算法 | 第3章 棧與隊列相關《程式員面試金典》

  • 注意看提示

    0<=stackNum<=2

     ，說明三個棧在數組中排列是123123123；
  • 可以試着跟面試官談談擴充問題，如：
    • 當運作棧塊空間大小靈活可變時，要進行彈性分割，該怎麼實作；
    • 可以将數組設計成環形，最後一個棧可能從數組尾處開始，環繞到數組起始處；
    • 方法實作起來比較複雜，可以試着提供僞代碼或其中部分代碼； 

class TripleInOne {
	int[] stack;
    int stackSize;
    int t0;
    int t1;
    int t2;

    public TripleInOne(int stackSize) {
        stack = new int[stackSize*3];
		int t0 = -3;
        int t1 = -2;
        int t2 = -1;

        this.stackSize = stackSize;
        this.t0 = t0;
        this.t1 = t1;
        this.t2 = t2;
    }
    
    public void push(int stackNum, int value) {
		if( stackNum == 0 ){
			this.t0 = pushVal( t0, value );
        } else if( stackNum == 1 ){
            this.t1 = pushVal( t1, value);
        } else if( stackNum == 2){
            this.t2 = pushVal( t2, value);
        }
    }
    public int pushVal( int top, int value ){
        if( top + 3 < stackSize*3 ){
			top += 3;
            stack[top] = value;
        }
        return top;
    }
    
    public int pop(int stackNum) {
        int val = peek(stackNum);
        if( val != -1 ){
            if( stackNum == 0 ){
				stack[t0] = -1;
                t0 -= 3;
            } else if( stackNum == 1 ){
                stack[t1] = -1;
                t1 -= 3;
            } else if( stackNum == 2){
                stack[t2] = -1;
                t2 -= 3;
            }
            return val;
        }
        return -1;

    }
    
    public int peek(int stackNum) {
		if( stackNum == 0 && t0 >= 0 ){
            return stack[t0];
        } else if( stackNum == 1 && t1 >= 1){
            return stack[t1];
        } else if( stackNum == 2 && t2 >= 2){
            return stack[t2];
        }
        return -1;
    }
    
    public boolean isEmpty(int stackNum) {
		int value = peek(stackNum);
        if( value == -1){
            return true;
        }
        return false;
    }
}
  • 執行時間：34.80%；記憶體消耗：44.07%；
  • 定義三個指針，分别指向三個隊列在數組的索引； 

class TripleInOne {
    int N = 3;
    // 3 * n 的數組，每一行代表一個棧
    int[][] data; 
    // 記錄每個棧「待插入」位置
    int[] locations; 

    public TripleInOne(int stackSize) {
        data = new int[N][stackSize];
        locations = new int[N];
    }
    
    public void push(int stackNum, int value) {
        int[] stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc < stk.length) {
            stk[loc] = value;
            locations[stackNum]++;
        }
    }
    
    public int pop(int stackNum) {
        int[] stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc > 0) {
            int val = stk[loc - 1];
            locations[stackNum]--;
            return val;
        } else {
            return -1;
        }
    }
    
    public int peek(int stackNum) {
        int[] stk = data[stackNum];
        int loc = locations[stackNum];
        if (loc > 0) {
            return stk[loc - 1];
        } else {
            return -1;
        }
    }
    
    public boolean isEmpty(int stackNum) {
        return locations[stackNum] == 0;
    }
}
  • 執行時間：97.06%；記憶體消耗：69.49%；
  • 時間複雜度：所有的操作均為 O(1)。
  • 空間複雜度：O(k*n)。k 為我們需要實作的棧的個數，n 為棧的容量；
  • 建立一個二維數組 datadata ；二維數組的每一行代表一個棧，同時使用一個locationslocations 記錄每個棧「待插入」的下标； 

class TripleInOne {
    int N = 3;
    int[] data;
    int[] locations;
    int size;
    public TripleInOne(int stackSize) {
        size = stackSize;
        data = new int[size * N];
        locations = new int[N];
        for (int i = 0; i < N; i++) {
            locations[i] = i * size;
        }
    }
    
    public void push(int stackNum, int value) {
        int idx = locations[stackNum];
        if (idx < (stackNum + 1) * size) {
            data[idx] = value;
            locations[stackNum]++;
        }
    }
    
    public int pop(int stackNum) {
        int idx = locations[stackNum];
        if (idx > stackNum * size) {
            locations[stackNum]--;
            return data[idx - 1];
        } else {
            return -1;
        }
    }
    
    public int peek(int stackNum) {
        int idx = locations[stackNum];
        if (idx > stackNum * size) {
            return data[idx - 1];
        } else {
            return -1;
        }
    }
    
    public boolean isEmpty(int stackNum) {
        return locations[stackNum] == stackNum * size;
    }
}
  • 執行時間：97.06%；記憶體消耗：44.07%；

算法 | 第3章 棧與隊列相關《程式員面試金典》

  • 把加入一個元素看成一種狀态，每種狀态都有對應最小值，這樣得到解法2； 

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> minStack;

    /** initialize your data structure here. */
    public MinStack() {
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> minStack = new Stack<>();
        this.stack = stack;
        this.minStack = minStack;
    }

    public void push(int x) {
        stack.add(x);
        if( minStack.isEmpty() ){
            minStack.add(x);
            return;
        }
        Stack<Integer> cache = new Stack<>();
        boolean isMatter = false;
        while( !isMatter ){
            if( !minStack.isEmpty() && minStack.peek() < x ){
                cache.add( minStack.pop() );
            } else {
                minStack.add(x);
                isMatter = true;
            }
        }
        while( !cache.isEmpty() ){
            minStack.add(cache.pop());
        }
    }

    public void pop() {
        if( stack.isEmpty() ){
            return;
        }
        int topNum = stack.pop();
        Stack<Integer> cache = new Stack<>();
        boolean isMatter = false;
        while( !isMatter ){
            if( minStack.peek() == topNum ){
                minStack.pop();
                isMatter = true;
            } else {
                cache.add(minStack.pop());
            }
        }
        while( !cache.isEmpty() ){
            minStack.add(cache.pop());
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}
  • 執行時間：5.02%；記憶體消耗：5.18%；
  • 不推薦用此方法，不滿足O(1)的時間複雜度；

算法 | 第3章 棧與隊列相關《程式員面試金典》
class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;

    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int x) {
        xStack.push(x);
        minStack.push(Math.min(minStack.peek(), x));
    }
    
    public void pop() {
        xStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return xStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}
  • 執行時間：91.63%；記憶體消耗：58.64%；

  • 建立兩個棧，一個棧是主棧 stackstack，另一個是輔助棧 minStackminStack，用于存放對應主棧不同時期的最小值；

    、

算法 | 第3章 棧與隊列相關《程式員面試金典》
  • push是往最後一個棧中放資料，而不是從前周遊找到空位；

  • 注意讨論當傳入cap=0時的情況；
  • 可以跟面試官讨論push的兩種情況：
    • 第一種是：往最後一個棧中放資料（下訴解法）；
    • 第二種是：從前周遊找到空位（需要推出棧n+1的棧底元素到棧n，循環往複到最後一個棧）；
    • 前者優點是能很大程度上改善時間複雜度，後者适用一些要求所有棧（除最後一個）都填滿的場景； 

class StackOfPlates {
    int cap;
    List<Stack<Integer>> list;

    public StackOfPlates(int cap) {
        List<Stack<Integer>> list = new ArrayList<>();
        this.cap = cap;
        this.list = list;
    }
    
    public void push(int val) {
        if( cap == 0 ){
            return;
        }
        Stack<Integer> stack;
        if( list.isEmpty() ){
            stack = new Stack<Integer>();
            list.add(stack);
        } else {
            stack = list.get(list.size() - 1);
            if( stack.size() >= cap ){
                stack = new Stack<Integer>();
                list.add(stack);
            }
        }
        if( stack.size() < cap ){
            stack.add(val);
        }
    }
    
    public int pop() {
        if( cap == 0 ){
            return -1;
        }
        if( list.isEmpty() ){
            return -1;
        }
        Stack<Integer> stack = list.get(list.size() - 1);
        int result = stack.pop();
        if(stack.isEmpty()){
            list.remove( list.size() - 1 );
        }
        return result;
    }
    
    public int popAt(int index) {
        if( cap == 0 ){
            return -1;
        }
        if( index > list.size()-1 || index < 0 || list.isEmpty() ){
            return -1;
        }
        Stack<Integer> stack = list.get(index);
        int result = stack.pop();
        if(stack.isEmpty()){
            list.remove( index );
        }
        return result;
    }
}
  • 執行時間：60.44%；記憶體消耗：43.48%； 

class StackOfPlates {
    private LinkedList<LinkedList<Integer>> setOfStacks;
    private int cap;

    public StackOfPlates(int cap) {
        this.setOfStacks = new LinkedList<>();
        this.cap = cap;
    }

    private boolean setIsEmpty() {
        return setOfStacks.isEmpty();
    }

    private boolean lastStackIsFUll() {
        if (setIsEmpty()) {
            return true;
        }
        return setOfStacks.getLast().size()>=cap;
    }

    private boolean lastStackIsEmpty() {
        return setOfStacks.getLast().isEmpty();
    }

    public void push(int val) {
        if (cap <= 0) {
            return;
        }
        if (setIsEmpty() || lastStackIsFUll()) {
            setOfStacks.addLast(new LinkedList<>());
        }
        setOfStacks.getLast().addLast(val);
    }

    public int pop() {
        int val = -1;
        if (setIsEmpty()) {
            return val;
        }
        val = setOfStacks.getLast().removeLast();
        if (lastStackIsEmpty()) {
            setOfStacks.removeLast();
        }
        return val;
    }

    public int popAt(int index) {
        int val = -1;
        if (setIsEmpty() ||setOfStacks.size()-1<index ) {
            return val;
        }
        val = setOfStacks.get(index).removeLast();
        if (setOfStacks.get(index).isEmpty()) {
            setOfStacks.remove(index);
        }
        return val;
    }
}
  • 執行時間：96.23%；記憶體消耗：60.59%；
  • 使用二維的連結清單存儲，每次目前棧滿了就新增；

算法 | 第3章 棧與隊列相關《程式員面試金典》

  • 下訴第一種解法會存在大量重複操作，可以使用第二種延遲移動的方法，在有必要時才反轉次序； 

class MyQueue {
    Stack<Integer> stack;
    Stack<Integer> cache;

    /** Initialize your data structure here. */
    public MyQueue() {
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> cache = new Stack<>();
        
        this.stack = stack;
        this.cache = cache;
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stack.add(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(stack.isEmpty()){
            return -1;
        }
        while( !stack.isEmpty() ){
            cache.add(stack.pop());
        }
        int result = cache.pop();
        while( !cache.isEmpty() ){
            stack.add(cache.pop());
        }
        return result;
    }
    
    /** Get the front element. */
    public int peek() {
        if(stack.isEmpty()){
            return -1;
        }
        while( !stack.isEmpty() ){
            cache.add(stack.pop());
        }
        int result = cache.peek();
        while( !cache.isEmpty() ){
            stack.add(cache.pop());
        }
        return result;
    }
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack.isEmpty();
    }
}
  • 執行時間：81.59%；記憶體消耗：53.96%； 

class MyQueue {
    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue() {
        inStack = new LinkedList<Integer>();
        outStack = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) {
            in2out();
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void in2out() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}
  • 執行時間：100.00%；記憶體消耗：35.19%；
  • 隻有進行pop()和peek()操作，并且輸出棧為空時才需要翻轉次序；
  • 當有必要反轉次序時才移動元素，使用者進行連續pop()操作時不需要反轉次序；

算法 | 第3章 棧與隊列相關《程式員面試金典》

  • 需要注意細節；
  • 可以考慮延遲移動； 

class SortedStack {
    Stack<Integer> stack;
    Stack<Integer> cache;

    public SortedStack() {
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> cache = new Stack<>();
        this.stack = stack;
        this.cache = cache;
    }
    
    public void push(int val) {
        if( stack.isEmpty() ){
            stack.add(val);
            return;
        }
        if( stack.peek() > val ){
            stack.add(val);
        } else {
            cache.add(stack.pop());
            stack.add(val);
            stack.add(cache.pop());
        }
    }
    
    public void pop() {
        if( stack.isEmpty() ){
            return;
        }
        stack.pop();
        int val;
        if( !stack.isEmpty() ){
            val = stack.peek(); //忘記peek
        } else {
            return;
        }
        while(!stack.isEmpty()){
            if( stack.peek() >= val ){
                cache.add(stack.pop());
            } else {
                val = stack.peek();
            }
        }
        boolean isEliminate = false;
        while( !cache.isEmpty() ){
            if( cache.peek() == val && !isEliminate ){
                cache.pop();
                isEliminate = true; //忘記上鎖
            } else {
                stack.add( cache.pop() );
            }
        }
        stack.add(val);
    }
    
    public int peek() {
        if(stack.isEmpty()){
            return -1;
        }
        return stack.peek(); 
    }
    
    public boolean isEmpty() {
        return stack.isEmpty();
    }
}
  • 執行時間：5.04%；記憶體消耗：70.80%；
  • 這裡的單棧指每次操作後資料都存儲在一個棧，另一個棧隻做輔助作用，可以用其他資料結構代替； 

class SortedStack {
    //原始棧
    Deque<Integer> stack = new LinkedList<>();
    //輔助棧
    Deque<Integer> tmp = new LinkedList<>();
    public SortedStack() {
    }
    
    public void push(int val) {
        int max = stack.isEmpty() ? Integer.MAX_VALUE : stack.peek();
        int min = tmp.isEmpty() ? Integer.MIN_VALUE : tmp.peek();
        //比較原始棧與輔助棧棧頂值，使其滿足 輔助棧 <= val <= 原始棧
        while(true){
            if(val > max){
                tmp.push(stack.pop());
                max = stack.isEmpty() ? Integer.MAX_VALUE : stack.peek();
            } else if(val < min){
                stack.push(tmp.pop());
                min = tmp.isEmpty() ? Integer.MIN_VALUE : tmp.peek();
            } else{
                stack.push(val);
                break;
            }
        }
    }
    
    public void pop() {
        //将輔助棧元素push回原始棧
        while (!tmp.isEmpty()){
            stack.push(tmp.pop());
        }
        if (!stack.isEmpty())
            stack.pop();
    }
    
    public int peek() {
        //将輔助棧元素push回原始棧
        while (!tmp.isEmpty()){
            stack.push(tmp.pop());
        }
        return stack.isEmpty() ? -1 : stack.peek();
    }
    
    public boolean isEmpty() {
        return stack.isEmpty() && tmp.isEmpty();
    }
}
  • 執行時間：99.65%；記憶體消耗：81.59%；
  • push()操作後資料可以分布在兩個棧中，隻有pop()或peek()操作時才考慮将儲存值比較小的棧歸位；

算法 | 第3章 棧與隊列相關《程式員面試金典》

  • 可以問問面試官允許使用多少個連結清單（或其他資料結構）；
  • 這個問題有多種解法，如果使用一個隊列，對

    dequeueAny()

     操作簡單，而

    dequeueCat()

     和

    dequeueDog()

     則需要周遊整個隊列，降低執行效率；（對應解法一）
  • 另一種解法是貓狗各自建立一個隊列，放進包裝類裡，包裝類有個時間戳屬性，用來标記進入時間，在執行

    dequeueAny()

     操作時隻需要檢視兩個隊列的的首部，比較時間戳，傳回較老那位；（對應解法二） 

class AnimalShelf {
    List<String> list;
    
    public AnimalShelf() {
        List<String> list = new ArrayList<>();
        this.list = list;
    }
    
    public void enqueue(int[] animal) {
        if( animal[0] < 0 || animal[1] < 0 || animal[1] > 2){
            return;
        }
        String animalStr = String.valueOf(animal[0]) + String.valueOf(animal[1]);
        list.add(animalStr);
    }
    
    public int[] dequeueAny() {
        if( list.isEmpty() ){
            return new int[]{-1, -1};
        }
        String result = list.get(0);
        list.remove(0);
        int num = Integer.parseInt(result);
        return new int[]{num/10, num%10};
    }
    
    public int[] dequeueDog() {
        if( list.isEmpty() ){
            return new int[]{-1, -1};
        }
        for( int i = 0; i < list.size(); i++){
            int num = Integer.parseInt( list.get(i) );
            if( num%10 == 1 ){
                list.remove(i);
                return new int[]{num/10, num%10};
            }
        }
        return new int[]{-1, -1};
    }
    
    public int[] dequeueCat() {
        if( list.isEmpty() ){
            return new int[]{-1, -1};
        }
        for( int i = 0; i < list.size(); i++){
            int num = Integer.parseInt( list.get(i) );
            if( num%10 == 0 ){
                list.remove(i);
                return new int[]{num/10, num%10};
            }
        }
        return new int[]{-1, -1};
    }
}
  • 執行時間：17.07%；記憶體消耗：97.72%； 

class AnimalShelf {
    LinkedList<int[]> queueCat;
    LinkedList<int[]> queueDog;

    public AnimalShelf() {
        queueCat = new LinkedList<>();
        queueDog = new LinkedList<>();
    }

    public void enqueue(int[] animal) {
        // 判斷種類後入隊
        if (animal[1] == 0) {
            queueCat.addLast(animal);
        } else if (animal[1] == 1) {
            queueDog.addLast(animal);
        }
    }

    public int[] dequeueAny() {
        // 取出cat的隊首，判空則直接傳回
        int[] headCat;
        if (!queueCat.isEmpty()) {
            headCat = queueCat.getFirst();
        } else if (!queueDog.isEmpty()) {
            return queueDog.removeFirst();
        } else {
            return new int[]{-1,-1};
        }
        // 取出dog的隊首，判空則直接傳回
        int[] headDog;
        if (!queueDog.isEmpty()) {
            headDog = queueDog.getFirst();
        } else {
            return queueCat.removeFirst();
        }
        // 比較後傳回
        if (headCat[0]<=headDog[0]) {
            return queueCat.removeFirst();
        } else {
            return queueDog.removeFirst();
        }
    }

    public int[] dequeueDog() {
        if (!queueDog.isEmpty()) {
            return queueDog.removeFirst();
        } else {
            return new int[]{-1,-1};
        }
    }

    public int[] dequeueCat() {
        if (!queueCat.isEmpty()) {
            return queueCat.removeFirst();
        } else {
            return new int[]{-1,-1};
        }
    }
}
  • 執行時間：98.86；記憶體消耗：29.43%；
  • 建立兩個隊列，分别存儲貓和狗。dequeCat和dequeDog分别取對應的隊首；

新人制作，如有錯誤，歡迎指出，感激不盡！

歡迎關注公衆号，會分享一些更日常的東西！

如需轉載，請标注出處！

算法 | 第3章 棧與隊列相關《程式員面試金典》
上一篇: 算法 | 第4章 樹與圖相關《程式員面試金典》
下一篇: 外媒稱阿裡财報完全超出預期，新零售戰略正在“孵化未來”