C ++中的设计命中计数器
假设我们要设计一个点击计数器,计算过去5分钟内收到的点击次数。在第二个单元中将有一个函数并且接受timestamp参数,并且我们可以假定正在按时间顺序对系统进行调用(因此,时间戳是单调递增的)。我们还假定最早的时间戳记从1开始。
几个匹配可能会大致同时到达。
因此,我们将调用hit()
函数hit和getHits()
function以获取命中计数。
为了解决这个问题,我们将遵循以下步骤-
定义大小为300的数组时间
定义大小为300的数组匹配
定义一个函数hit()
,这将需要时间戳记,
idx:=时间戳mod300
如果time[idx]不等于时间戳,则-
time[idx]:=时间戳
hits[idx]:=1
除此以外
hits[idx]:=hits[idx]+1
定义一个函数getHits()
,这将需要时间戳记,
ret:=0
对于初始化i:=0,当i<300时,更新(将i增加1),执行-
ret:=ret+hits[i]
如果时间戳-time[i]<300,则-
返回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