队列/堆"/>
LeetCode算法学习笔记——栈/队列/堆
栈是先进后出的线性表,包括以下操作:
队列是先进先出的线性表,包括以下操作:
二插堆是最大最小值先出的完全二叉树
std::priority queue<int> big_heap;//默认构造是最大堆
std::priority queue<int, std::vector<int>, std::greater<int>> small_heap;//最小堆构造方法
std::priority queue<int, std::vector<int>, std::less<int>> big_heap;//最大堆构造方法
题目:
1. 使用队列实现栈
设计一个栈,支持如下操作,算法复杂度为O(1),栈的内部存储数据的结构为队列,队列的方法只能包括push、front、pop、size、empty
分析:
要用队列实现栈,那么就要在类中维护一个逆序的队列,将对栈顶pop,top,empty的操作改为对队列首元素的操作。
问题:如何改变数据的存储顺序,使新增元素进来后实现整体逆序
假设队列中原有数据逆序存储,新来一个数据时可以使用一个临时队列temp做转储。
class MyStack {
public:MyStack() {}void push(int x) {std::queue<int> temp_queue;//使用temp_queue做临时转储,改变队列中数据的存储顺序temp_queue.push(x);while (!_data.empty()){temp_queue.push(_data.front());_data.pop();}while (!temp_queue.empty()){_data.push(temp_queue.front());temp_queue.pop();}}int pop() {int x = _data.front();_data.pop();return x;}int top() {return _data.front();}bool empty() {return _data.empty();}
private:std::queue<int> _data;
};
2. 使用栈实现队列
设计一个队列,队列的内部存储数据的结构为栈。
分析:和前面一样,通过改变数据的存储顺序实现该功能。
class MyQueue {
public:MyQueue() {}void push(int x) {std::stack<int> temp_stack;//通过临时栈转储while (!_mstack.empty()){temp_stack.push(_mstack.top());_mstack.pop();}temp_stack.push(x);while (!temp_stack.empty()){_mstack.push(temp_stack.top());temp_stack.ppop();}}int pop() {int x = _mstack.front();_mstack.pop();return x;}int peek() {return _mstack.peek();}bool empty() {return _mstack.empty();}
private:std::stack<int> _mstack;
};
3. 包含min函数的栈
设计一个栈,使其能够比其他的栈多一个返回栈内最小值的函数。
分析:
需要有一个栈容器时刻保存栈上各个状态的最小值。
新来的数据和最小栈栈顶数据进行比较,如果比栈顶数据大,则再入栈一个栈顶数据,如果比栈顶数据小,则入栈新数据。
注意:最小栈保存的是各个状态下的最小值,它和MinStack里面维护的数据栈有着相同的数据个数。
class MinStack
{
public:MinStack(){}void push(int x)//如果比栈顶数据大,则再入栈一个栈顶数据,如果比栈顶数据小,则入栈新数据。{_data.push(x);if (_min.empty()){_min.push(x);}else{if (x > _min.top()){_min.push(_min.top());}_min.push(x);}}void pop(){_data.pop();_min.pop();}int top(){return _data.top();}int getMin(){return _min.top();}private:std::stack<int> _data;std::stack<int> _min;
};
4. 合法的出栈顺序
分析:
手上有两组顺序的数据,一组是1到n的有序排列,一组是给定的出栈顺序,要做的是将有序排列的数据试图按入栈出栈的操作变成前一组数据,成功了则返回true,否则false。
判断过程:
数据依次入栈,当入栈数据与第一组数据的第一个数相同时,出栈
此时面临两种选择,如果栈里的top与第一组数据中的第二个数相同,则继续出栈,否则后续数据继续入栈
如果所有数据入完栈,但栈中依然有数据未被弹出,则说明是非法的,返回false。
发现对于第一组数据,我们是从前往后依次取出比较,且比较后的数据丢弃不用,所以可以用队列做数据结构
bool check_is_valid_order(std::queue<int>& order)
{std::stack<int> S;int n = order.size();for (int i = 1; i <= n; i++){S.push(i);while (S.top() == order.front()&&!S.empty())//当栈顶元素和队列首元素相同且栈不为空{order.pop();S.pop();}}if (!S.empty()){return false;}elsereturn true;
}
5. 数组中第K大的数
分析:
思路1:将n个数构建为最大二叉堆,求第k大的数就是pop出k个最大值。这样做有两个问题,一个是要占用n的空间,且每次pop出去都要经历一次变换,因此一共要经历n+k次变换。
思路2:求什么就保存什么。求n个数据中第k大的数,于是创建一个容器,保存n个数中前k个最大值并且可以直接弹出第k大的值。于是想到最小二叉堆,用最小二叉堆保存k个数,则堆顶为k个数中的最小值,然后依次与后续n-k个数进行比较,若新数比堆顶元素大,则替换掉堆顶元素,始终保持这k个元素是n中的最大的k个数,且堆顶元素为第k大的值。
class Solution
{
public:int findKthLargest(std::vector<int>& nums, int k){std::priority queue<int, std::vector<int>, std::greater<int>> small_heap;for (int i = 0; i < nums.size(); i++){if (small_heap.size() < k)small_heap.push(nums[i]);else if (small_heap.top() < nums[i]){small_heap.pop();small_heap.push(nums[i]);}}return small_heap.top();}
};
6. 寻找中位数
设计一个数据结构,该数据结构动态维护一组数据,且支持如下操作
添加元素:将整形num添加到数据结构中
返回数据的中位数,返回其维护的数据的中位数
中位数的定义
若数据个数为奇数,中位数是该数组排序后的中间的数
若数据个数为偶数,中位数是中间两数的平均值。
分析:
动态维护一个最大堆和最小堆,各存储一半的元素,最大堆的堆顶值小于最小堆的堆顶值。
这使得最大堆保存较小的数据,最小堆保存较大的数据。如果最大堆数据量比最小堆多1,最大堆的堆顶就是中位数,如果最大堆和最小堆数据量一样,两个堆顶元素和的一半就是中位数。那么如何维护这两个堆呢?新来一个元素,如果这个元素比最大堆的堆顶小,就应该把它放到最大堆里,这样最大堆就多出来一个元素,如果第二个数也比最大堆堆顶小,就会多出两个元素,因此要把最大堆的堆顶弹出,放到最小堆里去。因此要判断最大堆和最小堆里数据量以及数据大小,再做分类。
class MedianFinder
{
public:std::priority queue<int, std::vector<int>, std::greater<int>> small_heap;std::priority queue<int, std::vector<int>, std::less<int>> big_heap;void addNum(int num){if (big_heap.empty())big_heap.push(num);else{if (big_heap.size() <= small.size()){if (num < big_heap.top())big_heap.push(num);else{samll_heap.push(num);big_heap.push(small_heap.top());samll_heap.pop();}}else{if (num > small_heap.top())small_heap.push(num);else{big_heap.push(num);small_heap.push(big_heap.top());big_heap.pop();}}}}double findMedian(){if (big_heap.empty() && samll_heap.empty())return NULL;if (big_heap.size() == samll_heap.size())return (big_heap.top() + small_heap.top()) / 2;if (big_heap.size() > small_heap.size())return big_heap.top();if (big_heap.size() < small_heap.size())return samll_heap.top();}
};
更多推荐
LeetCode算法学习笔记——栈/队列/堆
发布评论