933.最近的请求次数

一、题目描述

写一个 RecentCounter 类来计算最近的请求。

它只有一个方法:ping(int t),其中 t 代表以毫秒为单位的某个时间。

返回从 3000 毫秒前到现在的 ping 数。

任何处于 [t - 3000, t] 时间范围之内的 ping 都将会被计算在内,包括当前(指 t 时刻)的 ping

保证每次对 ping 的调用都使用比之前更大的 t 值。

示例:

1
2
输入:inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
输出:[null,1,2,3,3]

提示:

  1. 每个测试用例最多调用 10000ping
  2. 每个测试用例会使用严格递增的 t 值来调用 ping
  3. 每次调用 ping 都有 1 <= t <= 10^9

二、题解

1.算法描述

  • 队列

2.个人分析

  1. 扫描数组,逐一进队
  2. 当队头元素 < 队尾元素时,出队
  3. 返回当前队伍长度

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#define maxSize 100000
typedef struct
{
int *queue;
int front;
int rear;

} RecentCounter;

RecentCounter *recentCounterCreate()
{
RecentCounter *rt = (RecentCounter *)malloc(sizeof(RecentCounter));
rt->queue = (int *)malloc(maxSize * sizeof(int));
memset(rt->queue, -1, maxSize * sizeof(int));
rt->front = 0;
rt->rear = 0;
return rt;
}

int recentCounterPing(RecentCounter *obj, int t)
{
obj->rear = (obj->rear + 1) % maxSize;
obj->queue[obj->rear] = t;
while (obj->queue[obj->front + 1] < t - 3000)
{
obj->front = (obj->front + 1) % maxSize;
}
return obj->rear - obj->front;
}
void recentCounterFree(RecentCounter *obj)
{
free(obj->queue);
free(obj);
}

/**
* Your RecentCounter struct will be instantiated and called as such:
* RecentCounter* obj = recentCounterCreate();
* int param_1 = recentCounterPing(obj, t);

* recentCounterFree(obj);
*/