持续更新中~
本篇为简单题
📍933. 最近的请求次数
问题描述
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：
- RecentCounter() 初始化计数器，请求数为 0 。
- int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
- 保证 每次对 ping 的调用都使用比之前更大的 t 值。
我的代码如下：
#include <queue> class RecentCounter { public: RecentCounter() { } int ping(int t) { qt.push(t); while(qt.front()<t-3000) { qt.pop(); } return qt.size(); } private: queue<int> qt; };
解题方案
使用了队列（queue）数据结构来解决问题。在 ping 方法中，将新请求的时间 t 入队，并使用 while 循环将队列头部过期的请求（在 [t-3000, t] 之外的请求）出队，然后返回队列的大小（即最近 3000 毫秒内的请求数）。由于队列是先进先出（FIFO）的数据结构，所以能够保证只保留最近的请求。
📍LCR 041. 数据流中的移动平均值
问题描述
给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。
实现 MovingAverage 类：
MovingAverage(int size) 用窗口大小 size 初始化对象。
double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。
解题方案
为了计算滑动窗口中的平均值，我们需要维护一个队列，其中存储了最近 size 个值。当添加一个新的值时，我们需要从队列的前端移除一个值，以保证队列的大小始终为 size。同时，我们还需要维护一个变量来跟踪队列的总和，以便我们可以计算平均值。
在 next 函数中，如果队列的大小小于 size，我们只需将新的值添加到队列中即可。否则，我们需要从队列的前端移除一个值，然后将新的值添加到队列的尾部。同时，我们还需要更新总和变量以包含新的值。最后，我们返回总和除以队列的大小，得到滑动窗口的平均值。
class MovingAverage { public: /** Initialize your data structure here. */ MovingAverage(int size) { _size = size; sum = 0; } double next(int val) { if (qt.size() < _size) { qt.push(val); } else { sum -= qt.front(); qt.pop(); qt.push(val); } sum += val; return sum * 1.0 / qt.size(); } private: int _size; int sum; queue<int> qt; };
📍1700. 无法吃午餐的学生数量
问题描述
学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：
- 如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。
- 否则，这名学生会 放弃这个三明治 并回到队列的尾部。
这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。
给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i 个三明治的类型（i = 0 是栈的顶部）， students[j] 是初始队列里第 j 名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。
解决方案
这个问题可以通过使用队列和指针来解决。首先，我们将所有的学生放入队列中。然后，我们开始处理栈顶的三明治，依次与队列中的学生比较。
- 如果队列头的学生喜欢栈顶的三明治，那么他就会拿走它并离开队列。此时，我们需要将队列的指针向前移动一位，并将计数器重置为0。
- 如果队列头的学生不喜欢栈顶的三明治，那么他就会放弃这个三明治并回到队列的尾部。此时，我们需要将队列头部的元素取出，放入队列尾部，并增加计数器。如果此时计数器的值等于队列的大小，说明所有的学生都无法吃到三明治，我们就可以提前结束循环并返回计数器的值。
- 如果栈为空，说明所有的三明治都已经处理完毕，我们就可以返回0。
这是对应的代码实现：
class Solution { public: int countStudents(vector<int>& students, vector<int>& sandwiches) { queue<int> st; for(int i=0;i<students.size();++i) { st.push(students[i]); } int point=0; int count=0; while(!st.empty()) { if(st.front()==sandwiches[point]) { st.pop(); point++; count=0; } else { int tmp=st.front(); st.pop(); st.push(tmp); count++; if(count==st.size()) { return count; } } } return 0; } };
这个解决方案的时间复杂度为O(n)，其中n是学生的数量。
📍queue的介绍和使用
👨🚀小明：“这里我们先看一下文档是怎么说的。总结就是下面几点。”
🎈queue的介绍
- ✨队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
- ✨队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
- ✨底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
- empty：检测队列是否为空
- size：返回队列中有效元素的个数
- front：返回队头元素的引用
- back：返回队尾元素的引用
- push_back：在队列尾部入队列
- pop_front：在队列头部出队列
- ✨标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。
👨🚀小明又给小星展示了一张表“它的常用函数有下面这些，每一个都是链接了文档的超链接，想了解更多就点它，后面接口说明有功能介绍”
🎈queue的常用函数
🎈queue的使用
👨🚀小明：”按照惯例，现在该做题练练手了“
🧚小星又恢复了活力，双手叉腰、鼻孔朝天道：”来吧，小小队列题“
👨🚀小明心想可不能打击他的士气，万一不学了就不好了，于是找到了这题：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
- 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
- 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false] 解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False
提示：
- 1 <= x <= 9
- 最多调用100 次 push、pop、top 和 empty
- 每次调用 pop 和 top 都保证栈不为空
接口如下：
class MyStack { public: MyStack() { } void push(int x) { } int pop() { } int top() { } bool empty() { } };
🧚小星脑袋极速运转：”用队列实现栈的功能，队列是先进先出，栈是先进后出，那么就需要两个队列，要把进入的数据倒来倒去，让后面的到前面就好了，其他的功能也是类似，把握好数据的顺序就可以了，这么简单？不愧是我，“
代码如下：
class MyStack { public: MyStack() { } void push(int x) { if(q1.empty()) { q1.push(x); while(!q2.empty()) { q1.push(q2.front()); q2.pop(); } } else { q2.push(x); while(!q1.empty()) { q2.push(q1.front()); q1.pop(); } } } int pop() { if(q1.empty()) { int res=q2.front(); q2.pop(); return res; } else { int res=q1.front(); q1.pop(); return res; } } int top() { if(q1.empty()) { int res=q2.front(); return res; } else { int res=q1.front(); return res; } } bool empty() { return q1.empty()&&q2.empty(); } private: queue<int> q1; queue<int> q2; };
过了！！！
👨🚀小明：”嗯嗯，孺子可教也，不错，看来有点天赋的“（其实都在我的掌控之中）
🧚小星：”哼哼，不看看我是谁（得意）“
🧚小星：”你尽管讲，那年我双手插兜，不知道什么是对手。“
