933.最近的请求次数

发表于 | 分类于
字数统计: 373 | 阅读时长 ≈ 1

一、题目描述

写一个 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. 每个测试用例最多调用 10000 次 ping。
  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);
*/