362. 敲击计数器
设计一个敲击计数器，使它可以统计在过去 5 分钟内被敲击次数。（即过去 300 秒）
您的系统应该接受一个时间戳参数 timestamp (单位为 秒 )，并且您可以假定对系统的调用是按时间顺序进行的(即 timestamp 是单调递增的)。几次撞击可能同时发生。
实现 HitCounter 类:
HitCounter() 初始化命中计数器系统。void hit(int timestamp) 记录在 timestamp ( 单位为秒 )发生的一次命中。在同一个 timestamp 中可能会出现几个点击。int getHits(int timestamp) 返回 timestamp 在过去 5 分钟内(即过去 300 秒)的命中次数。
示例 1:
输入： ["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"] [[], [1], [2], [3], [4], [300], [300], [301]] 输出： [null, null, null, null, 3, null, 4, 3] 解释： HitCounter counter = new HitCounter(); counter.hit(1);// 在时刻 1 敲击一次。 counter.hit(2);// 在时刻 2 敲击一次。 counter.hit(3);// 在时刻 3 敲击一次。 counter.getHits(4);// 在时刻 4 统计过去 5 分钟内的敲击次数, 函数返回 3 。 counter.hit(300);// 在时刻 300 敲击一次。 counter.getHits(300); // 在时刻 300 统计过去 5 分钟内的敲击次数，函数返回 4 。 counter.getHits(301); // 在时刻 301 统计过去 5 分钟内的敲击次数，函数返回 3 。
提示:
1 <= timestamp <= 2 * 109timestamp 是单调递增的）hit and getHits 最多被调用 300 次
进阶: 如果每秒的敲击次数是一个很大的数字，你的计数器可以应对吗？
相似题目
原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-10-21 20:06:07
type HitCounter struct {
m map[int]int
}
func Constructor() HitCounter {
m:=map[int]int{}
return HitCounter{m: m}
}
func (this *HitCounter) Hit(timestamp int) {
this.m[timestamp]++
}
func (this *HitCounter) GetHits(timestamp int) int {
ans:=0
l,r:=0,timestamp
if timestamp>300{
l = timestamp-300
}
for k,v:=range this.m{
if k>l && k<=r{
ans+=v
}
}
return ans
}
/**
* Your HitCounter object will be instantiated and called as such:
* obj := Constructor();
* obj.Hit(timestamp);
* param_2 := obj.GetHits(timestamp);
*/
golang 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2023-10-21 20:05:59
type HitCounter struct {
ts [300]int
cs [300]int
}
func Constructor() HitCounter {
return HitCounter{[300]int{}, [300]int{}}
}
func (this *HitCounter) Hit(timestamp int) {
i := timestamp % 300
if this.ts[i] != timestamp {
this.ts[i] = timestamp
this.cs[i] = 1
} else {
this.cs[i]++
}
}
func (this *HitCounter) GetHits(timestamp int) int {
tb := timestamp - 299
sum := 0
for i, t := range this.ts {
if t >= tb {
sum += this.cs[i]
}
}
return sum
}
/**
* Your HitCounter object will be instantiated and called as such:
* obj := Constructor();
* obj.Hit(timestamp);
* param_2 := obj.GetHits(timestamp);
*/
python3 解法, 执行用时: 40 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-21 20:05:15
class HitCounter:
# 方法1： 哈希字典
def __init__(self):
"""
Initialize your data structure here.
"""
self.time_freq = defaultdict(int)
def hit(self, timestamp: int) -> None:
"""
Record a hit.
@param timestamp - The current timestamp (in seconds granularity).
"""
self.time_freq[timestamp] += 1
def getHits(self, timestamp: int) -> int:
"""
Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity).
"""
res = 0
k = list(self.time_freq.keys())
for key in k:
if timestamp - key < 300:
res += self.time_freq[key]
else:
del self.time_freq[key]
return res
class HitCounter2:
# 方法2：数组+二分查找
def __init__(self):
"""
Initialize your data structure here.
"""
self.nums = []
def hit(self, timestamp: int) -> None:
"""
Record a hit.
@param timestamp - The current timestamp (in seconds granularity).
"""
self.nums.append(timestamp)
def getHits(self, timestamp: int) -> int:
"""
Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity).
"""
res = 0
window_L_val = timestamp - 299
window_L = bisect.bisect_left(self.nums, window_L_val)
#借助二分查找
return len(self.nums) - window_L
# Your HitCounter object will be instantiated and called as such:
# obj = HitCounter()
# obj.hit(timestamp)
# param_2 = obj.getHits(timestamp)
java 解法, 执行用时: 1 ms, 内存消耗: 39.4 MB, 提交时间: 2023-10-21 20:04:11
class HitCounter {
int[] times = new int[300];
int[] hits = new int[300];
public HitCounter() {
}
public void hit(int timestamp) {
int index = timestamp % 300;
if (times[index] != timestamp) {
times[index] = timestamp;
hits[index] = 1;
} else {
hits[index]++;
}
}
public int getHits(int timestamp) {
int res = 0;
for (int i = 0; i < 300; i++) {
if (timestamp - times[i] < 300) {
res += hits[i];
}
}
return res;
}
}
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/
java 解法, 执行用时: 1 ms, 内存消耗: 39.5 MB, 提交时间: 2023-10-21 20:03:32
class HitCounter {
/** Initialize your data structure here. */
Queue<Integer> q;
int count;
public HitCounter() {
q = new LinkedList<Integer>();
count = 0;
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
q.add(timestamp);
count++;
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
if(q.size() == 0) return 0;
int peek = q.peek();
while(peek < timestamp - 299) {
q.poll();
count--;
if(q.isEmpty()) return 0;
peek = q.peek();
}
return count;
}
}
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/
cpp 解法, 执行用时: 0 ms, 内存消耗: 7.6 MB, 提交时间: 2023-10-21 20:03:15
class HitCounter1 {
public:
/** Initialize your data structure here. */
HitCounter1() {
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
void hit(int timestamp) {
time2Cnt[timestamp]++;
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
int getHits(int timestamp) {
int count = 0;
for (int i = timestamp - 300 + 1; i <= timestamp; i++) {
count += time2Cnt[i];
}
return count;
}
private:
unordered_map<int, int> time2Cnt;
};
class HitCounter2 {
public:
/** Initialize your data structure here. */
HitCounter2() {
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
void hit(int timestamp) {
q.push(timestamp);
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
int getHits(int timestamp) {
while(!q.empty() && timestamp - q.front() >= 300) {
q.pop();
}
return q.size();
}
private:
queue<int> q;
};
class HitCounter {
public:
/** Initialize your data structure here. */
HitCounter() {
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
void hit(int timestamp) {
if (!dq.empty() && dq.back().first == timestamp) {
dq.back().second++; // could have many hits in one second
} else {
dq.push_back({timestamp, 1});
}
cnt++;
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
int getHits(int timestamp) {
while(!dq.empty() && timestamp - dq.front().first >= 300) {
cnt -= dq.front().second;
dq.pop_front();
}
return cnt;
}
private:
int cnt = 0;
deque<pair<int, int>> dq;
};
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter* obj = new HitCounter();
* obj->hit(timestamp);
* int param_2 = obj->getHits(timestamp);
*/