数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 设计点击计数器
假设我们想要设计一个点击计数器，用于统计过去 5 分钟内收到的点击次数。该计数器将包含一个函数，该函数接受以秒为单位的时间戳参数，并且我们可以假设对系统的调用是按时间顺序进行的（因此，时间戳单调递增）。我们还假设最早的时间戳从 1 开始。
可能会有多个点击几乎同时到达。
因此，我们将调用 hit() 函数进行点击计数，并调用 getHits() 函数获取点击次数。
为了解决这个问题，我们将遵循以下步骤：
定义一个大小为 300 的数组 time
定义一个大小为 300 的数组 hits
定义一个函数 hit()，它将接收时间戳作为参数：
idx := timestamp mod 300
如果 time[idx] 不等于 timestamp，则：
time[idx] := timestamp
hits[idx] := 1
否则
hits[idx] := hits[idx] + 1
定义一个函数 getHits()，它将接收时间戳作为参数：
ret := 0
从 i := 0 开始，当 i < 300 时，执行以下操作（i 增加 1）：
如果 timestamp - time[i] < 300，则：
ret := ret + hits[i]
返回 ret
示例
让我们来看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class HitCounter {
public:
vector<int< time;
vector<int< hits;
HitCounter(){
time = vector<int<(300);
hits = vector<int<(300);
}
void hit(int timestamp){
int idx = timestamp % 300;
if (time[idx] != timestamp) {
time[idx] = timestamp;
hits[idx] = 1;
}
else {
hits[idx] += 1;
}
}
int getHits(int timestamp){
int ret = 0;
for (int i = 0; i < 300; i++) {
if (timestamp - time[i] < 300) {
ret += hits[i];
}
}
return ret;
}
};
main(){
HitCounter ob;
ob.hit(1);
ob.hit(2);
ob.hit(3);
cout << (ob.getHits(4)) << endl;
ob.hit(300);
cout << (ob.getHits(300)) << endl;
cout << (ob.getHits(301));
}输入
ob.hit(1); ob.hit(2); ob.hit(3); ob.getHits(4); ob.hit(300); ob.getHits(300); ob.getHits(301);
输出
3 4 3
更新于：2020年11月19日
568 次浏览
广告