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

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

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

第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 双队列法(优)
  • 最后


前言

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


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;
  • 可以试着跟面试官谈谈扩展问题,如:
    • 当运行栈块空间大小灵活可变时,要进行d性分割,该怎么实现;
    • 可以将数组设计成环形,最后一个栈可能从数组尾处开始,环绕到数组起始处;
    • 方法实现起来比较复杂,可以试着提供伪代码或其中部分代码;
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 stack;
    Stack minStack;

    
    public MinStack() {
        Stack stack = new Stack<>();
        Stack 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 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 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 xStack;
    Deque minStack;

    public MinStack() {
        xStack = new linkedList();
        minStack = new linkedList();
        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> list;

    public StackOfPlates(int cap) {
        List> list = new ArrayList<>();
        this.cap = cap;
        this.list = list;
    }
    
    public void push(int val) {
        if( cap == 0 ){
            return;
        }
        Stack stack;
        if( list.isEmpty() ){
            stack = new Stack();
            list.add(stack);
        } else {
            stack = list.get(list.size() - 1);
            if( stack.size() >= cap ){
                stack = new Stack();
                list.add(stack);
            }
        }
        if( stack.size() < cap ){
            stack.add(val);
        }
    }
    
    public int pop() {
        if( cap == 0 ){
            return -1;
        }
        if( list.isEmpty() ){
            return -1;
        }
        Stack 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 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> 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 
  • 执行时间:96.23%;内存消耗:60.59%;
  • 使用二维的链表存储,每次当前栈满了就新增;

4. 化栈为队 [easy]

4.1 考虑点
  • 下诉第一种解法会存在大量重复 *** 作,可以使用第二种延迟移动的方法,在有必要时才反转次序;
4.2 解法 4.2.1 双栈法
class MyQueue {
    Stack stack;
    Stack cache;

    
    public MyQueue() {
        Stack stack = new Stack<>();
        Stack cache = new Stack<>();
        
        this.stack = stack;
        this.cache = cache;
    }
    
    
    public void push(int x) {
        stack.add(x);
    }
    
    
    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;
    }
    
    
    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;
    }
    
    public boolean empty() {
        return stack.isEmpty();
    }
}
  • 执行时间:81.59%;内存消耗:53.96%;
4.2.2 延迟移动法(优)
class MyQueue {
    Deque inStack;
    Deque outStack;

    public MyQueue() {
        inStack = new linkedList();
        outStack = new linkedList();
    }
    
    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 stack;
    Stack cache;

    public SortedStack() {
        Stack stack = new Stack<>();
        Stack 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 stack = new linkedList<>();
    //辅助栈
    Deque 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 list;
    
    public AnimalShelf() {
        List 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 queueCat;
    linkedList 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分别取对应的队首;


最后
新人制作,如有错误,欢迎指出,感激不尽!
欢迎关注公众号,会分享一些更日常的东西!
如需转载,请标注出处!

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/4660620.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-11-06
下一篇 2022-11-06

发表评论

登录后才能评论

评论列表(0条)

保存