leetcode刷面试题(面试题03合集)

面试题 03.01. 三合一

三合一。描述如何只用一个数组来实现三个栈。
你应该实现push(stackNum, value)、pop(stackNum)、isEmpty(stackNum)、peek(stackNum)方法。stackNum表示栈下标，value表示压入的值。
构造函数会传入一个stackSize参数，代表每个栈的大小。

示例1:
输入：
[“TripleInOne”, “push”, “push”, “pop”, “pop”, “pop”, “isEmpty”]
[[1], [0, 1], [0, 2], [0], [0], [0], [0]]
输出：
[null, null, null, 1, -1, -1, true]
说明：当栈为空时pop, peek返回-1，当栈满时push不压入元素。

示例2:
输入：
[“TripleInOne”, “push”, “push”, “push”, “pop”, “pop”, “pop”, “peek”]
[[2], [0, 1], [0, 2], [0, 3], [0], [0], [0], [0]]
输出：
[null, null, null, null, 2, 1, -1, -1]

class TripleInOne {

    int[] arr;
    int[] top;
    int stackSize;

    public TripleInOne(int stackSize) {
        this.stackSize = stackSize;
        top = new int[3];
        arr = new int[stackSize * 3];
    }

    public void push(int stackNum, int value) {
        if (top[stackNum] >= stackSize) {
            return;
        }
        arr[top[stackNum] * 3 + stackNum] = value;
        top[stackNum]++;
    }

    public int pop(int stackNum) {
        if (top[stackNum] == 0) {
            return -1;
        }
        top[stackNum]--;
        return arr[top[stackNum] * 3 + stackNum];
    }

    public int peek(int stackNum) {
        if (top[stackNum] == 0) {
            return -1;
        }
        return arr[(top[stackNum]-1) * 3 + stackNum];
    }

    public boolean isEmpty(int stackNum) {
        return top[stackNum] == 0;
    }
}

面试题 03.02. 栈的最小值
请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。

示例：

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

class MinStack {

    Stack<Integer> list;
    Stack<Integer> min;
    int miin;

    public MinStack() {
        list = new Stack<>();
        min = new Stack<>();
        miin = Integer.MAX_VALUE;
    }

    public void push(int x) {
        list.push(x);
        miin = Math.min(miin, x);
        min.push(miin);
    }

    public void pop() {
        list.pop();
        min.pop();
        if (min.isEmpty()) {
            miin = Integer.MAX_VALUE;
            return;
        }
        miin = min.peek();
    }

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

    public int getMin() {
        return miin;
    }
}

面试题 03.03. 堆盘子

堆盘子。设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。 进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。
当某个栈为空时，应当删除该栈。当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1.

示例1:
输入：
[“StackOfPlates”, “push”, “push”, “popAt”, “pop”, “pop”]
[[1], [1], [2], [1], [], []]
输出：
[null, null, null, 2, 1, -1]

示例2:
输入：
[“StackOfPlates”, “push”, “push”, “push”, “popAt”, “popAt”, “popAt”]
[[2], [1], [2], [3], [0], [0], [0]]
输出：
[null, null, null, null, 2, 1, 3]

class StackOfPlates {

    List<Stack<Integer>> ans = new ArrayList<>();
    int cap = 0;
    int size = 0;

    public StackOfPlates(int cap) {
        this.cap = cap;
    }

    public void push(int val) {
        if (cap == 0) {
            return;
        }
        if (size == 0) {
            Stack stack = new Stack();
            stack.push(val);
            ans.add(stack);
            size = 1;
            return;
        }
        Stack stack = ans.get(size - 1);
        if (stack.size() == cap) {
            stack = new Stack();
            size++;
            ans.add(stack);
        }
        stack.add(val);
    }

    public int pop() {
        if (size == 0) {
            return -1;
        }
        Stack<Integer> stack = ans.get(size - 1);
        int val = stack.pop();
        if (stack.isEmpty()) {
            ans.remove(size - 1);
            size--;
        }
        return val;
    }

    public int popAt(int index) {
        if (size <= index) {
            return -1;
        }
        Stack<Integer> stack = ans.get(index);
        int val = stack.pop();
        if (stack.isEmpty()) {
            ans.remove(index);
            size--;
        }
        return val;
    }
}

面试题 03.04. 化栈为队

实现一个MyQueue类，该类用两个栈来实现一个队列。

示例：
MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false

说明：
你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

以下是一个傻逼的错误示范，对，就是我自己

class MyQueue {

    Stack<Integer> stackIn = new Stack<>();
    Stack<Integer> stackOut = new Stack<>();
    boolean stateIn = true;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {

    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        if (!stateIn) {
            stateIn = true;
            deChange(stackOut, stackIn);
        }
        stackIn.push(x);
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        if (stateIn) {
            stateIn = false;
            deChange(stackIn, stackOut);
        }
        return stackOut.pop();
    }

    /**
     * Get the front element.
     */
    public int peek() {
        if (stateIn) {
            stateIn = false;
            deChange(stackIn, stackOut);
        }
        return stackOut.peek();
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        if (stateIn) {
            return stackIn.isEmpty();
        } else {
            return stackOut.isEmpty();
        }
    }

    private void deChange(Stack<Integer> stackIn, Stack<Integer> stackOut) {
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }
}

下面操作，反转次数会少很多

class MyQueue {

    Stack<Integer> stackIn = new Stack<>();
    Stack<Integer> stackOut = new Stack<>();

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {

    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        stackIn.push(x);
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        peek();
        return stackOut.pop();
    }

    /**
     * Get the front element.
     */
    public int peek() {
        if (stackOut.isEmpty()) {
            deChange(stackIn, stackOut);
        }
        return stackOut.peek();
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
    private void deChange(Stack<Integer> stackIn, Stack<Integer> stackOut) {
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }
}

面试题 03.05. 栈排序

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。

示例1:
输入：
[“SortedStack”, “push”, “push”, “peek”, “pop”, “peek”]
[[], [1], [2], [], [], []]
输出：
[null,null,null,1,null,2]

示例2:
输入：
[“SortedStack”, “pop”, “pop”, “push”, “pop”, “isEmpty”]
[[], [], [], [1], [], []]
输出：
[null,null,null,null,null,true]

说明:
栈中的元素数目在[0, 5000]范围内。

class SortedStack {

    Stack<Integer> left;
    Stack<Integer> right;

    public SortedStack() {
        left = new Stack<>();
        right = new Stack<>();
    }

    public void push(int val) {
        if (right.isEmpty() || right.peek() > val) {
            while (!left.isEmpty() && left.peek() > val) {
                right.push(left.pop());
            }
        } else if (left.isEmpty() || left.peek() < val) {
            while (!right.isEmpty() && right.peek() < val) {
                left.push(right.pop());
            }
        }
        right.push(val);
    }

    public void pop() {
        if (peek() != -1) {
            right.pop();
        }
    }

    public int peek() {
        doChange(left, right);
        if (right.isEmpty()) {
            return -1;
        }
        return right.peek();
    }

    public boolean isEmpty() {
        return left.isEmpty() && right.isEmpty();
    }

    private void doChange(Stack<Integer> stackIn, Stack<Integer> stackOut) {
        while (!stackIn.isEmpty()) {
            stackOut.push(stackIn.pop());
        }
    }
}

面试题 03.06. 动物收容所

动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能*挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat。允许使用Java内置的LinkedList数据结构。
enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。
dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。

示例1:
输入：
[“AnimalShelf”, “enqueue”, “enqueue”, “dequeueCat”, “dequeueDog”, “dequeueAny”]
[[], [[0, 0]], [[1, 0]], [], [], []]
输出：
[null,null,null,[0,0],[-1,-1],[1,0]]

示例2:
输入：
[“AnimalShelf”, “enqueue”, “enqueue”, “enqueue”, “dequeueDog”, “dequeueCat”, “dequeueAny”]
[[], [[0, 0]], [[1, 0]], [[2, 1]], [], [], []]
输出：
[null,null,null,null,[2,1],[0,0],[1,0]]

说明:
收纳所的最大容量为20000

class AnimalShelf {

    LinkedList<int[]> dogList = new LinkedList<>();
    LinkedList<int[]> catList = new LinkedList<>();
    int step = 0;

    public AnimalShelf() {

    }

    public void enqueue(int[] animal) {
        if (animal[1] == 0) {
            catList.push(new int[]{animal[0], step++});
        } else {
            dogList.push(new int[]{animal[0], step++});
        }
    }

    public int[] dequeueAny() {
        if (catList.isEmpty() && dogList.isEmpty()) {
            return new int[]{-1, -1};
        }
        if (catList.isEmpty()) {
            return new int[]{dogList.removeLast()[0], 1};
        }
        if (dogList.isEmpty()) {
            return new int[]{catList.removeLast()[0], 0};
        }
        if (dogList.getLast()[1] < catList.getLast()[1]) {
            return new int[]{dogList.removeLast()[0], 1};
        } else {
            return new int[]{catList.removeLast()[0], 0};
        }
    }

    public int[] dequeueDog() {
        if (dogList.isEmpty()) {
            return new int[]{-1, -1};
        }
        return new int[]{dogList.removeLast()[0], 1};
    }

    public int[] dequeueCat() {
        if (catList.isEmpty()) {
            return new int[]{-1, -1};
        }
        return new int[]{catList.removeLast()[0], 0};
    }
}