目录
leetcode题目
一、数组中两元素的最大乘积
求数组中最大的两个元素top1, top2, 返回(top1-1)*(top2-1)
2.算法分析
遍历数组，放入优先级队列中，pop出最大的两个元素，求结果即可
3.算法代码
class Solution {
public:
int maxProduct(vector<int>& nums)
{
priority_queue<int> q;
for(auto x : nums)
q.push(x);
int top1 = q.top();
q.pop();
int top2 = q.top();
q.pop();
return (top1-1) * (top2-1);
}
};二、最后一块石头的重量
1046. 最后一块石头的重量 - 力扣（LeetCode）
https://leetcode.cn/problems/last-stone-weight/description/1.题目解析
每次选取最重的两块石头，两两碰撞，重量小的粉碎，重量大的石头剩余重量为原始重量-重量小的石头的重量，最终如果剩一块石头，就返回该石头的重量；如果没有剩石头，就返回0
2.算法分析
用堆(优先级队列) 模拟即可
3.算法代码
class Solution {
public:
int lastStoneWeight(vector<int>& stones)
{
priority_queue<int> heap; //默认大堆
for(auto x : stones)
heap.push(x);
while(heap.size() > 1)
{
int a = heap.top();
heap.pop();
int b = heap.top();
heap.pop();
if(a > b) heap.push(a-b);
}
return heap.size() == 1 ? heap.top() : 0;
}
};三、数据流中的第 K 大元素
703. 数据流中的第 K 大元素 - 力扣（LeetCode）https://leetcode.cn/problems/kth-largest-element-in-a-stream/1.题目解析
实现一个类， 返回给定数组的第K大元素(排序之后的)(不断新增数据)
2.算法分析
典型的top-k问题，用优先级队列来解决~
详见博客: 独树一帜的完全二叉树---堆-CSDN博客
3.算法代码
class KthLargest {
public:
KthLargest(int k, vector<int>& nums)
{
_k = k;
for(auto x : nums)
{
heap.push(x); //小堆
if(heap.size() > _k) heap.pop();
}
}
int add(int val)
{
heap.push(val);
if(heap.size() > _k) heap.pop();
return heap.top();
}
private:
priority_queue<int, vector<int>, greater<int>> heap; //小堆
int _k;
};
四、前K个高频元素
347. 前 K 个高频元素 - 力扣（LeetCode）https://leetcode.cn/problems/top-k-frequent-elements/1.题目解析
给定一个数组，返回该数组中出现次数最多的k个元素, 顺序任意
2.算法分析
典型的top-k问题，不过求的不是前K大的元素或前K小的元素，而是求前K个出现次数最多的元素，因此我们先用哈希表绑定每个元素和其出现的次数；然后定义优先级队列， 每个元素类型是pair<int, int> (传仿函数指定比较规则，按照pair中的second也就是元素次数进行比较，由于求的是出现次数最多的k个单词，因此建小堆), 最后从优先级队列中提取结果即可
3.算法代码
class Solution {
public:
typedef pair<int, int> PII;
struct cmp
{
bool operator()(const PII& p1, const PII& p2)
{
return p1.second > p2.second; //小堆比较规则
}
};
vector<int> topKFrequent(vector<int>& nums, int k)
{
//1.哈希表统计次数
unordered_map<int, int> hash; //单词-次数
for(auto& e : nums)
hash[e]++;
//2.Top-K的主逻辑
priority_queue<PII, vector<PII>, cmp> heap;
for(auto& pii : hash)
{
heap.push(pii);
if(heap.size() > k) heap.pop();
}
//3.提取结果
vector<int> ret(k);
for(int i = k-1; i >= 0; i--)
{
ret[i] = heap.top().first;
heap.pop();
}
return ret;
}
};五、前K个高频单词
692. 前K个高频单词 - 力扣（LeetCode）https://leetcode.cn/problems/top-k-frequent-words/1.题目解析
返回前k个出现次数最多的单词，如果出现频次相同，按照字典序从小到大排列
2.算法分析
同样是top-k问题，但是比较规则有所变化，在priority_queue中传递仿函数指定比较规则即可~
仿函数博客: stack 与 queue 与 priority_queue 与 仿函数 与 模板进阶-CSDN博客
1.哈希表统计单词出现次数
2.创建大小为k的堆
比较规则:
①单词频次不同时，由于频次高的往前排，因此创建小根堆
②单词频次相同时，谁的字典序小谁往前排，因此创建大根堆
3. top-K的主逻辑
4. 提取结果(注意在vector中存放的顺序)
3.算法代码
class Solution {
typedef pair<string, int> PSI;
struct cmp
{
bool operator()(const PSI& a, const PSI& b)
{
if(a.second == b.second) //频次相同，字典序按照大根堆的方式排列
return a.first < b.first;
return a.second > b.second;
}
};
public:
vector<string> topKFrequent(vector<string>& words, int k)
{
//1.哈希表统计单词频次
unordered_map<string, int> hash;
for(auto& s : words)
hash[s]++;
//2.创建大小为k的堆
priority_queue<PSI, vector<PSI>, cmp> heap;
//3.top-k主逻辑
for(auto& psi : hash)
{
heap.push(psi);
if(heap.size() > k) heap.pop();
}
//4.提取结果
vector<string> ret(k);
for(int i = k - 1; i >= 0; i--)
{
ret[i] = heap.top().first;
heap.pop();
}
return ret;
}
};六、数据流的中位数
295. 数据流的中位数 - 力扣（LeetCode）https://leetcode.cn/problems/find-median-from-data-stream/description/1.题目解析
实现一个类，求数据流的中位数(不断新增数据), 奇数个元素返回中位数，偶数个元素返回中间两个数的平均值
2.算法分析
大小堆维护数据流的中位数
1.当 m == n, 中位数就是两个堆的堆顶元素的平均值
2.当 m == n + 1, 中位数就是大根堆的堆顶元素
细节问题: add()函数, 插入num元素
1. m == n
1.1 num <= x 或 m == 0, 此时进入大根堆, m == n + 1
1.2 num > x, 进入小根堆, 此时 n = m + 1, 因此我们需要调整， 只需要把小根堆的堆顶元素挪到大根堆的堆顶即可~
2. m == n+1
2.2 num <= x, 此时进入大根堆, m == n + 2, 因此我们需要调整, 只需要将大根堆的堆顶元素挪到小根堆的堆顶即可~
2.2 num > x, 此时进入小根堆, m == n
3.算法代码
class MedianFinder {
public:
MedianFinder()
{}
void addNum(int num)
{
if(left.size() == right.size())
{
if(left.empty() || num <= left.top())
left.push(num);
else
{
right.push(num);
left.push(right.top());
right.pop();
}
}
else
{
if(num <= left.top())
{
left.push(num);
right.push(left.top());
left.pop();
}
else
right.push(num);
}
}
double findMedian()
{
if(left.size() == right.size())
return (left.top() + right.top()) / 2.0;
else
return left.top();
}
private:
priority_queue<int> left; //大根堆
priority_queue<int, vector<int>, greater<int>> right; //小根堆
};
七、有序矩阵中的第K小的元素
求矩阵中第K小的元素
2.算法分析
优先级队列
3.算法代码
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k)
{
priority_queue<int> heap;
int m = matrix.size(), n = matrix[0].size();
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
heap.push(matrix[i][j]);
if(heap.size() > k) heap.pop();
}
}
return heap.top();
}
};八、根据字符出现频率排序
451. 根据字符出现频率排序 - 力扣（LeetCode）https://leetcode.cn/problems/sort-characters-by-frequency/1.题目解析
把出现频率高的字符排在前面， 输出新的字符串
2.算法分析
优先级队列
3.算法代码
class Solution {
typedef pair<char, int> PCI;
public:
struct cmp
{
bool operator()(const PCI& p1, const PCI& p2)
{
return p1.second < p2.second; //大堆
}
};
string frequencySort(string s)
{
//1.哈希表统计频次
unordered_map<char, int> hash;
for(auto ch : s)
hash[ch]++;
//2.top-k的主逻辑
priority_queue<PCI, vector<PCI>, cmp> heap;
for(auto pci : hash)
heap.push(pci);
//3.提取结果
string ret;
while(!heap.empty())
{
auto top = heap.top();
for(int i = 0; i < top.second; i++)
ret += top.first;
heap.pop();
}
return ret;
}
};