One, foreword

This problem is very easy to understand. However, WHEN I used the code to express my thoughts, I did not pay attention to it, which resulted in the solution error in my first submission. Here’s what’s wrong: An ascending array, every time you add an element to it let’s say it’s t (which is larger than the original element in the array), you have to delete everything in the array that is less than t-3000. So I wrote the following code:

for(let i = 0; i < this.arr.length; ++i) {
    if(this.arr[i] < t - 3000) {
      this.arr.shift()
    } else{
      break
    }
  }
Copy the code

At first glance, there is no problem. Note that when deleting, you should add a line of code I –, correct code:

for(let i = 0; i < this.arr.length; ++i) {
    if(this.arr[i] < t - 3000) {
      this.arr.shift()
      i--
    } else{
      break
    }
  }
Copy the code

2. Title Description

Write a RecentCounter class to count the most recent requests within a specific time range.

Please implement RecentCounter class:

  • RecentCounter() initializes the counter with 0 requests.
  • Int ping(int t) adds a new request at time t, where t represents some time in milliseconds, and returns the number of all requests (including new requests) that occurred in the last 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 before.

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], 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 code

 

Tip:

  • 1 <= t <= 109
  • Ensure that the t value used for each ping call is strictly incremented
  • Ping is called at most 104 times

See the Leetcode link for a full description

Third, the problem solving

3.1 train of thought

If you read this carefully, you know how to do it

  • Maintains an array to store the timestamp of each request
  • The elements in this array are ordered, ascending
  • The timestamp in this array is Max – min <= 3000
  • As it is in ascending order, that is, ARr [Length-1] -ARr [0] <= 3000

3.2 Accidentally error code

If you are not careful, you will make the kind of mistake I mentioned in the preface

var RecentCounter = function() {
  this.arr = [] 
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
  this.arr.push(t)
  for(let i = 0; i < this.arr.length; ++i) {
    if(this.arr[i] < t - 3000) {
      this.arr.shift()
      i--
    } else{
      break
    }
  }
  return this.arr.length
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */
Copy the code

3.3 Elegant Code

It’s elegant and it’s not prone to the kind of mistakes THAT I made in the prologue

var RecentCounter = function() {
  this.arr = []
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
  this.arr.push(t)
  while(t - this.arr[0] > 3000) {
    this.arr.shift()
  }
  return this.arr.length
};

/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */
Copy the code