- 前言
- 一、练习题目
- 二、思路及题解
- 1. LC933-最近的请求次数
- 2. LC2073-买票需要的时间
- 3. LC641-设计循环双端队列
- 4. LC1670-设计前中后队列
- 总结
前言
欢迎大家积极在评论区留言一起讨论交流，知无不言，言无不尽，共同进步。本文是 队列 专题，更多其他专题内容详见《LeetCode每月集训系列》
一、练习题目
| 题目链接 | 难度 | 备注 |
|---|---|---|
| 933. 最近的请求次数 | ★☆☆☆☆ | |
| 2073. 买票需要的时间 | ★★☆☆☆ | |
| 641. 设计循环双端队列 | ★★★☆☆ | |
| 1670. 设计前中后队列 | ★★★☆☆ |
方法一：直接使用队列
（1）由于时间是单调递增的，直接使用队列即可；
（2）只保留时间差值在 3000 以内的请求。
代码如下：
class RecentCounter {
queue que;
public:
RecentCounter() {}
int ping(int t) {
que.push(t);
while (que.front() < t - 3000) {
que.pop();
}
return que.size();
}
};
方法二：使用数组模拟
代码如下：
class RecentCounter {
int front, rear;
int data[10001];
public:
RecentCounter() {
front = 0;
rear = -1;
}
int ping(int t) {
data[++rear] = t;
while (rear - front + 1 > 0 && data[front] < t - 3000) {
front ++;
}
return rear - front + 1;
}
};
2. LC2073-买票需要的时间
方法一：模拟
（1）定义一个 map 储存买票人待买的票数，然后直接模拟队列即可。
代码如下：
class Solution {
public:
int timeRequiredToBuy(vector& tickets, int k) {
int ans = 0;
queue que;
unordered_map mp;
for (int i = 0; i < tickets.size(); ++i) {
mp[i] = tickets[i];
que.push(i);
}
while (mp[k] > 0) {
int people = que.front();
que.pop();
mp[people]--;
if (mp[people] > 0) que.push(people);
++ans;
}
return ans;
}
};
方法二 ：思考
（1）遍历计算每个人买票所需时间，在 k 买到所需要的票前，其后面的人一定总比他少买到一张。
代码如下：
class Solution {
public:
int timeRequiredToBuy(vector& tickets, int k) {
int res = 0;
for(int i = 0; i < tickets.size(); ++i) {
// 遍历计算每个人所需时间
if(i <= k) {
res += min(tickets[i], tickets[k]); // 排在k前面需要购买的票数
}else {
res += min(tickets[i], tickets[k] - 1); // 排在k后面需要购买的票数
}
}
return res;
}
};
3. LC641-设计循环双端队列
方法一：数组模拟
（1）初始化时，front 和 rear 都指向第一个有效位置 0 处；
（2）为了避免队列为空和队列为满两种情况的判别条件冲突，而引入了一个多余的位置；
（3）由于队列会有循环的情况出现，所以需要注意数组下标可能会越界，这里通过取模运算来防止越界现象的发生。
代码如下：
class MyCircularDeque {
private:
int front, rear, cap;
vector arr;
public:
MyCircularDeque(int k) {
cap = k + 1;
arr.resize(cap, 0);
front = 0, rear = 0;
}
bool insertFront(int value) {
if (isFull()) {
return false;
}
front = (front - 1 + cap) % cap; // 相当于环状，防止过界
arr[front] = value;
return true;
}
bool insertLast(int value) {
if (isFull()) {
return false;
}
arr[rear] = value;
rear = (rear + 1) % cap;
return true;
}
bool deleteFront() {
if (isEmpty()) {
return false;
}
front = (front + 1) % cap;
return true;
}
bool deleteLast() {
if (isEmpty()) {
return false;
}
rear = (rear - 1 + cap) % cap;
return true;
}
int getFront() {
if (isEmpty()) {
return -1;
}
return arr[front];
}
int getRear() {
if (isEmpty()) {
return -1;
}
return arr[(rear - 1 + cap) % cap]; // 防止为0时数组越界
}
bool isEmpty() {
return front == rear;
}
bool isFull() {
return (rear + 1) % cap == front;
}
};
4. LC1670-设计前中后队列
方法一：使用动态数组进行模拟
（1）与LC641思路类似，只需特别注意中间位置的取值即可。
（2）以后会尝试使用链表来做。
代码如下：
class FrontMiddleBackQueue {
private:
vector arr;
public:
FrontMiddleBackQueue() {
}
void pushFront(int val) {
arr.insert(arr.begin(), val);
}
void pushMiddle(int val) {
int pos = arr.size() / 2;
arr.insert(arr.begin() + pos, val);
}
void pushBack(int val) {
arr.push_back(val);
}
int popFront() {
if (arr.empty()) {
return -1;
}
int ret = arr[0];
arr.erase(arr.begin());
return ret;
}
int popMiddle() {
if (arr.empty()) {
return -1;
}
int pos = (arr.size() - 1) / 2;
int ret = arr[pos];
arr.erase(arr.begin() + pos);
return ret;
}
int popBack() {
if (arr.empty()) {
return -1;
}
int ret = arr.back();
arr.pop_back();
return ret;
}
};
总结
题目难不要怕，只要每个月的每一天都坚持刷题学习，总有一天会熟练掌握的。欢迎加入【知识星球｜英雄算法联盟】与我们一同早起刷刷刷⛽️
