C++ map代码练习 1、2、priority_queue基础概念、对象创建、数据插入、获取堆顶、出队操作、大小操作，自定义结构、代码练习 1 2

map代码练习1，对应力扣 两个数据的交集，代码见下

class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {map<int, int> cnt;vector<int> ans;for(int i=0; i<nums1.size(); ++i){int x = nums1[i];cnt[x]++;}for(int i=0; i<nums2.size(); ++i){int x = nums2[i];if(cnt[x] > 0){cnt[x]--;ans.push_back(x);}}return ans;}
};

代码2，对应力扣，合并相似的物品

class Solution {
public:vector<vector<int>> mergeSimilarItems(vector<vector<int>>& items1, vector<vector<int>>& items2) {map<int, int> mp;for(int i=0; i<items1.size(); ++i){int val = items1[i][0];int weh = items1[i][1];mp[val] += weh; }for(int i=0; i<items2.size(); ++i){int val = items2[i][0];int weh = items2[i][1];mp[val] += weh; }vector<vector<int>> ans;for(map<int, int>::iterator it = mp.begin(); it != mp.end(); it++){int val = it->first;int weh = it->second;ans.push_back({val, weh});}return ans;}
};

priority_queue 优先级队列

parent(id) = (id - 1)/2

left(id) = id*2 + 1;

right(id) = id*2 + 2;

堆概念：满足比他的所有子节点大或者小

大顶堆：满足堆的概念（比所有子节点大），并且他的子节点也满足堆的概念（比所有子节点大）

小顶堆：满足堆的概念（比所有子节点小），并且他的子节点呀满足堆的概念（比所有子节点小）

大顶堆的增删查：

1，元素插入：往数组尾部插入一个元素、对插入的元素，比较他（在树形结构中）和他父节点的大小关系，来决定是否和父节点进行交换。这个就是优先队列的入队操作。

2，获取栈顶：获取数组的第0个元素

3，元素删除：把数组的第0个元素和最后有一个元素交换、然后对栈顶的元素不断做“下沉”操作，选择大的进行交换，直到“自己”成为最大的、删除数组的最后一个元素。

容器特点：

线性容器：vector string list

树形容器：set multiset map multimap

线性模拟树：priority_queue

priority_queue对象创建，代码见下

#include<iostream>
#include<queue>using namespace std;int main() {// 最大优先队列priority_queue<int> q1;// 最小优先队列priority_queue<int, vector<int>, greater<int>> q2;return 0;
}

priority_queue 数据插入

插入有一个特点，便是插入后的队列的第零个元素都是当前元素中最大的那个元素（这个队列是最大优先队列）。最小优先队列的话恰恰相反

代码见下：

#include<iostream>
#include<queue>using namespace std;int main() {// 最大优先队列priority_queue<int> q1;q1.push(6);q1.push(2);q1.push(1);q1.push(8); q1.push(16);q1.push(26);q1.push(9);// 最小优先队列priority_queue<int, vector<int>, greater<int>> q2;q2.push(6);q2.push(2);q2.push(1);q2.push(8);q2.push(16);q2.push(26);q2.push(9);return 0;
}

具体调试过程可见下，用于帮助理解：

priority_queue获取栈顶

#include<iostream>
#include<queue>using namespace std;int main() {// 最大优先队列priority_queue<int> q1;q1.push(6); cout << q1.top() << endl;q1.push(2); cout << q1.top() << endl;q1.push(1); cout << q1.top() << endl;q1.push(8); cout << q1.top() << endl;q1.push(16); cout << q1.top() << endl;q1.push(26); cout << q1.top() << endl;q1.push(9); cout << q1.top() << endl;cout << "-----------------------------";// 最小优先队列priority_queue<int, vector<int>, greater<int>> q2;q2.push(6); cout << q2.top() << endl;q2.push(2); cout << q2.top() << endl;q2.push(1); cout << q2.top() << endl;q2.push(8); cout << q2.top() << endl;q2.push(16); cout << q2.top() << endl;q2.push(26); cout << q2.top() << endl;q2.push(9); cout << q2.top() << endl;return 0;
}

这里的top其实便是front，见以下截图

priority_queue 出队操作，代码见下

#include<iostream>
#include<queue>using namespace std;int main() {// 最大优先队列priority_queue<int> q;q.push(6); q.push(2); q.push(1); q.push(8); q.push(16); q.push(26); q.push(9);for (int i = 0; i < 7; ++i) {cout << "top()" << q.top() << endl;q.pop();}return 0;
}

priority_queue 大小操作，代码见下

#include<iostream>
#include<queue>using namespace std;int main() {// 最大优先队列priority_queue<int> q;q.push(6); q.push(2); q.push(1); q.push(8); q.push(16); q.push(26); q.push(9);while (!q.empty()) {cout << "top()" << q.top() << "size()" << q.size() << endl;q.pop();}return 0;
}

priority_queue 自定义结构，代码见下

#include<iostream>
#include<queue>using namespace std;struct type {int key;int value;type() { key = value = 0; };type(int k, int v) :key(k), value(v){};bool operator<(const type& t) const { // 这里的第二个const是确保成员函数不被修改return key < t.key;}
};
int main() {priority_queue<type> q;q.push(type(6, 1));q.push(type(5, 2));q.push(type(4, 2));q.push(type(8, 3));q.push(type(9, 2));while (!q.empty()) {cout << "top() = " << q.top().key << ", size()=" << q.size() << endl;q.pop();}return 0;
}

代码练习一，对应力扣，丑数 || 代码见下

class Solution {#define ll long long
public:int nthUglyNumber(int n) {priority_queue<ll, vector<ll>, greater<ll>> q;q.push(1);ll pre = -1;while(1){ll val = q.top();q.pop();while(val == pre){val = q.top();q.pop();}pre = val;--n;if(n==0){return val;}q.push(val * 2);q.push(val * 3);q.push(val * 5);}return -1;}
};

代码练习 2 对应力扣 矩阵中的和，代码见下

class Solution {
public:int matrixSum(vector<vector<int>>& nums) {int n = nums.size();int m = nums[0].size();priority_queue<int> q[300];for(int i=0; i<n; ++i){for(int j=0; j<m; ++j){q[i].push(nums[i][j]);}}int sum = 0;while(m--){int ret = 1;for(int i=0; i<n; ++i){ret = max(ret, q[i].top());q[i].pop();}sum += ret;}return sum;}
};