怎样去各大网站做淘宝推广,阿里巴巴做网站需要多少钱,wordpress扫码阅读,ppt模板免费下载第一ppt优先级队列 #includequeue --队列 和 优先级队列的头文件 优先级队列#xff1a; 堆结构 最大堆 和 最小堆 相关函数#xff1a; front() 获取第一个元素 back() 获取最后一个元素 push() 放入元素 pop() 弹出第一个元素 size() 计算队列中元素…优先级队列 #includequeue --队列 和 优先级队列的头文件 优先级队列 堆结构 最大堆 和 最小堆 相关函数 front() 获取第一个元素 back() 获取最后一个元素 push() 放入元素 pop() 弹出第一个元素 size() 计算队列中元素的个数 empty() 判断是否为空 为空返回true 不为空返回false 石头的重量
1046. 最后一块石头的重量https://leetcode.cn/problems/last-stone-weight/ 有一堆石头每块石头的重量都是正整数。
每一回合从中选出两块 最重的 石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且 x y。那么粉碎的可能结果如下
如果 x y那么两块石头都会被完全粉碎如果 x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为 y-x。
最后最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下就返回 0。 思路 利用优先级队列默认最大堆结构将数组中元素升序排一下然后每次取出堆顶元素和堆顶下一位用两个变量接收利用top和pop函数。 class Solution {
public:int lastStoneWeight(vectorint stones) {priority_queueint q;for(int i0; istones.size(); i){q.push(stones[i]);}while(q.size()1){int xq.top();q.pop();int yq.top();q.pop();if(x ! y) {q.push(x-y);}}if(q.empty()) {return 0;} else {return q.top();}}
};分发饼干
455. 分发饼干https://leetcode.cn/problems/assign-cookies/ 假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。
对每个孩子 i都有一个胃口值 g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j都有一个尺寸 s[j] 。如果 s[j] g[i]我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子并输出这个最大数值。4 与上题思路相同 class Solution {
public:int findContentChildren(vectorint g, vectorint s) {priority_queueint g_que,s_que;int res0;for(int i0;ig.size();i){g_que.push(g[i]);}for(int i0;is.size();i){s_que.push(s[i]);}while(!s_que.empty()!g_que.empty())//当同时存在时{if(g_que.top() s_que.top()){res;g_que.pop();s_que.pop();}elseg_que.pop();}return res;}
};面试题最小k个数
面试题 17.14. 最小K个数https://leetcode.cn/problems/smallest-k-lcci/
提示
设计一个算法找出数组中最小的k个数。以任意顺序返回这k个数均可。
示例
输入 arr [1,3,5,7,2,4,6,8], k 4
输出 [1,2,3,4] 思路 创建一个队列队列默认最大堆结构将前k个始终维护成最大堆结构k~arr.size()-1中每个元素始终与栈顶元素作比较最终队列即为所求。 如果用最小堆的话当数据量非常大时时间复杂度太高了。 class Solution {
public:vectorint smallestK(vectorint arr, int k) {if(k0||arr.size()0)return {};priority_queueint que;vectorintres;for(int i0;ik;i)que.push(arr[i]);for(int ik;iarr.size();i){if(arr[i]que.top()){que.pop();que.push(arr[i]);}}while(!que.empty()){res.push_back(que.top());que.pop();}return res;}
};队列
周末舞会 1332【例2-1】周末舞会 【题目描述】 假设在周末舞会上男士们和女士们进入舞厅时各自排成一队。跳舞开始时依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序模拟上述舞伴配对问题。 【输入】 第一行两队的人数; 第二行舞曲的数目。 【输出】 配对情况。 思路 这段代码通过两个队列分别表示舞会上的男士和女士队伍循环读取舞曲数目来模拟配对跳舞的过程。对于每首舞曲从男女队列的队首分别取出一个人配对为舞伴然后将这对舞伴放回队列的末尾以便参与下一轮配对直至所有舞曲播放完毕。这样通过队列的先进先出特性实现了一个简单的舞伴轮换配对模拟。 #includeiostream
#includequeue//栈的头文件
using namespace std;int main()
{int m, n, k;cin m n k;queueints1;queueints2;for (int j 1; j m; j){s1.push(j);}for (int c 1; c n; c){s2.push(c);}for (int i 1; i k; i){cout s1.front() s2.front() endl;int x s1.front(), y s2.front();s1.pop(); s2.pop();s1.push(x), s2.push(y);}return 0;
} 面试题--用两个队列实现栈
225. 用队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/
请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。
实现 MyStack 类
void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。 思路 这段代码通过两个队列q1和q2来模拟一个后入先出LIFO的栈结构。当新元素被加入push操作时它直接进入q1。为了模拟栈的pop操作代码将q1中的元素除了最后一个加入的元素之外都转移到q2中这样q1中剩下的最后一个元素就是需要被pop的元素。在这个元素被移除后q2的内容回到q1实现了后入先出的逻辑。top操作简单地返回q1的最后一个元素而empty操作检查q1是否为空从而判断栈是否为空。 class MyStack {
public:queueintq1;queueintq2;void push(int x) {q1.push(x);}int pop() {while(q1.size()1)//队列中只剩下一个元素{q2.push(q1.front());q1.pop();}int xq1.front();//记录最后一个元素 即返回值q1.pop();q1q2;while(!q2.empty())//清空q2{q2.pop();}return x;}int top() {return q1.back();}bool empty() {return q1.empty();}
}; 面试题--用两个栈实现队列
232. 用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty
实现 MyQueue 类
void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false 思路 这段代码使用两个栈s1和s2来实现一个队列。当元素被推入队列时它被压入s1。要执行pop或peek操作时如果s2为空s1的所有元素逆序转移到s2中使得s1的底部元素移动到s2的顶部即队列的前端。这样从s2中弹出或查看顶部元素就可以模拟队列的pop和peek操作。empty操作通过检查两个栈是否都为空来判断队列是否为空实现了一个先入先出的队列行为。 class MyQueue {
public:
/*先将栈中元素除了最后一个取出*/
stackints1;
stackints2;void push(int x) {s1.push(x);}int pop() {if(s2.empty())//s2不为空的话直接删除为空将s1中元素全部放入s2{while(!s1.empty()){s2.push(s1.top());s1.pop();}}int xs2.top();s2.pop();return x;}int peek() {if(s2.empty())//s2不为空的话直接删除为空将s1中元素全部放入s2{while(!s1.empty()){s2.push(s1.top());s1.pop();}}int xs2.top();return x;}bool empty() {return s1.empty()s2.empty();//都为空才为空}
};
