其他系列文章导航
Java基础合集
数据结构与算法合集设计模式合集
多线程合集
分布式合集
ES合集
文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1 队列问题一般解法
2.2 方法一：队列
三、代码
3.1 方法一：队列
四、复杂度分析
4.1 方法一：队列
前言
这是力扣的 933 题，难度为简单，解题方案有很多种，本文讲解我认为最奇妙的一种。
慢慢开始队列的模块了，这道题是一道非常好的队列的例题，很有代表性。
一、题目描述
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：
-
RecentCounter()初始化计数器，请求数为 0 。 -
int ping(int t)在时间t添加一个新请求，其中t表示以毫秒为单位的某个时间，并返回过去3000毫秒内发生的所有请求数（包括新请求）。确切地说，返回在[t-3000, t]内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
示例 1：
输入： ["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]] 输出： [null, 1, 2, 3, 3] 解释： RecentCounter recentCounter = new RecentCounter(); recentCounter.ping(1); // requests = [1]，范围是 [-2999,1]，返回 1 recentCounter.ping(100); // requests = [1, 100]，范围是 [-2900,100]，返回 2 recentCounter.ping(3001); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3 recentCounter.ping(3002); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3
提示：
1 <= t <= 109- 保证每次对
ping调用所使用的t值都 严格递增 - 至多调用
ping方法104次
二、题解
2.1 队列问题一般解法
队列是一种特殊的线性表，只允许在表的前端进行删除操作，在表的后端进行插入操作。以下是队列问题的基本算法：
- 初始化队列：创建一个空队列，并设置一个队头指针和一个队尾指针，分别指向队列的开头和结尾。
- 入队操作：将一个元素插入到队列的尾部。具体操作是先将队尾指针向后移动一位，然后将新元素插入到队尾指针所指的位置。
- 出队操作：从队列的头部删除一个元素。具体操作是先将队头指针向后移动一位，然后返回队头指针所指向的元素。如果队列为空，则无法进行出队操作。
- 获取队头元素：返回队头指针所指向的元素，但不删除该元素。如果队列为空，则无法获取队头元素。
- 判断队列是否为空：如果队头指针和队尾指针指向同一位置，则队列为空。
以上是队列问题的基本算法，可以用于解决各种相关问题，如生产者消费者问题、约瑟夫环问题等。
2.2 方法一：队列
思路与算法：
由于每次调用 ping 方法时，请求时间 t 是严格单调递增的，因此按照调用顺序存储请求时间可以得到请求时间的严格递增序列。每次调用 ping 方法要求返回过去 3000 毫秒内发生的所有请求数，因此可以将请求时间序列中的距离请求时间超过 3000 毫秒的请求删除，然后计算请求时间序列中的请求数，即为过去 3000 毫秒内发生的所有请求数。
由于最早发生的请求会最先被删除，因此请求时间序列满足先进先出的特点，可以使用队列实现请求时间序列，在构造方法中初始化队列。
对于 ping 方法，首先将过时的请求出队列，如果队列不为空且队首元素距离当前请求时间超过 3000 毫秒，则将队首元素出队列，重复该操作直到队列变为空或者队首元素距离当前请求时间不超过 3000 毫秒。然后将当前请求时间入队列，此时队列内的元素个数即为过去 3000 毫秒内发生的所有请求数，返回队列内的元素个数即可。
三、代码
3.1 方法一：队列
Java版本：
class RecentCounter {
static final int RANGE = 3000;
Queue<Integer> queue;
public RecentCounter() {
queue=new ArrayDeque<>();
}
public int ping(int t) {
while(!queue.isEmpty()&&t-queue.peek()>RANGE){
queue.poll();
}
queue.add(t);
return queue.size();
}
}C++版本：
#include <queue>
using namespace std;
class RecentCounter {
private:
static const int RANGE = 3000;
queue<int> q;
public:
RecentCounter() {}
int ping(int t) {
while (!q.empty() && t - q.front() > RANGE) {
q.pop();
}
q.push(t);
return q.size();
}
};
Python版本：文章来源：https://www.toymoban.com/news/detail-790060.html
from collections import deque
class RecentCounter:
RANGE = 3000
def __init__(self):
self.q = deque()
def ping(self, t: int) -> int:
while self.q and t - self.q[0] > self.RANGE:
self.q.popleft()
self.q.append(t)
return len(self.q)
Go版本：文章来源地址https://www.toymoban.com/news/detail-790060.html
package main
import "container/list"
type RecentCounter struct {
rangeVal int
q *list.List
}
func Constructor() RecentCounter {
return RecentCounter{rangeVal: 3000, q: list.New()}
}
func (this *RecentCounter) Ping(t int) int {
for this.q.Len() > 0 && t-this.q.Front().Value.(int) > this.rangeVal {
this.q.Remove(this.q.Front())
}
this.q.PushBack(t)
return this.q.Len()
}
四、复杂度分析
4.1 方法一：队列
- 时间复杂度 ：构造方法的时间复杂度是 O(1)，方法 ping 的均摊时间复杂度是 O(1)。每个元素最多入队和出队各一次，因此方法 ping 的均摊时间复杂度是 O(1)。
- 空间复杂度：O(n)，其中 n 是请求次数。空间复杂度主要取决于队列空间，队列内存储最近 3000毫秒的请求，空间复杂度是 O(n)。
到了这里，关于【数据结构和算法】最近的请求次数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
