【优选算法之队列+宽搜/优先级队列】No.14--- 经典队列+宽搜/优先级队列算法

文章目录

前言
一、队列+宽搜示例：
- 1.1 N 叉树的层序遍历
- 1.2 ⼆叉树的锯⻮形层序遍历
- 1.3 ⼆叉树最⼤宽度
- 1.4 在每个树⾏中找最⼤值
二、优先级队列（堆）示例：
- 2.1 最后⼀块⽯头的重量
- 2.2 数据流中的第 K ⼤元素
- 2.3 前 K 个⾼频单词
- 2.4 数据流的中位数

前言

在这里插入图片描述

👧个人主页：@小沈YO.
😚小编介绍：欢迎来到我的乱七八糟小星球🌝
📋专栏：优选算法
🔑本章内容：队列+宽搜/优先级队列
记得评论📝 +点赞👍 +收藏😽 +关注💞哦~

一、队列+宽搜示例：

1.1 N 叉树的层序遍历

题⽬链接：429. N 叉树的层序遍历
题⽬描述：
解法：
算法思路：
层序遍历即可~
仅需多加⼀个变量，⽤来记录每⼀层结点的个数就好了。
C++代码

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> vv;vector<int> v;if(root==nullptr)return vv;queue<Node*> q;q.push(root);while(!q.empty()){int sz=q.size();//统计本层节点个数while(sz--){Node* tmp=q.front();v.push_back(tmp->val);q.pop();for(auto&e:tmp->children)//逐次加入孩子节点{if(e!=nullptr)q.push(e);}}vv.push_back(v);v.clear();}return vv;}
};

1.2 ⼆叉树的锯⻮形层序遍历

题⽬链接：103. ⼆叉树的锯⻮形层序遍历
题⽬描述：
解法（层序遍历）：
算法思路：
在正常的层序遍历过程中，我们是可以把⼀层的结点放在⼀个数组中去的。
既然我们有这个数组，在合适的层数逆序就可以得到锯⻮形层序遍历的结果。
C++代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> vv;vector<int> v;if(root==nullptr)return vv;int cnt=0;queue<TreeNode*> q;q.push(root);while(!q.empty()){cnt++;int sz=q.size();while(sz--){TreeNode* tmp=q.front();q.pop();v.push_back(tmp->val);if(tmp->left!=nullptr)q.push(tmp->left);if(tmp->right!=nullptr)q.push(tmp->right);}if(cnt%2==0)reverse(v.begin(),v.end());vv.push_back(v);v.clear();}return vv;}
};

1.3 ⼆叉树最⼤宽度

题⽬链接：662. ⼆叉树最⼤宽度
题⽬描述：
解法（层序遍历）：
算法思路：

第⼀种思路（会超过内存限制）：
既然统计每⼀层的最⼤宽度，我们优先想到的就是利⽤层序遍历，把当前层的结点全部存在队列⾥⾯，利⽤队列的⻓度来计算每⼀层的宽度，统计出最⼤的宽度。但是，由于空节点也是需要计算在内的。因此，我们可以选择将空节点也存在队列⾥⾯。
这个思路是我们正常会想到的思路，但是极端境况下，最左边⼀条⻓链，最右边⼀条⻓链，我们需要存⼏亿个空节点，会超过最⼤内存限制。
第⼆种思路（利⽤⼆叉树的顺序存储 - 通过根节点的下标，计算左右孩⼦的下标）：
依旧是利⽤层序遍历，但是这⼀次队列⾥⾯不单单存结点信息，并且还存储当前结点如果在数组中存储所对应的下标（在我们学习数据结构 - 堆的时候，计算左右孩⼦的⽅式）。这样我们计算每⼀层宽度的时候，⽆需考虑空节点，只需将当层结点的左右结点的下标相减再加 1 即可。
但是，这⾥有个细节问题：如果⼆叉树的层数⾮常恐怖的话，我们任何⼀种数据类型都不能存下下标的值。但是没有问题，因为
• 我们数据的存储是⼀个环形的结构；
• 并且题⽬说明，数据的范围在 int 这个类型的最⼤值的范围之内，因此不会超出⼀圈；
• 因此，如果是求差值的话，我们⽆需考虑溢出的情况。

C++代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int widthOfBinaryTree(TreeNode* root) {queue<pair<TreeNode*,unsigned int>> q;q.push(make_pair(root,1));unsigned int cnt=0;while(!q.empty()){int sz=q.size();cnt=max(q.back().second-q.front().second+1,cnt);while(sz--){TreeNode* tmp=q.front().first;unsigned int ret=q.front().second;q.pop();if(tmp->left!=nullptr){q.push(make_pair(tmp->left,2*ret));}if(tmp->right!=nullptr){q.push(make_pair(tmp->right,2*ret+1));}}}return cnt;}
};
--------------------------------------------------------------------------------------------
//用数组模拟队列
/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int widthOfBinaryTree(TreeNode* root) {vector<pair<TreeNode*,unsigned int>> v;v.push_back({root,1});unsigned int cnt=0;while(v.size()){auto&[x1,y1]=v[0];auto&[x2,y2]=v.back();cnt=max(cnt,y2-y1+1);vector<pair<TreeNode*,unsigned int>> tmp;for(auto&[x,y]:v){if(x->left)tmp.push_back({x->left,2*y});if(x->right)tmp.push_back({x->right,2*y+1});}v=tmp;}return cnt;}
};

1.4 在每个树⾏中找最⼤值

题⽬链接：515. 在每个树⾏中找最⼤值
题⽬描述：
解法（bfs）：
算法思路：
层序遍历过程中，在执⾏让下⼀层节点⼊队的时候，我们是可以在循环中统计出当前层结点的最⼤值的。
因此，可以在 bfs 的过程中，统计出每⼀层结点的最⼤值。
C++代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> largestValues(TreeNode* root) {vector<int> v;if(root==nullptr)return v;queue<TreeNode*> q;q.push(root);int maxnum=INT_MIN;while(!q.empty()){int sz=q.size();while(sz--){TreeNode* tmp=q.front();maxnum=max(maxnum,tmp->val);q.pop();if(tmp->left)q.push(tmp->left);if(tmp->right)q.push(tmp->right);}v.push_back(maxnum);maxnum=INT_MIN;}return v;}
};

二、优先级队列（堆）示例：

2.1 最后⼀块⽯头的重量

题⽬链接：1046. 最后⼀块⽯头的重量
题⽬描述：
解法（利⽤堆）：
算法思路：
其实就是⼀个模拟的过程：
• 每次从⽯堆中拿出最⼤的元素以及次⼤的元素，然后将它们粉碎；
• 如果还有剩余，就将剩余的⽯头继续放在原始的⽯堆⾥⾯
重复上⾯的操作，直到⽯堆⾥⾯只剩下⼀个元素，或者没有元素（因为所有的⽯头可能全部抵消了）
那么主要的问题就是解决：
• 如何顺利的拿出最⼤的⽯头以及次⼤的⽯头；
• 并且将粉碎后的⽯头放⼊⽯堆中之后，也能快速找到下⼀轮粉碎的最⼤⽯头和次⼤⽯头；
这不正好可以利⽤堆的特性来实现嘛？
• 我们可以创建⼀个⼤根堆；
• 然后将所有的⽯头放⼊⼤根堆中；
• 每次拿出前两个堆顶元素粉碎⼀下，如果还有剩余，就将剩余的⽯头继续放⼊堆中；
这样就能快速的模拟出这个过程。
C++代码

class Solution {
public:struct cmp{bool operator()(int t1,int t2){return t1<t2;}};int lastStoneWeight(vector<int>& stones) {//priority_queue<int,vector<int>,less<int>> pq;priority_queue<int,vector<int>,cmp> pq;for(auto&e:stones)pq.push(e);while(pq.size()>1){int tmp1=pq.top();pq.pop();int tmp2=pq.top();pq.pop();int tmp=abs(tmp1-tmp2);if(tmp==0&&!pq.empty())continue;pq.push(tmp);}return pq.top();}
};

2.2 数据流中的第 K ⼤元素

题⽬链接：703. 数据流中的第 K ⼤元素
题⽬描述：
解法（优先级队列）：
算法思路：
我相信，看到 TopK 问题的时候，兄弟们应该能⽴⻢想到「堆」，这应该是刻在⻣⼦⾥的记忆。
C++代码

class KthLargest {priority_queue<int,vector<int>,greater<int>> pq;int _k;
public:KthLargest(int k, vector<int>& nums) {_k=k;for(auto&e:nums){pq.push(e);if(pq.size()>_k)pq.pop();}}int add(int val) {pq.push(val);if(pq.size()>_k)pq.pop();return pq.top();}
};/*** Your KthLargest object will be instantiated and called as such:* KthLargest* obj = new KthLargest(k, nums);* int param_1 = obj->add(val);*/

2.3 前 K 个⾼频单词

题⽬链接：692. 前 K 个⾼频单词
题⽬描述：
解法（堆）：
算法思路：
• 稍微处理⼀下原数组：
a. 我们需要知道每⼀个单词出现的频次，因此可以先使⽤哈希表，统计出每⼀个单词出现的频次；
b. 然后在哈希表中，选出前 k ⼤的单词（为什么不在原数组中选呢？因为原数组中存在重复的单词，哈希表⾥⾯没有重复单词，并且还有每⼀个单词出现的频次）
• 如何使⽤堆，拿出前 k ⼤元素：
a. 先定义⼀个⾃定义排序，我们需要的是前 k ⼤，因此需要⼀个⼩根堆。但是当两个字符串的频次相同的时候，我们需要的是字典序较⼩的，此时是⼀个⼤根堆的属性，在定义⽐较器的时候需要注意！
▪ 当两个字符串出现的频次不同的时候：需要的是基于频次⽐较的⼩根堆
▪ 当两个字符串出现的频次相同的时候：需要的是基于字典序⽐较的⼤根堆
b. 定义好⽐较器之后，依次将哈希表中的字符串插⼊到堆中，维持堆中的元素不超过 k 个；
c. 遍历完整个哈希表后，堆中的剩余元素就是前 k ⼤的元素
C++代码

class Solution {typedef pair<string,int> PII;
public:struct cmp{bool operator()(const PII& p1,const PII& p2){if(p1.second==p2.second)return p1.first<p2.first;// 频次相同，字典序按照⼤根堆的⽅式排列return p1.second>p2.second;}};vector<string> topKFrequent(vector<string>& words, int k) {priority_queue<PII,vector<PII>,cmp> pq;vector<string> v(k);unordered_map<string,int> hash;for(auto&e:words)hash[e]++;for(auto&e:hash){pq.push(e);if(pq.size()>k)pq.pop();}for(int i=k-1;i>=0;i--){v[i]=pq.top().first;pq.pop();}return v;}
};

2.4 数据流的中位数

题⽬链接：295. 数据流的中位数
题⽬描述：
解法（利⽤两个堆）：
算法思路：
这是⼀道关于「堆」这种数据结构的⼀个「经典应⽤」。
我们可以将整个数组「按照⼤⼩」平分成两部分（如果不能平分，那就让较⼩部分的元素多⼀个），较⼩的部分称为左侧部分，较⼤的部分称为右侧部分：
• 将左侧部分放⼊「⼤根堆」中，然后将右侧元素放⼊「⼩根堆」中；
• 这样就能在 O(1) 的时间内拿到中间的⼀个数或者两个数，进⽽求的平均数。
如下图所⽰：

于是问题就变成了「如何将⼀个⼀个从数据流中过来的数据，动态调整到⼤根堆或者⼩根堆中，并且保证两个堆的元素⼀致，或者左侧堆的元素⽐右侧堆的元素多⼀个」为了⽅便叙述，将左侧的「⼤根堆」记为 left ，右侧的「⼩根堆」记为 right ，数据流中来的「数据」记为 x 。
其实，就是⼀个「分类讨论」的过程：

如果左右堆的「数量相同」， left.size() == right.size() ：
a. 如果两个堆都是空的，直接将数据 x 放⼊到 left 中；
b. 如果两个堆⾮空：
i. 如果元素要放⼊左侧，也就是 x <= left.top() ：那就直接放，因为不会影响我们制定的规则；
ii. 如果要放⼊右侧
• 可以先将 x 放⼊ right 中，
• 然后把 right 的堆顶元素放⼊ left 中；
如果左右堆的数量「不相同」，那就是 left.size() > right.size() ：
a. 这个时候我们关⼼的是 x 是否会放⼊ left 中，导致 left 变得过多：
i. 如果 x 放⼊ right 中，也就是 x >= right.top() ，直接放；
ii. 反之，就是需要放⼊ left 中：
• 可以先将 x 放⼊ left 中，
• 然后把 left 的堆顶元素放⼊ right 中；
只要每⼀个新来的元素按照「上述规则」执⾏，就能保证 left 中放着整个数组排序后的「左半部分」， right 中放着整个数组排序后的「右半部分」，就能在 O(1) 的时间内求出平均数。

C++代码

class MedianFinder 
{priority_queue<int,vector<int>,less<int>> left;//大根堆priority_queue<int,vector<int>,greater<int>> right;//小根堆
public:MedianFinder() {}void addNum(int num) {int n=left.size(),m=right.size();if(n==m){if(!left.empty()&&num>left.top()){right.push(num);left.push(right.top());right.pop();}else left.push(num);}else if(n>m){if(num<=left.top()){right.push(left.top());left.pop();left.push(num);}else right.push(num);}}double findMedian() {if(left.size()==right.size())return (left.top()+right.top())/2.0;else return left.top();}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/