LCR 125. 图书整理 II

戚戚复戚戚，我心汝不知。

题目

LeetCode每日一题，参考LCR 125. 图书整理 II。

解题思路

• 队列：队列可直接实现，但是其实题目要求使用两个书车，需要使用两个栈来实现。
• 两个栈：使用两个栈，一个A负责存书，一个B负责取书：存好办，直接往A里面压入存放就行；怎么取呢？一开始B为空，要取的时候把A全部弹出压入B，从B中弹出最上面的就行，如果B不为空，直接从里面取就行，这样保证取的都是最早存的书。

队列

class CQueue {
    ArrayDeque<Integer> q = new ArrayDeque<>();
    public CQueue() {}
    public void appendTail(int value) {
        q.offer(value);
    }
    public int deleteHead() {
        if(q.isEmpty()) return -1;
        else return q.pop();
    }
}

复杂度分析

• 时间复杂度：O(1)。
• 空间复杂度：O(n)。

两个栈模拟队列操作

两个栈可模拟队列，这个特性还是挺有意思的。

class CQueue {
    //针对栈的操作只能使用push和pop
    ArrayDeque<Integer> q1 = new ArrayDeque<>(), q2 = new ArrayDeque<>();
    public CQueue() {}
    //A用来存 B用来取
    public void appendTail(int value) {// O(1)
        q1.push(value);
    }
    public int deleteHead() { // 均摊 O(1)。对于每个元素，至多入栈和出栈各两次。
        if(q1.isEmpty()) return -1;
        while(q1.size() > 0) {
            q2.push(q1.pop());
        }
        int r = q2.pop();
        while(q2.size() > 0) {
            q1.push(q2.pop());
        }
        return r;
    }
}
/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

复杂度分析

• 时间复杂度：O(1)，均摊 O(1)。对于每个元素，至多入栈和出栈各两次。
• 空间复杂度：O(n)，n为图书馆书的总数。

2023/10/13