This is the second day of my participation in the August More text Challenge. For details, see:August is more challenging

[933] – Number of recent requests

Topic:

Write a RecentCounter class to count the most recent requests in a specific time frame.

Please implement the RecentCounter class:

RecentCounter() initializes the counter with the number of requests being zero. Int ping(int t) Adds a new request at time t, where t represents a time in milliseconds, and returns the number of all requests (including new requests) that occurred in the past 3000 milliseconds. Specifically, return the number of requests that occurred within [T-3000, t]. Make sure that each call to ping uses a larger t value than the previous one.

Example:

Input: [" RecentCounter ", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]] output: [null, 1, 2, 3, 3] :  RecentCounter recentCounter = new RecentCounter(); `` recentCounter.ping(1); // Requests = [1], range [-2999,1], return 1 recentCounter.ping(100); // Requests = [1, 100], range [-2900,100], return 2 recentCounter.ping(3001); // Requests = [1, 100, 3001], range [1,3001], return 3 recentCounter.ping(3002); // requests = [1, 100, 3001, 3002], range [2,3002], return 3Copy the code

Implementation solution 1: Traversing the number group (profiteering cracking)

答 案 :

• Store the number of each request in an array (and record the last bit subscript)
• Each time from the end of the array to iterate, for greater than or equal to [T-3000], the number of statistics, the sum

class RecentCounter {
	
 	  List<Integer> list = new ArrayList<Integer>(10000);

    public RecentCounter(a) {}public int ping1(int t) {
        list.add(t);
        int end = list.size() - 1;
        int count = 0;
        while (list.get(end) >= t - 3000) {
            count++;
            if (--end < 0) {
                break; }}returncount; }}Copy the code

Implementation Scenario 2: Optimization – Traversing groups

Optimization idea:

• Confirm the maximum number of requests in 3000 milliseconds? — > Use to reduce the storage space of arrays
  • T requests + the first 3000 times = 3001
  • But the array needs to be set to 3002 times.
• Do you need to iterate through all the nodes to count the number of times of the array? — > Reduce unnecessary cycles
  • Each time the array is added, the loop iterates through the array, deleting the data in the array that does not fit the range
  • Finally, only the request times that meet the conditions are left in the list, and the request times can be obtained directlysize()Can be

class RecentCounter {
	
 	  List<Integer> list = new ArrayList<Integer>(3002);

    public RecentCounter(a) {}public int ping1(int t) {
        list.add(t);
		   while (list.get(0) < t - 3000) {
    			list.remove(0);
		   }
		   returnlist.size(); }}Copy the code

Implementation scheme 3: queue solution

3-1: Custom queues (underlying use of linked lists)

答 案 :

• Use queue data structure, first in first out principle
  • Queue through a linked list
  • Define attributes: Headers:head, to the end:tail, length:size
  • Define method: Add node:add()Remove a node:poll(), queue length:size()
  • Internal definition:NodeClass to encapsulate each queued request and a pointer to the next node
• Each request appends a node to the end of the queue
• Loop to check if column header data is valid and remove nodes if it is not
• Return queue length

class RecentCounter {

    Queue<Integer> q = new LinkedList<Integer>();

    public RecentCounter(a) {}public int ping(int t) {
        q.add(t);
        while (q.head.getVal() < t - 3000) {
            q.poll();
        }
       return q.size();
    }

    class Queue {
        Node head;

        Node tail;

        int size = 0;

        Queue() {

        }

        public void add(int val) {
            if (head == null) {
                head = new Node(val);
                tail = head;
            } else {
                Node last = new Node(val);
                tail.next = last;
                tail = last;
            }
            size++;
        }

        public int poll(a) {
            int headVal = head.val;
            Node next = head.next;
            head.next = null;
            head = next;
            if (next == null) {
                tail = null;
            }
            size--;
            return headVal;
        }


        public int size(a) {
            return this.size;
        }


        class Node {
            int val;
            Node next;

            Node(int index) {
                this.val = index;
            }

            int getVal(a) {
                returnval; }}}}Copy the code

3-2: Use the queue provided by Java

The solution logic is consistent with the custom logic. There isn’t much customization needed to implement lists and queues in The native Java:

class RecentCounter {

    Queue<Integer> q = new LinkedList<Integer>();

    public RecentCounter(a) {}public int ping(int t) {
        q.add(t);
        while (q.peek() < t - 3000) {
            q.poll();
        }
        returnq.size(); }}Copy the code

Gitlab address

Case address