Leetcode question brushing record ｜ 933_ Recent requests

author github link ： github link

Force to buckle 933 topic

type ： queue

subject ：

Write a RecentCounter Class to calculate the most recent request in a specific time range .

Please realize RecentCounter class ：

• RecentCounter() Initialize counter , The number of requests is 0 .
• int ping(int t) In time t Add a new request , among t Represents a time in milliseconds , And go back to the past 3000 The number of all requests in milliseconds （ Including new requests ）. To be precise , Back in the [t-3000, t] The number of requests that occurred in .
  Guarantee Every time the ping All calls to the t value .

Example 1

 Input ：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
 Output ：
[null, 1, 2, 3, 3]

 explain ：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1);     // requests = [1], The scope is  [-2999,1], return  1
recentCounter.ping(100);   // requests = [1, 100], The scope is  [-2900,100], return  2
recentCounter.ping(3001);  // requests = [1, 100, 3001], The scope is  [1,3001], return  3
recentCounter.ping(3002);  // requests = [1, 100, 3001, 3002], The scope is  [2,3002], return  3

Their thinking

Train of thought details ：

1. Define a queue , Used to load request time
2. Load the request time into the queue one by one
3. Each time, judge whether the difference between the time when the queue now enters the queue and the time at the beginning of the queue is greater than 3000 La ！
4. Greater than 3000, Just make it out of the queue at the beginning of the queue , Go back and judge whether it is greater than 3000.
5. If not greater than 3000, The length of the return queue is the desired .

c++

class RecentCounter {
    
public:
    queue<int> Q;
    RecentCounter() {
    

    }
    
    int ping(int t) {
    
        Q.push(t);
        while(Q.size()>0 and t-Q.front()>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); */

python

class RecentCounter:

    def __init__(self):
        self.Q = collections.deque()
    def ping(self, t: int) -> int:
        self.Q.append(t)
        while len(self.Q)>0 and t-self.Q[0]>3000:
            self.Q.popleft()
        return len(self.Q)