8.21刷题

发表于 | 分类于 | 0 comments

第一题 225. Implement Stack using Queues

题目描述

使用队列实现栈的下列操作：

push(x) – 将元素x压入栈.
pop() – 移除栈顶元素.
top() – 获得栈顶元素.
empty() – 返回栈是否为空.

注意：

你可以假设所有的操作都是有效的（例如，不会对空栈执行pop或者top操作）
取决于你使用的语言，queue可能没有被原生支持。你可以使用list或者deque（双端队列）模拟一个队列，只要保证你仅仅使用队列的标准操作即可——亦即只有如下操作是有效的：push to back（加入队尾），pop from front（弹出队首），size（取队列大小）以及is empty（判断是否为空）

算法

使用两个队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class MyStack {
    Queue<Integer> queue;
    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<>();
    }
    /** Push element x onto stack. */
    public void push(int x) {
        queue.offer(x);
    }
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        Queue<Integer> temp = new LinkedList<>();
        int last = queue.poll();
        while (!queue.isEmpty()) {
            temp.offer(last);
            last = queue.poll();
        }
        queue = temp;
        return last;
    }
    /** Get the top element. */
    public int top() {
        Queue<Integer> temp = new LinkedList<>();
        int last = queue.poll();
        while (!queue.isEmpty()) {
            temp.offer(last);
            last = queue.poll();
        }
        temp.offer(last);
        queue = temp;
        return last;
    }
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}
利用queue每次取出后重新添加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class MyStack {
    Queue<Integer> queue;
    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.offer(x);
        for (int i = 1; i < queue.size(); i++)
            queue.offer(queue.poll());
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

第二题 232. Implement Queue using Stacks

题目描述

使用栈实现队列的下列操作：

push(x) – 将元素x加至队列尾部
pop() – 从队列头部移除元素
peek() – 获取队头元素
empty() – 返回队列是否为空
注意：

你只可以使用栈的标准操作——这意味着只有push to top（压栈）, peek/pop from top（取栈顶/弹栈顶），以及empty（判断是否为空）是允许的

取决于你的语言，stack可能没有被内建支持。你可以使用list（列表）或者deque（双端队列）来模拟，确保只使用栈的标准操作即可

你可以假设所有的操作都是有效的（例如，不会对一个空的队列执行pop或者peek操作）

算法

双栈法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class MyQueue {
    Stack<Integer> stack;
    Stack<Integer> stackreverse;
    
    /** Initialize your data structure here. */
    public MyQueue() {
        stack = new Stack<>();
        stackreverse = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        if (stack.isEmpty()) {
            while (!stackreverse.isEmpty())
                stack.push(stackreverse.pop());
        }
        stack.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (!stack.isEmpty()) {
            while(!stack.isEmpty())
                stackreverse.push(stack.pop());
        }
        return stackreverse.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if (!stack.isEmpty()) {
            while(!stack.isEmpty())
                stackreverse.push(stack.pop());
        }
        return stackreverse.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack.isEmpty() && stackreverse.isEmpty();
    }
}

第三题 170. Two Sum III - Data structure design

题目描述

设计一个Data Structure，可以快速的添加和查询structure中是否存在两个数字的加和

算法

这道题如果面试时候遇到，需要询问是添加操作更多还是查询操作更多，然后根据情况给如设计的结构。

查询操作较多
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class TwoSum {
    //if more find than add
    Set<Integer> sum;
    Set<Integer> num;
    TwoSum(){
        sum = new HashSet<Integer>();
        num = new HashSet<Integer>();
    }
    // Add the number to an internal data structure.
    public void add(int number) {
        if(num.contains(number)){
            sum.add(number * 2);
        }else{
            Iterator<Integer> iter = num.iterator();
            while(iter.hasNext()){
                sum.add(iter.next() + number);
            }
            num.add(number);
        }
    }
    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        return sum.contains(value);
    }
}

添加操作较多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class TwoSum {
    Map<Integer, Integer> map;
    /** Initialize your data structure here. */
    public TwoSum() {
        map = new HashMap<>();
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if (map.containsKey(number)) {
            map.put(number, 2);
        } else {
            map.put(number, 1);
        }
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        Iterator<Integer> itr = map.keySet().iterator();
        while (itr.hasNext()) {
            int number = itr.next();
            if (map.containsKey(value - number)) {
                if (value - number != number || map.get(value - number) == 2)
                    return true;
            }
        }
        return false;
    }
}

相关问题

1. Two Sum

关键思路：使用HashMap存储过去的value和index，这样即可在O(n)的情况下完成遍历

167. Two Sum II - Input array is sorted

关键思路：双指针，前后同时搜索结果

15. 3Sum

关键思路：先进行排序，然后利用双向指针进行大小确认，这样可以在O(n^2)的情况下找出所有的test cases

16. 3Sum Closest

关键思路：与之前的题目一样，只是对target的值稍微进行一下调整

259. 3Sum Smaller

关键思路：思路一样，sort + 双指针

18. 4Sum

关键思路：思路与之前问题相似，sort后，确定两个位置，然后使用双指针进行遍历