leetcode 刷题视频(2) - 栈、队列和堆

栈、队列和堆

问题1 使用队列实现栈

Implement the following operations of a stack using queues.

• push(x) – Push element x onto stack.
• pop() – Removes the element on top of the stack.
• top() – Get the top element.
• empty() – Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

• You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

链接：https://leetcode-cn.com/problems/implement-stack-using-queues/

问题2 使用栈实现队列

Implement the following operations of a queue using stacks.

• push(x) – Push element x to the back of the queue.
• pop() – Removes the element from in front of the queue.
• peek() – Get the front element.
• empty() – Return whether the queue is empty.

Notes:

• You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, the stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1);
myQueue.push(2);
myQueue.peek(); // return 1
myQueue.pop(); // return 1
myQueue.empty(); // return False

Constraints:

• 1 <= x < 10
• At most 100 calls will be made to push, pop, peek, and empty.

链接：https://leetcode-cn.com/problems/implement-queue-using-stacks/

问题3 包含min函数的栈

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) – Push element x onto stack.
• pop() – Removes the element on top of the stack.
• top() – Get the top element.
• getMin() – Retrieve the minimum element in the stack.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

• Methods pop, top and getMin operations will always be called on non-empty stacks.

链接：https://leetcode-cn.com/problems/min-stack/

问题4 合法的出栈队列

Description

There is a famous railway station in PopPush City. Country there is incredibly hilly. The station was built in last century. Unfortunately, funds were extremely limited that time. It was possible to establish only a surface track. Moreover, it turned out that the station could be only a dead-end one (see picture) and due to lack of available space it could have only one track.

The local tradition is that every train arriving from the direction A continues in the direction B with coaches reorganized in some way. Assume that the train arriving from the direction A has N <= 1000 coaches numbered in increasing order 1, 2, …, N. The chief for train reorganizations must know whether it is possible to marshal coaches continuing in the direction B so that their order will be a1, a2, …, aN. Help him and write a program that decides whether it is possible to get the required order of coaches. You can assume that single coaches can be disconnected from the train before they enter the station and that they can move themselves until they are on the track in the direction B. You can also suppose that at any time there can be located as many coaches as necessary in the station. But once a coach has entered the station it cannot return to the track in the direction A and also once it has left the station in the direction B it cannot return back to the station.

Input

The input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, …, N. The last line of the block contains just 0.

The last block consists of just one line containing 0.

Output

The output contains the lines corresponding to the lines with permutations in the input. A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition, there is one empty line after the lines corresponding to one block of the input. There is no line in the output corresponding to the last ``null’’ block of the input.

Sample Input

5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0

Sample Output

Yes
No

Yes

链接：http://poj.org/problem?id=1363

已知从1到n的数字序列，按顺序入栈，每个数字入栈后即可出栈，也可在栈中停留，等待后面的数字入栈出栈后，该数字再出栈，求该数字序列的出栈序列是否合法。

问题5 计算器

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces ``.

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23

Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

链接：https://leetcode-cn.com/problems/basic-calculator/

实现支持加减括号的计算器。

计算器算法 - 知乎

堆（优先级队列）

大顶堆

每个最大堆的子树都是最大堆。

在STL中优先级队列

#include "iostream"
#include "queue"
#include "vector"
using namespace std;

int main() {
    priority_queue<int> big_heap;
    priority_queue<int, vector<int>, greater<int> > small_heap;
    priority_queue<int, vector<int>, less<int> > big_heap2;
    int test[] = {6, 10, 1, 7, 99, 4, 33};
    for (int i = 0; i < 7; ++i) {
        big_heap.push(test[i]);
    }
    printf("big_heap.top = %d\n", big_heap.top());
    big_heap.push(10000);
    printf("big_heap.top = %d\n", big_heap.top());
    for (int i = 0; i < big_heap.size(); ++i) {
        printf("pop %d\n", big_heap.top());
        big_heap.pop();
    }
    return 0;
}

问题6 数组中第k大的数

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

最小堆里面放的是比较大的数

问题7 寻找中位数

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,

[2,3,4]`, the median is `3
[2,3]`, the median is `(2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

Follow up:

1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

链接：https://leetcode-cn.com/problems/find-median-from-data-stream/