| comments | difficulty | edit_url | tags | |||
|---|---|---|---|---|---|---|
true |
简单 |
|
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：
RecentCounter()初始化计数器，请求数为 0 。int ping(int t)在时间t添加一个新请求，其中t表示以毫秒为单位的某个时间，并返回过去3000毫秒内发生的所有请求数（包括新请求）。确切地说，返回在[t-3000, t]内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
示例 1：
输入： ["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]] 输出： [null, 1, 2, 3, 3] 解释： RecentCounter recentCounter = new RecentCounter(); recentCounter.ping(1); // requests = [1]，范围是 [-2999,1]，返回 1 recentCounter.ping(100); // requests = [1, 100]，范围是 [-2900,100]，返回 2 recentCounter.ping(3001); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3 recentCounter.ping(3002); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3
提示：
1 <= t <= 109- 保证每次对
ping调用所使用的t值都 严格递增 - 至多调用
ping方法104次
由题得知，t 是严格递增的，当一个元素不满足 [t - 3000, t] 条件时，在后续的请求当中，它也不可能满足。
对此，需要将其从记录容器中移除，减少无意义的比较。
可以使用队列。每次将 t 进入队尾，同时从队头开始，依次移除小于 t - 3000 的元素。然后返回队列的大小（q.size()）即可。
class RecentCounter:
def __init__(self):
self.q = deque()
def ping(self, t: int) -> int:
self.q.append(t)
while self.q[0] < t - 3000:
self.q.popleft()
return len(self.q)
# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)class RecentCounter {
private int[] s = new int[10010];
private int idx;
public RecentCounter() {
}
public int ping(int t) {
s[idx++] = t;
return idx - search(t - 3000);
}
private int search(int x) {
int left = 0, right = idx;
while (left < right) {
int mid = (left + right) >> 1;
if (s[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
/**
* Your RecentCounter object will be instantiated and called as such:
* RecentCounter obj = new RecentCounter();
* int param_1 = obj.ping(t);
*/class RecentCounter {
public:
queue<int> q;
RecentCounter() {
}
int ping(int t) {
q.push(t);
while (q.front() < t - 3000) q.pop();
return q.size();
}
};
/**
* Your RecentCounter object will be instantiated and called as such:
* RecentCounter* obj = new RecentCounter();
* int param_1 = obj->ping(t);
*/type RecentCounter struct {
q []int
}
func Constructor() RecentCounter {
return RecentCounter{[]int{}}
}
func (this *RecentCounter) Ping(t int) int {
this.q = append(this.q, t)
for this.q[0] < t-3000 {
this.q = this.q[1:]
}
return len(this.q)
}
/**
* Your RecentCounter object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Ping(t);
*/class RecentCounter {
private queue: number[];
constructor() {
this.queue = [];
}
ping(t: number): number {
this.queue.push(t);
while (this.queue[0] < t - 3000) {
this.queue.shift();
}
return this.queue.length;
}
}
/**
* Your RecentCounter object will be instantiated and called as such:
* var obj = new RecentCounter()
* var param_1 = obj.ping(t)
*/use std::collections::VecDeque;
struct RecentCounter {
queue: VecDeque<i32>,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl RecentCounter {
fn new() -> Self {
Self {
queue: VecDeque::new(),
}
}
fn ping(&mut self, t: i32) -> i32 {
self.queue.push_back(t);
while let Some(&v) = self.queue.front() {
if v >= t - 3000 {
break;
}
self.queue.pop_front();
}
self.queue.len() as i32
}
}var RecentCounter = function () {
this.q = [];
};
/**
* @param {number} t
* @return {number}
*/
RecentCounter.prototype.ping = function (t) {
this.q.push(t);
while (this.q[0] < t - 3000) {
this.q.shift();
}
return this.q.length;
};
/**
* Your RecentCounter object will be instantiated and called as such:
* var obj = new RecentCounter()
* var param_1 = obj.ping(t)
*/public class RecentCounter {
private Queue<int> q = new Queue<int>();
public RecentCounter() {
}
public int Ping(int t) {
q.Enqueue(t);
while (q.Peek() < t - 3000)
{
q.Dequeue();
}
return q.Count;
}
}
/**
* Your RecentCounter object will be instantiated and called as such:
* RecentCounter obj = new RecentCounter();
* int param_1 = obj.Ping(t);
*/t 严格单调递增，非常适合用二分查找来定位 [t-3000, t] 的左右边界。
class RecentCounter:
def __init__(self):
self.s = []
def ping(self, t: int) -> int:
self.s.append(t)
return len(self.s) - bisect_left(self.s, t - 3000)
# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)class RecentCounter {
public:
vector<int> s;
RecentCounter() {
}
int ping(int t) {
s.push_back(t);
return s.size() - (lower_bound(s.begin(), s.end(), t - 3000) - s.begin());
}
};
/**
* Your RecentCounter object will be instantiated and called as such:
* RecentCounter* obj = new RecentCounter();
* int param_1 = obj->ping(t);
*/type RecentCounter struct {
s []int
}
func Constructor() RecentCounter {
return RecentCounter{[]int{}}
}
func (this *RecentCounter) Ping(t int) int {
this.s = append(this.s, t)
search := func(x int) int {
left, right := 0, len(this.s)
for left < right {
mid := (left + right) >> 1
if this.s[mid] >= x {
right = mid
} else {
left = mid + 1
}
}
return left
}
return len(this.s) - search(t-3000)
}
/**
* Your RecentCounter object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Ping(t);
*/