文章目录
- ~~~~~~~~~~~~队列~~~~~~~~~~~~
- 232. 用栈实现队列
-
- 解法1：栈+队列
- 71. 简化路径
-
- 解法1：deque+字符串模拟
- 剑指 Offer 59 - II. 队列的最大值
-
- 解法1：deque+queue
- ~~~~~~~~~~~~优先队列（堆）~~~~~~~~~~~~
-
- 一.队列和优先队列的差别
- 二.优先队列（堆）的特性
- 三.基本的堆操作
- 四.C++中优先级队列的定义
- 五.通过重写仿函数来支持自定义数据类型
- 六.通过运算符重载来支持自定义比较函数
- 215. 数组中的第K个最大元素
-
- 解法1：堆排序
- 解法2：快排思想
- 23. 合并K个升序链表
-
- 解法1：优先队列
- 解法2：优化优先队列
- 解法3：两两合并
- 解法4：分治
- 630. 课程表 III
-
- 解法1：贪心+优先队列
- 1405. 最长快乐字符串
-
- 解法1：贪心+优先队列
- 剑指 Offer 41. 数据流中的中位数
-
- 解法1：两个优先队列
- 767. 重构字符串
-
- 解法1：最大堆+哈希表
- 相似题目：621. 任务调度器
-
- 解法1：桶思想+排序
- 239. 滑动窗口最大值
-
- 解法1：单调队列
- 解法2：优先队列
- 451. 根据字符出现频率排序
-
- 解法1：优先队列（堆排序）
队列 232. 用栈实现队列 力扣链接
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
进阶：
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
示例：
输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
解法1：栈+队列 思路：
（1）这是一道模拟题，不涉及到具体算法，考察的就是对栈和队列的掌握程度。
（2）使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。
（3）在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
（4）最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。
代码：
class MyQueue {
public:
stack staIn;
//输入栈
stack staOut;
//输出栈MyQueue() {
}//构造函数void push(int x) {
staIn.push(x);
}int pop() {
//当输出栈为空时，将输入栈的所有元素导入输出栈，然后执行pop；否则就先pop再导入
if (staOut.empty())
{
// 从stIn导入数据直到stIn为空
while (!staIn.empty()){
staOut.push(staIn.top());
staIn.pop();
}
}
int result = staOut.top();
staOut.pop();
return result;
}int peek() {
// 直接使用已有的pop函数
int result = this->pop();
staOut.push(result);
// 因为pop函数弹出了元素res，所以再添加回去
return result;
}bool empty() {
return staIn.empty() && staOut.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
复杂度分析：
篇)](http://img.readke.com/220601/105145E09-0.jpg)
文章图片
71. 简化路径 力扣链接
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，‘//’）都被视为单个斜杠 ‘/’ 。 对于此问题，任何其他格式的点（例如，‘…’）均被视为文件/目录名称。
请注意，返回的 规范路径 必须遵循下述格式：
始终以斜杠 ‘/’ 开头。
两个目录名之间必须只有一个斜杠 ‘/’ 。
最后一个目录名（如果存在）不能 以 ‘/’ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘…’）。
返回简化后得到的 规范路径 。
示例 1：
输入：path = “/home/”
输出：“/home”
解释：注意，最后一个目录名后面没有斜杠。
示例 2：
输入：path = “/…/”
输出：“/”
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。
示例 3：
输入：path = “/home//foo/”
输出：“/home/foo”
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入：path = “/a/./b/…/…/c/”
输出：“/c”
提示：
1 <= path.length <= 3000
path 由英文字母，数字，‘.’，‘/’ 或 ‘_’ 组成。
path 是一个有效的 Unix 风格绝对路径。
解法1：deque+字符串模拟 思路：
1 根据’/‘分隔字符串，对于空字符串或’.‘无需理会，因为’.‘代表当前路径
2 将分割出来的字符串加入到deque尾部，如果是’…'且队列不为空,则从尾部删除。
3 将双端队列里的字符串按先进先出的顺序加入ans
代码：
class Solution {
public:
string simplifyPath(string path) {
deque> dq;
string result = "", local = "";
for(int i = 0;
i<=path.size();
i++){
if(i == path.size() || path[i] == '/'){
if(local != "" && local != "."){
if(local == ".."){
if(dq.size()) dq.pop_back();
}
else{
dq.push_back(local);
}
}
local = "";
}
else{
local += path[i];
}
}while(!dq.empty()){
result += "/";
result += dq.front();
dq.pop_front();
}
if(result == "") return "/";
return result;
}
};
复杂度分析：
时间复杂度：O(n)，其中 nn 是字符串 path 的长度。
空间复杂度：O(n)。我们需要 O(n) 的空间存储 names 中的所有字符串。
剑指 Offer 59 - II. 队列的最大值 力扣链接
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入:
[“MaxQueue”,“push_back”,“push_back”,“max_value”,“pop_front”,“max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：
输入:
[“MaxQueue”,“pop_front”,“max_value”]
[[],[],[]]
输出: [null,-1,-1]
限制：
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5
解法1：deque+queue 思路：
参考
篇)](http://img.readke.com/220601/1051451C5-1.jpg)
文章图片
代码：
class MaxQueue {
private:
queue q;
deque d;
public:
MaxQueue() {}int max_value() {
if(d.empty()) return -1;
return d.front();
}void push_back(int value) {
while(!d.empty() && value > d.back()){
d.pop_back();
}
d.push_back(value);
q.push(value);
}int pop_front() {
if(q.empty()) return -1;
int res = q.front();
q.pop();
if(res == d.front()) d.pop_front();
return res;
}
};
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue* obj = new MaxQueue();
* int param_1 = obj->max_value();
* obj->push_back(value);
* int param_3 = obj->pop_front();
*/
篇)](http://img.readke.com/220601/105145K31-2.jpg)
文章图片
优先队列（堆） 该部分主要参考最详细版图解优先队列（堆）
一.队列和优先队列的差别
篇)](http://img.readke.com/220601/105145H12-3.jpg)
文章图片
篇)](http://img.readke.com/220601/1051451157-4.jpg)
文章图片
二.优先队列（堆）的特性
篇)](http://img.readke.com/220601/1051453452-5.jpg)
文章图片
篇)](http://img.readke.com/220601/10514532M-6.jpg)
文章图片
三.基本的堆操作
篇)](http://img.readke.com/220601/10514534Y-7.jpg)
文章图片
篇)](http://img.readke.com/220601/1051451321-8.jpg)
文章图片
四.C++中优先级队列的定义 参考
（1）priority_queue 容器适配器定义了一个元素有序排列的队列。默认队列头部的元素优先级最高。 因为它是一个队列，所以只能访问第一个元素，这也意味着优先级最高的元素总是第一个被处理。但是如何定义“优先级”完全取决于我们自己。如果一个优先级队列记录的是医院里等待接受急救的病人，那么病人病情的严重性就是优先级。如果队列元素是银行的借贷业务，那么借记可能会优先于信贷。
（2）
C++中，使用优先级队列需要包含头文件，优先级队列的定义如下：
priority_queue
1.typename是数据的类型；
2.container是容器类型，可以是vector,queue等用数组实现的容器，不能是list，默认可以用vector；
3.functional是比较的方式，默认是大顶堆（就是元素值越大，优先级越高）；如果使用C++基本数据类型，可以直接使用自带的less和greater这两个仿函数（默认使用的是less，就是构造大顶堆，元素小于当前节点时下沉）。使用自定义的数据类型的时候，可以重写比较函数，也可以进行运算符重载（less重载小于“<”运算符，构造大顶堆；greater重载大于“>”运算符，构造小顶堆）。
定义一个优先级队列的示例如下：
//构造一个大顶堆，堆中小于当前节点的元素需要下沉，因此使用less
priority_queue, less> priQueMaxFirst;
//构造一个小顶堆，堆中大于当前节点的元素需要下沉，因此使用greater
priority_queue, greater> priQueMinFirst;
五.通过重写仿函数来支持自定义数据类型 仿函数是通过重载“()”运算符来模拟函数操作的类。
先自定义一个类Data，将id作为该类的关键字，进行比较，重写仿函数。
//自定义数据类型，Data类
class Data
{
public:
Data(int i, int d) :id(i), data(d) {}
~Data() {}
int getId() { return id;
}
int getData() { return data;
}
private:
int id;
int data;
};
//重写仿函数，完成less的功能，也可以用class定义类，此时需要将运算符重载函数设为public
//结构体struct中默认是访问类型是public
struct cmp
{
bool operator() ( Data &a, Data &b) {
return a.getId() < b.getId();
}
};
int main(void){
priority_queue, cmp > priQueMaxFirst;
//该优先级队列维护一个大顶堆，因此最大的元素最先出队
...//一系列操作
...
return 0;
}
六.通过运算符重载来支持自定义比较函数
#include
#include
using namespace std;
//方法1
struct tmp1 //运算符重载<
{
int x;
tmp1(int a) {x = a;
}
bool operator<(const tmp1& a) const
{
return x < a.x;
//大顶堆
}
};
//方法2
struct tmp2 //重写仿函数
{
bool operator() (tmp1 a, tmp1 b)
{
return a.x < b.x;
//大顶堆
}
};
int main()
{
tmp1 a(1);
tmp1 b(2);
tmp1 c(3);
priority_queue d;
d.push(b);
d.push(c);
d.push(a);
while (!d.empty())
{
cout << d.top().x << '\n';
d.pop();
}
cout << endl;
priority_queue, tmp2> f;
f.push(b);
f.push(c);
f.push(a);
while (!f.empty())
{
cout << f.top().x << '\n';
f.pop();
}
}
215. 数组中的第K个最大元素 力扣链接
给定整数数组 nums 和整数 k，请返回数组中第 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
提示：
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
解法1：堆排序 思路：
优先队列的思路是很朴素的。由于找第 K 大元素，其实就是整个数组排序以后后半部分（k个）最小的那个元素。因此，我们可以维护一个有 K 个元素的最小堆：
1.如果当前堆不满，直接添加；
2.堆满的时候，如果新读到的数小于等于堆顶，肯定不是我们要找的元素，只有新遍历到的数大于堆顶的时候，才将堆顶拿出，然后放入新读到的数，进而让堆自己去调整内部结构
代码：
class Solution {
public:
int findKthLargest(vector& nums, int k) {
if (nums.size() == 0 || nums.size() < k) return 0;
priority_queue,greater> heap;
for (int i = 0;
iheap.top()){
heap.pop();
heap.push(nums[i]);
}
}
return heap.top();
}
};
篇)](http://img.readke.com/220601/1051454Z1-9.jpg)
文章图片
复杂度分析：
时间复杂度：O(NlogK)，遍历数据 O(N)，堆内元素调整 O(K)；
空间复杂度：O(K)。
解法2：快排思想 思路：
思路
代码：
class Solution {
public:
//快排思想
int partition(vector& nums, int l, int r){
int i = rand() % (r-l+1) + l;
swap(nums[i],nums[l]);
int p = nums[l];
while(l < r){
while(l < r && nums[r] >= p ) r--;
swap(nums[r],nums[l]);
while(l < r && nums[l] < p ) l++;
swap(nums[r],nums[l]);
}
return l;
}
int qSort(vector& nums, int l, int r, int k){
int p = partition(nums, l, r);
if(p == nums.size() - k) return nums[p];
else if(p < nums.size() - k) return qSort(nums, p+1, r, k);
else return qSort(nums, l, p-1, k);
}
int findKthLargest(vector& nums, int k) {
return qSort(nums, 0, nums.size() - 1, k);
}
};
篇)](http://img.readke.com/220601/1051452439-10.jpg)
文章图片
23. 合并K个升序链表 力扣链接
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
解法1：优先队列 思路：
篇)](http://img.readke.com/220601/1051451b2-11.jpg)
文章图片
篇)](http://img.readke.com/220601/105145I16-12.jpg)
文章图片
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode() : val(0), next(nullptr) {}
*ListNode(int x) : val(x), next(nullptr) {}
*ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
struct Node{
int val;
//数据域
ListNode* ptr;
//指针域
bool operator < (const Node& r) const {
if(val > r.val) return true;
//小根堆
return false;
}
};
ListNode* mergeKLists(vector& lists) {
//创建一个堆，并设置元素的排序方式
priority_queue que;
//遍历链表数组，将每个链表的每个结点放入堆
for(int i = 0;
ival,lists[i]});
lists[i] = lists[i]->next;
}
}
//从堆中不断取出元素，并串联起来
ListNode* head = new ListNode;
ListNode* pre = head;
while(!que.empty()){
pre->next = que.top().ptr;
que.pop();
pre = pre->next;
}pre->next = nullptr;
return head->next;
}
};
复杂度分析：
时间复杂度：O（kn*logkn）
空间复杂度：O(kn)
解法2：优化优先队列 思路：
篇)](http://img.readke.com/220601/1051454641-13.jpg)
文章图片
复杂度分析：
篇)](http://img.readke.com/220601/105145G14-14.jpg)
文章图片
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode() : val(0), next(nullptr) {}
*ListNode(int x) : val(x), next(nullptr) {}
*ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
struct Node{
int val;
ListNode* ptr;
bool operator < (const Node& r) const{
return val > r.val;
}
};
ListNode* mergeKLists(vector& lists) {
priority_queue que;
ListNode* head = new ListNode;
ListNode* pre = head;
//这里跟上一版不一样，不再是一股脑全部放到堆中
//而是只把k个链表的第一个节点放入到堆中
for(int i = 0;
ival,lists[i]});
}//之后不断从堆中取出节点，如果这个节点还有下一个节点，
//就将下个节点也放入堆中
while(!que.empty()){
pre->next = que.top().ptr;
que.pop();
pre = pre->next;
if(pre->next != nullptr) que.push({pre->next->val,pre->next});
}
pre->next = nullptr;
return head->next;
}
};
解法3：两两合并 思路：
篇)](http://img.readke.com/220601/1051455517-15.jpg)
文章图片
复杂度分析：
篇)](http://img.readke.com/220601/105145GP-16.jpg)
文章图片
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode() : val(0), next(nullptr) {}
*ListNode(int x) : val(x), next(nullptr) {}
*ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector& lists) {
if(lists.size() == 0) return nullptr;
//两两合并
//将lists[0]作为最终合并的链表，然后将list[0]和lists[1]合并成lists[0-1]
//再将lists[0-1]和lists[2]合并，如此反复最终lists[0]就是最终结果
ListNode* result = lists[0];
for(int i = 1;
ival < b->val){
a->next = mergeTwoLists(a->next,b);
return a;
}else{
b->next = mergeTwoLists(a,b->next);
return b;
}
}
};
解法4：分治 思路：
篇)](http://img.readke.com/220601/105145A58-17.jpg)
文章图片
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
*int val;
*ListNode *next;
*ListNode() : val(0), next(nullptr) {}
*ListNode(int x) : val(x), next(nullptr) {}
*ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector& lists) {
if(lists.size() == 0) return nullptr;
return helper(lists,0,lists.size()-1);
}ListNode* helper(vector& lists,int start, int end){
if (start == end) return lists[start];
int mid = start + (end-start)/2;
ListNode* left = helper(lists,start,mid);
ListNode* right = helper(lists,mid+1,end);
return mergeTwoLists(left,right);
}ListNode* mergeTwoLists(ListNode* a, ListNode* b){
if(a == nullptr) return b;
else if (b == nullptr) return a;
else if(a->val < b->val){
a->next = mergeTwoLists(a->next,b);
return a;
}else{
b->next = mergeTwoLists(a,b->next);
return b;
}
}
};
篇)](http://img.readke.com/220601/1051453b2-18.jpg)
文章图片
复杂度分析：
篇)](http://img.readke.com/220601/1051452549-19.jpg)
文章图片
630. 课程表 III 力扣链接
这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
返回你最多可以修读的课程数目。
示例 1：
输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。
示例 2：
输入：courses = [[1,2]]
输出：1
示例 3：
输入：courses = [[3,2],[4,3]]
输出：0
提示:
1 <= courses.length <= 104
1 <= durationi, lastDayi <= 104
解法1：贪心+优先队列 思路：
代码：
class Solution {
public:
static bool cmp(const vector& a ,const vector& b){
return a[1] < b[1];
}
int scheduleCourse(vector>& courses) {
//将课程结束时间按升序排序
sort(courses.begin(),courses.end(),cmp);
//大根堆，将课程持续时间最长的课放在堆顶
priority_queue que;
int sum = 0;
//从课程结束时间最早的开始加入堆中，如果碰到总课程时间大于课程结束时间
//就把当前队列中最耗时的课程给弹出队列，借此贪心保证学习的课程最多
for(vector& course:courses){
int day = course[0],end = course[1];
que.push(day);
sum += day;
if(sum > end){
sum-=que.top();
que.pop();
}
}
return que.size();
}
};
复杂度分析：
时间复杂度：O(nlogn)
空间复杂度：O(n)
1405. 最长快乐字符串 力扣链接
如果字符串中不含有任何 ‘aaa’，‘bbb’ 或 ‘ccc’ 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：
s 是一个尽可能长的快乐字符串。
s 中 最多 有a 个字母 ‘a’、b 个字母 ‘b’、c 个字母 ‘c’ 。
s 中只含有 ‘a’、‘b’ 、‘c’ 三种字母。
如果不存在这样的字符串 s ，请返回一个空字符串 “”。
示例 1：
输入：a = 1, b = 1, c = 7
输出：“ccaccbcc”
解释：“ccbccacc” 也是一种正确答案。
示例 2：
输入：a = 2, b = 2, c = 1
输出：“aabbc”
示例 3：
输入：a = 7, b = 1, c = 0
输出：“aabaa”
解释：这是该测试用例的唯一正确答案。
提示：
0 <= a, b, c <= 100
a + b + c > 0
解法1：贪心+优先队列 代码：
struct cmp{
bool operator()(const pair& a, const pair& b){
return a.second < b.second;
}
};
class Solution {
public:
string longestDiverseString(int a, int b, int c) {
// 大顶堆，数量多的在最上面
priority_queue, vector>, cmp> pq;
//大根堆
// 初始化入堆
if(a != 0) pq.push(pair{0,a});
if(b != 0) pq.push(pair{1,b});
if(c != 0) pq.push(pair{2,c});
string result = "";
while(pq.size()){
auto [ch,cnt] = pq.top();
pq.pop();
// 如果字符串后两位等于数量最多的，那么数量最多的不能再加入字符串了
if(result.size() >= 2 && result[result.size()-1] - 'a' == ch && result[result.size()-2] - 'a' == ch){
if(!pq.empty()){
// 我们就加入数量次多的
auto [ch1,cnt1] = pq.top();
pq.pop();
result += ch1+'a';
// 数量次多的使用了一个之后还有剩余，重新入堆
if(--cnt1>0) pq.push(pair{ch1,cnt1});
// 数量最多的重新入堆
pq.push(pair{ch,cnt});
}
}else{
// 不满足上面的条件，我们直接使用数量最多的
result += ch+'a';
// 数量最多的使用了一个之后还有剩余，重新入堆
if(--cnt>0) pq.push(pair{ch,cnt});
}
}
return result;
}
};
篇)](http://img.readke.com/220601/1051455345-20.jpg)
文章图片
剑指 Offer 41. 数据流中的中位数 力扣链接
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入：
[“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入：
[“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
限制：
最多会对 addNum、findMedian 进行 50000 次调用。
注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-stream/
解法1：两个优先队列 思路：
篇)](http://img.readke.com/220601/1051456015-21.jpg)
文章图片
篇)](http://img.readke.com/220601/105145N46-22.jpg)
文章图片
篇)](http://img.readke.com/220601/1051453H2-23.jpg)
文章图片
代码：
class MedianFinder {
public:
priority_queue,less> maxPq;
//最大堆，存储左边数据
priority_queue,greater> minPq;
//最小堆，存储右边数据
/** initialize your data structure here. */
MedianFinder() {}void addNum(int num) {
if(maxPq.size() == minPq.size()){
minPq.push(num);
int top = minPq.top();
minPq.pop();
maxPq.push(top);
}else{
maxPq.push(num);
int top = maxPq.top();
maxPq.pop();
minPq.push(top);
}
}double findMedian() {
if(maxPq.size() == minPq.size()){
return (maxPq.top() + minPq.top()) / 2.0;
}else{
return maxPq.top() * 1.0;
}
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
篇)](http://img.readke.com/220601/105145D06-24.jpg)
文章图片
767. 重构字符串 力扣链接
给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。
返回 s 的任意可能的重新排列。若不可行，返回空字符串 “” 。
示例 1:
输入: s = “aab”
输出: “aba”
示例 2:
输入: s = “aaab”
输出: “”
提示:
1 <= s.length <= 500
s 只包含小写字母
解法1：最大堆+哈希表 思路：
以 aaaabbbcc 为例：
可以看出，由于两个相邻的字符不能相同，我们需要把出现次数最多的字符先放完，才有可能有满足题意的结果。于是：
1.第一次都取出现次数最多的字符’a’ 放置
2.第二次只能取出现次数第二多的字符 ‘b’ 放置（因为不能取和 ‘a’ 相同的字符）
观察规律可以发现我们可以维护一个大顶堆 Q 和一个last元素。大顶堆 Q 以字符出现的次数排序，last元素包含某个字符和该字符出现的次数。
每pop出堆顶，返回值就加上堆顶的字符，并且堆顶字符出现的次数减一，保存在last中
代码：
class Solution {
public:
string reorganizeString(string s) {
unordered_map umap;
for(auto& c:s) umap[c]++;
priority_queue> pq;
for(pair x:umap) pq.push({x.second,x.first});
string res;
pair last;
while(!pq.empty()){
auto [i,c] = pq.top();
pq.pop();
res += c;
if(last.first > 0) pq.push(last);
last = {i-1,c};
}
return last.first > 0 ? "":res;
}
};
相似题目：621. 任务调度器 力扣链接
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
示例 1：
输入：tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
示例 2：
输入：tasks = [“A”,“A”,“A”,“B”,“B”,“B”], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
[“A”,“A”,“A”,“B”,“B”,“B”]
[“A”,“B”,“A”,“B”,“A”,“B”]
[“B”,“B”,“B”,“A”,“A”,“A”]
…
诸如此类
示例 3：
输入：tasks = [“A”,“A”,“A”,“A”,“A”,“A”,“B”,“C”,“D”,“E”,“F”,“G”], n = 2
输出：16
解释：一种可能的解决方案是：
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A
提示：
1 <= task.length <= 104
tasks[i] 是大写英文字母
n 的取值范围为 [0, 100]
解法1：桶思想+排序 思路：
我们只需要算两个数：
用出现最多字母的次数max作为桶的数量，最后一个桶只有当其他字母出现数量与桶数量相同时，才能放入字母。
桶有固定容量（n + 1), 则会出现两种情况：
①桶的容量没有满，则需要（n + 1） * （max - 1） + cnt 空间， 最后的cnt是指最后一个桶放的字母数量
②桶的容量满了， 这里要注意桶容量是可以看做是无限的， 但是有一个最小值（n+ 1）。桶容量满了则不会浪费空间，为tasks.size()。
篇)](http://img.readke.com/220601/10514524Y-25.jpg)
文章图片
代码：
class Solution {
public:
int leastInterval(vector& tasks, int n) {
if(n == 0) return tasks.size();
int len = tasks.size();
vector vec(26);
for(auto& c:tasks){
vec[c-'A']++;
}
sort(vec.begin(),vec.end(),[&](const int& a, const int& b){
return a > b;
});
int res = (vec[0]-1)*(n+1), cnt = 1;
while(cnt < vec.size() && vec[cnt] == vec[0]) cnt++;
return max(res + cnt,len);
}
};
239. 滑动窗口最大值 力扣链接
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
解法1：单调队列 思路：
代码随想录
代码：
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
//单调队列
int n = nums.size();
deque dq;
for(int i = 0;
i= nums[dq.back()]){
dq.pop_back();
}
dq.push_back(i);
}
vector res = {nums[dq.front()]};
for(int i = k;
i= nums[dq.back()]){
dq.pop_back();
}
dq.push_back(i);
while(dq.front() <= i - k){
dq.pop_front();
}
res.push_back(nums[dq.front()]);
}
return res;
}
};
篇)](http://img.readke.com/220601/10514540M-26.jpg)
文章图片
解法2：优先队列 【数据结构与算法基础|[力扣刷题总结](队列和优先队列(堆)篇)】思路：
代码：
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
//优先队列 默认是最大堆
int n = nums.size();
priority_queue> pq;
//num-下标
for(int i = 0;
i res = {pq.top().first};
for(int i = k;
i 篇)](http://img.readke.com/220601/1051455963-27.jpg)
文章图片
451. 根据字符出现频率排序 力扣链接
给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串 。如果有多个答案，返回其中任何一个。
示例 1:
输入: s = “tree”
输出: “eert”
解释: 'e’出现两次，'r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。
示例 2:
输入: s = “cccaaa”
输出: “cccaaa”
解释: 'c’和’a’都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:
输入: s = “Aabb”
输出: “bbAa”
解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意’A’和’a’被认为是两种不同的字符。
提示:
1 <= s.length <= 5 * 105
s 由大小写英文字母和数字组成
解法1：优先队列（堆排序）
struct cmp{
bool operator()(const pair& a,const pair& b){
return a.second < b.second;
}
};
class Solution {
public:
string frequencySort(string s) {
unordered_map umap;
//出现次数-下标
int n = s.size();
for(char c:s){
umap[c]++;
}
priority_queue,vector>,cmp> pq;
for(auto it = umap.begin();
it!=umap.end();
it++){
pq.push({it->first,it->second});
}
string res = "";
while(pq.size()){
auto [ch,cnt] = pq.top();
pq.pop();
for(int i = 0;
i 篇)](http://img.readke.com/220601/1051453164-28.jpg)
文章图片
推荐阅读
- IO流|IO流原理及流的分类FileInputStream类和FileOutputStream类基本介绍
- 数组-一文搞定前缀和数组
- 职场|BI项目经理入门指南（用最详细的图解，带你落地企业自助分析项目）
- 职场|沦为“取数工具”的那些日子，我懂得了这些道理
- 报表开发|如何通过分析数据，从而找到最能赚钱的明星产品（--最详细图解波士顿举证模型篇）
- JAVA递归算法
- 实现深层对象属性访问
- #yyds干货盘点#看动画学算法之:二叉搜索树BST
- 机器学习|机器学习之入门但门被焊死 分类KNN算法实现