Google 美国面经:用栈实现队列

zzzrf 11天前 6

G 家不看重解出最优解,更看重代码优化的思路,有时候不解出答案,但面试官看到了你优秀的代码逻辑,也能直接拿到 strong hire 。

关于面试,G 家一般是 4 轮算法+1 轮 BQ,偶尔会考到系统设计,算法比较少考原题,考原题也不是做出来就能过……

今年 HC 很少!今年 HC 很少!不要报太大期望,且败且战,不要太气馁。

写到最后时间不多,其实面试官没啥 follow up 问我,最后问了一下复杂度和有没有什么优化方法。

题目:

正如标题所述,你需要使用两个栈来实现队列的一些操作。

队列应支持 push(element),pop() 和 top(),其中 pop 是弹出队列中的第一个(最前面的)元素。 pop 和 top 方法都应该返回第一个元素的值。

在线做题地址

例 1:

输入:
    push(1)
    pop()    
    push(2)
    push(3)
    top()    
    pop()     
输出:
    1
    2
    2

例 2:

输入:
    push(1)
    push(2)
    push(2)
    push(3)
    push(4)
    push(5)
    push(6)
    push(7)
    push(1)
输出:
[]

解题思路

先考虑只有一个栈的时候,由于栈的先入后出特性 FILO,栈中的元素的顺序是反的,我们无法直接访问栈底的元素。但是当把 1 号栈中所有元素依次弹出并压入到 2 号栈中,2 号栈顶的元素就变成了原来 1 号栈的栈底,即正序。所以我们要提取元素时,只需从 2 号栈提取即可。

但是由于 2 号栈中栈顶元素是最先加入队列的元素,所以只有当 2 号栈为空时,才能将 1 号栈中所有元素加入到 2 号栈中。

举例说明:

首先我们有一个主要栈 stack1:[1,2,3) ,以下所有栈的表示方式中,圆括号 ')' 均为栈顶。 那么 stack1 的出栈顺序为 3-2-1,其中 1 为我们要找到的元素,也就是队首。

我们需要借助一个辅助栈 stack2:[),将 stack1 中的元素依次放到 stack2 中:stack2 [3,2,1)。这时我们发现 stack2 的栈顶就是我们要找的元素,弹出即可。

此时我们再向主要栈 stack1 中压入 4 和 5 。两个栈状态:stack1 [4,5) 、stack2 [3,2)。 现在我们需要队首的话,应该先弹出辅助栈 stack2 的栈顶。

如果此时辅助栈空,我们就要执行之前转移的操作,将 stack1 的所有元素压入 stack2,然后弹出 stack2 的栈顶即可。

代码思路

定义 move(),操作是将元素从 1 号栈转移到 2 号栈。当要提取元素,且 2 号栈为空时,调用 move()。

复杂度分析

时间复杂度

  • 每个元素最多会别 push,pop,move 一次,每个操作的均摊时间复杂度为 O(1)。

空间复杂度

  • 假设一共操作了 N 次 push,空间复杂度为 O(N)。
public class MyQueue {
    public MyQueue() {
        // do intialization if necessary
    }
    /*
     * @param element: An integer
     * @return: nothing
     */
    public void push(int element) {
        stack1.push(element);
    }
    /*
     * @return: An integer
     */
    public int pop() {
        if (stack2.isEmpty()) {
            move();
        }
        return stack2.pop();
    }
    /*
     * @return: An integer
     */
    public int top() {
        if (stack2.isEmpty()) {
            move();
        }
        return stack2.peek();
    }
    
    // 将 1 号栈中的元素移动到 2 号栈中
    private void move() {
        while (! stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    }
    
    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();
}
最新回复 (0)
  • 游客
    2
返回