剑指 Offer II 042. 最近请求次数：
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请实现 RecentCounter 类：
RecentCounter()初始化计数器，请求数为 0 。int ping(int t)在时间t添加一个新请求，其中t表示以毫秒为单位的某个时间，并返回过去3000毫秒内发生的所有请求数（包括新请求）。确切地说，返回在[t-3000, t]内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
样例 1
输入：
inputs = ["RecentCounter", "ping", "ping", "ping", "ping"]
inputs = [[], [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 次
分析
- 二当家的觉得这道算法题相对来说还是自由度比较高的。
- 由于有提示中第二条的规定，每次 ping 调用所使用的t值都严格递增，所以可以使用队列，如果已经和最新的t相差超过3000，就可以清除了，按顺序出队列即可，队列中元素最多也只有3000个，也就是每次 ping 最差就是不超过3000次出队列，而队列留下的值恰好就是 ping 方法返回值。
- 由于有提示中第三条的规定，ping 的最高调用次数已经知道，如果使用可随机访问的数据结构，还可以使用二分查找，时间复杂度上会比按顺序出队列好一些，但是如果 ping 的次数是不一定的，还是用队列好。
题解
java
没有使用自带的二分查找，因为查不到是负数，不是我们想要的值。
class RecentCounter {
private int[] q;
private int head;
private int tail;
public RecentCounter() {
q = new int[10000];
}
public int ping(int t) {
head = binarySearch(q, head, tail, t - 3000);
q[tail++] = t;
return tail - head;
}
private int binarySearch(int[] a, int fromIndex, int toIndex, int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return low; // key not found.
}
}c
typedef struct {
int *q;
int head;
int tail;
} RecentCounter;
RecentCounter *recentCounterCreate() {
RecentCounter *recentCounter = (RecentCounter *) malloc(sizeof(RecentCounter));
recentCounter->q = (int *) malloc(sizeof(int) * 10000);
recentCounter->head = 0;
recentCounter->tail = 0;
return recentCounter;
}
int binarySearch(int *a, int fromIndex, int toIndex, int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return low; // key not found.
}
int recentCounterPing(RecentCounter *obj, int t) {
obj->head = binarySearch(obj->q, obj->head, obj->tail, t - 3000);
obj->q[obj->tail++] = t;
return obj->tail - obj->head;
}
void recentCounterFree(RecentCounter *obj) {
free(obj->q);
free(obj);
}c++
class RecentCounter {
private:
vector<int> q;
int head;
public:
RecentCounter() {
head = 0;
}
int binarySearch(vector<int>& a, int fromIndex, int toIndex, int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return low; // key not found.
}
int ping(int t) {
head = binarySearch(q, head, q.size(), t - 3000);
q.push_back(t);
return q.size() - head;
}
};python
python这次是最简洁的了，主要就是有可以直接用的二分查找。
class RecentCounter:
def __init__(self):
self.q = []
self.head = 0
def ping(self, t: int) -> int:
self.head = bisect.bisect_left(self.q, t - 3000, self.head)
self.q.append(t)
return len(self.q) - self.headgo
type RecentCounter struct {
q []int
head int
}
func Constructor() RecentCounter {
return RecentCounter{[]int{}, 0}
}
func (this *RecentCounter) Ping(t int) int {
this.head = binarySearch(this.q, this.head, len(this.q), t - 3000)
this.q = append(this.q, t)
return len(this.q) - this.head
}
func binarySearch(a []int, fromIndex int, toIndex int, key int) int {
low := fromIndex
high := toIndex - 1
for low <= high {
mid := (low + high) >> 1
midVal := a[mid]
if midVal < key {
low = mid + 1
} else if midVal > key {
high = mid - 1
} else {
return mid // key found
}
}
return low // key not found.
}rust
struct RecentCounter {
q: Vec<i32>,
head: 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 {
RecentCounter { q: Vec::new(), head: 0 }
}
fn ping(&mut self, t: i32) -> i32 {
self.head = RecentCounter::binarySearch(&self.q, self.head, self.q.len() as i32, t - 3000);
self.q.push(t);
self.q.len() as i32 - self.head
}
fn binarySearch(a: &Vec<i32>, fromIndex: i32, toIndex: i32, key: i32) -> i32 {
let mut low = fromIndex;
let mut high = toIndex - 1;
while low <= high {
let mid = (low + high) >> 1;
let midVal = a[mid as usize];
if midVal < key {
low = mid + 1;
} else if midVal > key {
high = mid - 1;
} else {
return mid; // key found
}
}
return low; // key not found.
}
}
原题传送门：https://leetcode-cn.com/problems/H8086Q/
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~
