# [LeetCode] 362. Design Hit Counter 设计点击计数器

2021年09月15日 阅读数：1

Design a hit counter which counts the number of hits received in the past 5 minutes.html

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.java

It is possible that several hits arrive roughly at the same time.python

Example:app

```HitCounter counter = new HitCounter();

// hit at timestamp 1.
counter.hit(1);

// hit at timestamp 2.
counter.hit(2);

// hit at timestamp 3.
counter.hit(3);

// get hits at timestamp 4, should return 3.
counter.getHits(4);

// hit at timestamp 300.
counter.hit(300);

// get hits at timestamp 300, should return 4.
counter.getHits(300);

// get hits at timestamp 301, should return 3.
counter.getHits(301);
```

What if the number of hits per second could be very large? Does your design scale?post

Java:设计

```public class HitCounter {
private ArrayDeque<Integer> queue;

/** Initialize your data structure here. */
public HitCounter() {
queue = new ArrayDeque<Integer>();
}

/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
queue.offer(timestamp);
}

/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
int startTime = timestamp - 300;
while(!queue.isEmpty() && queue.peek() <= startTime) {
queue.poll();
}
return queue.size();
}
}

/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/　　```

Java：htm

```public class HitCounter {

private Hit start = new Hit(0);
private Hit tail = start;
private int count = 0;

/** Initialize your data structure here. */
public HitCounter() {

}

/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
if (tail.timestamp == timestamp) {
tail.count ++;
count ++;
} else {
tail.next = new Hit(timestamp);
tail = tail.next;
count ++;
}
getHits(timestamp);
}

/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
while (start.next != null && timestamp - start.next.timestamp >= 300) {
count -= start.next.count;
start.next = start.next.next;
}
if (start.next == null) tail = start;
return count;
}
}

class Hit {
int timestamp;
int count;
Hit next;
Hit(int timestamp) {
this.timestamp = timestamp;
this.count = 1;
}
}

/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/
```

Python:blog

```# Time:  O(1), amortized
# Space: O(k), k is the count of seconds.

from collections import deque

class HitCounter(object):

def __init__(self):
"""
"""
self.__k = 300
self.__dq = deque()
self.__count = 0

def hit(self, timestamp):
"""
Record a hit.
@param timestamp - The current timestamp (in seconds granularity).
:type timestamp: int
:rtype: void
"""
self.getHits(timestamp)
if self.__dq and self.__dq[-1][0] == timestamp:
self.__dq[-1][1] += 1
else:
self.__dq.append([timestamp, 1])
self.__count += 1

def getHits(self, timestamp):
"""
Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity).
:type timestamp: int
:rtype: int
"""
while self.__dq and self.__dq[0][0] <= timestamp - self.__k:
self.__count -= self.__dq.popleft()[1]
return self.__count

# Your HitCounter object will be instantiated and called as such:
# obj = HitCounter()
# obj.hit(timestamp)
# param_2 = obj.getHits(timestamp)
```

C++:

```// Time:  O(1), amortized
// Space: O(k), k is the count of seconds.

class HitCounter {
public:
/** Initialize your data structure here. */
HitCounter() : count_(0) {

}

/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
void hit(int timestamp) {
getHits(timestamp);
if (!dq_.empty() && dq_.back().first == timestamp) {
++dq_.back().second;
} else {
dq_.emplace_back(timestamp, 1);
}
++count_;
}

/** 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() && dq_.front().first <= timestamp - k_) {
count_ -= dq_.front().second;
dq_.pop_front();
}
return count_;
}

private:
const int k_ = 300;
int count_;
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);
*/
```

C++:

```class HitCounter {
public:
/** Initialize your data structure here. */
HitCounter() {}

/** 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;
};
```

C++:

```class HitCounter {
public:
/** Initialize your data structure here. */
HitCounter() {}

/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
void hit(int timestamp) {
v.push_back(timestamp);
}

/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
int getHits(int timestamp) {
int i, j;
for (i = 0; i < v.size(); ++i) {
if (v[i] > timestamp - 300) {
break;
}
}
return v.size() - i;
}

private:
vector<int> v;
};
```

C++:

```class HitCounter {
public:
/** Initialize your data structure here. */
HitCounter() {
times.resize(300);
hits.resize(300);
}

/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
void hit(int timestamp) {
int idx = timestamp % 300;
if (times[idx] != timestamp) {
times[idx] = timestamp;
hits[idx] = 1;
} else {
++hits[idx];
}
}

/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
int getHits(int timestamp) {
int res = 0;
for (int i = 0; i < 300; ++i) {
if (timestamp - times[i] < 300) {
res += hits[i];
}
}
return res;
}

private:
vector<int> times, hits;
};
```

[LeetCode] 359. Logger Rate Limiter 记录速率限制器