This is the first day of my participation in the Gwen Challenge in November. Check out the details: the last Gwen Challenge in 2021
Thank you very much for reading this article. Welcome [👍 like] [⭐ collect] [📝 comment] ~ Give up is not difficult, But insists it must be very cool ~ hope we all can be a little bit of progress every day ~ in this paper, from two headed white hat original ~ https://juejin.cn/user/2771185768884824/posts blog
1. Number of recent requests:
Write a RecentCounter class to count the most recent requests within a specific time range.
Please implement RecentCounter class:
RecentCounter()Initialize the counter with a request count of 0.int ping(int t)In the timetAdd a new request to thetRepresents a time in milliseconds and returns to the past3000The number of all requests (including new requests) that occurred in milliseconds. To be exact, return in[t-3000, t]The number of requests that occur within.
Make sure that each call to ping uses a larger t value than before.
Sample 1
Input: inputs = [" RecentCounter ", "ping", "ping", "ping", "ping"] inputs = [[], [1], [100], [3001], [3002]] output: [NULL, 1, 2, 3, 3] RecentCounter = new RecentCounter(); recentCounter.ping(1); // requests = [1], range [-2999,1], returns 1 recentCounter.ping(100); // requests = [1], range [-2999,1], returns 1 recentCounter.ping(100); // requests = [1, 100] in the range [-2900,100], returns 2 recentCounter.ping(3001); // requests = [1, 100] in the range [-2900,100], returns 2 recentCounter.ping(3001); // requests = [1, 100, 3001] in range [1,3001], return 3 recentCounter.ping(3002); // requests = [1, 100, 3001] in range [1,3001], return 3 recentCounter.ping(3002); // requests = [1, 100, 3001, 3002] in the range [2,3002], return 3Copy the codeprompt
- 1 <= t <= 109
- Ensure that the t value used for each ping call is strictly incremented
- Ping is called at most 104 times
Analysis of the
- Two master think this algorithm is relatively high degree of freedom.
- If the difference between t and the latest t exceeds 3000, the queue can be cleared. The maximum number of elements in the queue is 3000. If the difference between t and the latest T exceeds 3000, the queue can be cleared. In other words, the minimum number of pings per ping is 3000, and the value left in the queue is exactly the value returned by ping method.
- If you use a randomly accessible data structure, you can also use binary lookup. The time complexity is better than the sequential queuing, but if the number of pings is uncertain, it is better to use queuing.
Answer key
java
We didn’t use binary search, because we couldn’t find a negative value, which is not what we want.
class RecentCounter {
private int[] q;
private int head;
private int tail;
public RecentCounter(a) {
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.}}Copy the codec
typedef struct {
int *q;
int head;
int tail;
} RecentCounter;
RecentCounter *recentCounterCreate(a) {
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);
}
Copy the codec++
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; }};Copy the codepython
Python is about as clean as it gets this time, mainly with binary lookup that you can use directly.
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.head
Copy the codego
type RecentCounter struct {
q []int
head int
}
func Constructor(a) 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.
}
Copy the coderust
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.}}Copy the code