算法 | 第3章栈与队列相关《程序员面试金典》

作者: 多氯环己烷 | 来源:发表于2021-10-17 15:16 被阅读0次

前言

本系列笔记主要记录笔者刷《程序员面试金典》算法的一些想法与经验总结，按专题分类，主要由两部分构成：经验值点和经典题目。其中重点放在经典题目上；

0. *经验总结

0.1 程序员面试金典 P82

栈 - 后进先出（LIFO）：
- 栈无法在常数时间复杂度内访问第i个元素。但因为栈不需要在添加和删除时移动元素，可以在常数时间复杂度内完成此操作；
- 对于递归算法：有时需要把临时变量加入到栈中，在回溯时删除；
队列 - 先进先出（FIFO）：
- 更新队列第一个和最后一个节点容易出错，要再三确认；
- 队列常用于广度优先搜索或缓存的实现；
- 例如，在广度优先搜索中，可以使用队列来存储需要被处理的节点。每处理一个结点，就把其相邻节点加入队列尾部。这样可以按照发现顺序处理节点；
需要注意的共同点：
- 要理清下标的栈大小的区别；
- 涉及栈和队列的题目往往需要编写好几个方法，要理清楚前后逻辑；

0.2 Java常用数据结构API

详细见以下文章：
Java | 个人总结的Java常用API手册汇总

0.3 关于延迟移动

有些时候我们需要访问栈底或者队列底的数据，往往需要对数据次序进行反转操作；
我们可以每次都进行两次反转，因为要保证回到原来的样子，这样会产生大量重复操作；
另一种做法是我们先对栈或队列进行反转，需要访问栈顶或队列顶元素时才翻转回来；
第二种方法需要注意翻转的时机；
下面《4. 化栈为队》和《5. 栈排序》都用到类似的思想；

1. 三合一 [easy]

三合一

1.1 考虑点

注意看提示0<=stackNum<=2，说明三个栈在数组中排列是123123123；
可以试着跟面试官谈谈扩展问题，如：
- 当运行栈块空间大小灵活可变时，要进行弹性分割，该怎么实现；
- 可以将数组设计成环形，最后一个栈可能从数组尾处开始，环绕到数组起始处；
- 方法实现起来比较复杂，可以试着提供伪代码或其中部分代码；

1.2 解法

1.2.1 三指针法

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%；
定义三个指针，分别指向三个队列在数组的索引；

1.2.2 二维数组法（优）

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 记录每个栈「待插入」的下标；

1.2.3 一维数组法

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%；

2. 栈的最小值 [easy]

栈的最小值

2.1 考虑点

把加入一个元素看成一种状态，每种状态都有对应最小值，这样得到解法2；

2.2 解法

2.2.1 循环遍历法

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)的时间复杂度；

2.2.2 主辅栈法（优）

在这里插入图片描述

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. 堆盘子 [medium]

堆盘子

push是往最后一个栈中放数据，而不是从前遍历找到空位；

3.1 考虑点

注意讨论当传入cap=0时的情况；
可以跟面试官讨论push的两种情况：
- 第一种是：往最后一个栈中放数据（下诉解法）；
- 第二种是：从前遍历找到空位（需要推出栈n+1的栈底元素到栈n，循环往复到最后一个栈）；
- 前者优点是能很大程度上改善时间复杂度，后者适用一些要求所有栈（除最后一个）都填满的场景；

3.2 解法

3.2.1 单链表寻栈法

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%；

3.2.2 二维链表法（优）

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%；
使用二维的链表存储，每次当前栈满了就新增；

4. 化栈为队 [easy]

化栈为队

4.1 考虑点

下诉第一种解法会存在大量重复操作，可以使用第二种延迟移动的方法，在有必要时才反转次序；

4.2 解法

4.2.1 双栈法

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%；

4.2.2 延迟移动法（优）

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()操作时不需要反转次序；

5. 栈排序 [medium]

栈排序

5.1 考虑点

需要注意细节；
可以考虑延迟移动；

5.2 解法

5.2.1 单栈法

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%；
这里的单栈指每次操作后数据都存储在一个栈，另一个栈只做辅助作用，可以用其他数据结构代替；

5.2.2 根据插入值分离栈法（优）

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()操作时才考虑将储存值比较小的栈归位；

6. 动物收容所 [easy]

动物收容所

6.1 考虑点

可以问问面试官允许使用多少个链表（或其他数据结构）；
这个问题有多种解法，如果使用一个队列，对dequeueAny()操作简单，而dequeueCat()和dequeueDog()则需要遍历整个队列，降低执行效率；（对应解法一）
另一种解法是猫狗各自创建一个队列，放进包装类里，包装类有个时间戳属性，用来标记进入时间，在执行dequeueAny()操作时只需要查看两个队列的的首部，比较时间戳，返回较老那位；（对应解法二）

6.2 解法

6.2.1 单链表法

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%；

6.2.2 双队列法（优）

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分别取对应的队首；

最后

$\color{blue}{\rm\small{新人制作，如有错误，欢迎指出，感激不尽！}}$

$\color{blue}{\rm\small{欢迎关注我，并与我交流！}}$

$\color{blue}{\rm\small{如需转载，请标注出处！}}$

算法 | 第3章 栈与队列相关《程序员面试金典》

前言