本文共 5704 字,大约阅读时间需要 19 分钟。
目录
使用队列实现栈的下列操作:
注意:
push to back
, peek/pop from front
, size
, 和 is empty
这些操作是合法的。思考:
栈是特性是先进后出,队列的特性是先进先出。可以用两个队列来实现栈的功能。
push和pop功能——用一个队列保持为空,另一个队列负责入栈操作。当有出栈操作时,将非空队列中的元素依次出队,存入那个空队列中,最后一个元素出队的时候返回给客户端。这样就可以一直保持一个队列是空的,返回给客户端的元素也是最后入队的那个元素。
top功能——返回非空队列的back元素即可。
class MyStack {public: /** Initialize your data structure here. */ MyStack() {} /** Push element x onto stack. */ void push(int x) { if (q1.empty()) { q2.push(x); } else { q1.push(x); } } /** Removes the element on top of the stack and returns that element. */ int pop() { if (q1.empty()) { while (q2.size() != 1) { q1.push(q2.front()); q2.pop(); } res = q2.front(); q2.pop(); } else if (q2.empty()) { while (q1.size() != 1) { q2.push(q1.front()); q1.pop(); } res = q1.front(); q1.pop(); } else { res = 0; } return res; } /** Get the top element. */ int top() { if (q1.empty()) { if (q2.empty()) { return 0; } else { return q2.back(); } } else { return q1.back(); } } /** Returns whether the stack is empty. */ bool empty() { if (q1.empty() && q2.empty()) return true; return false; }private: queue q1; queue q2; int res;};
使用栈实现队列的下列操作:
示例:
MyQueue queue = new MyQueue();queue.push(1);queue.push(2); queue.peek(); // 返回 1queue.pop(); // 返回 1queue.empty(); // 返回 false
说明:
push to top
, peek/pop from top
, size
, 和 is empty
操作是合法的。思路:
一个栈作为出队栈,一个栈作为入队栈。
push操作——向入队栈中压入元素
pop操作——若出队栈为空,则将入队栈中的元素全部存入出队栈中,然后返回出队栈的栈顶元素。
若出队栈不为空,则返回栈顶元素。
peek操作——返回出队栈的栈顶元素
class MyQueue {public: /** Initialize your data structure here. */ MyQueue() { } /** Push element x to the back of queue. */ void push(int x) { in.push(x); } /** Removes the element from in front of queue and returns that element. */ int pop() { if(out.empty()){ while(!in.empty()){ out.push(in.top()); in.pop(); } } res=out.top(); out.pop(); return res; } /** Get the front element. */ int peek() { if(out.empty()){ while(!in.empty()){ out.push(in.top()); in.pop(); } } res=out.top(); return res; } /** Returns whether the queue is empty. */ bool empty() { if((in.empty())&&(out.empty())) return true; return false; }private: stack in; stack out; int res;};
设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。
示例:
MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); --> 返回 -3.minStack.pop();minStack.top(); --> 返回 0.minStack.getMin(); --> 返回 -2.
思路:(主要是考察你的细心程度,细心,细心啊~~~~~~~~~~~~~~~)
写一个类,里面包含两个栈,一个栈用于正常的栈功能,一个栈用于存储当前栈中最小元素,名为最小栈。
push操作——正常栈入栈,如果最小值为空,则入栈,如果最小栈非空,则检查该元素的值是否小于最小栈的栈顶元素的值,如果小,则入栈,否则,入栈一个最小栈的栈顶元素(保持两个栈中的元素个数相同)
pop操作——若正常栈非空,则正常栈出栈,最小栈出栈(保持两个栈中的元素个数相同)
top操作——若正常栈的元素非空,则返回正常栈的栈顶
getmin操作——若最小栈的元素非空,返回最小栈的栈顶。
class MinStack {public: /** initialize your data structure here. */ MinStack() { } void push(int x) { normal.push(x); if(!min.empty()){ if(x
在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4输出: 4
说明:
你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。
思路:
构造一个小顶堆,保持堆的大小为k。一边遍历数组元素一边将元素的值与堆顶进行比较。如果堆的尺寸小于k,则将元素压入堆中,如果堆的尺寸等于k,则有元素大于堆顶元素的值时,将堆顶弹出,将该元素压入堆中。
class Solution {public: int findKthLargest(vector & nums, int k) { priority_queue
中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。
例如,
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构:
示例:
addNum(1)addNum(2)findMedian() -> 1.5addNum(3) findMedian() -> 2
进阶:
思路:
class MedianFinder { priority_queue
转载地址:http://vyfq.baihongyu.com/