“This is the 12th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Title 1

933. The number of recent requests

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 = 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 3

 

Tip:

1 <= t <= 109 Ensures that the t value used for each ping call is rigorously incremented \

Ping is called at most 104 times

Analysis of the

  • As can be seen from the above description,tRange of [T-3000,t]
  • definepingArrayArray, which holds the request values
  • judgepingArrayEvery element of the array, if it’s less than t-3000, we call itshift
  • Requests that remain in the range [t-3000,t]

Code implementation

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

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

Topic 2

17.09. The KTH number

Some numbers have only 3, 5, and 7 prime factors. design an algorithm to find the KTH number. Note that it is not necessary to have these prime factors, but to contain no other prime factors. For example, the first numbers would be 1,3,5,7,9,15,21 in that order.

Example 1:

Input: k = 5 Output: 9

Analysis of the

  • First of all, you can think about how does 1 make it through3,5,7Three to the zeroFive to the zero7 to the power is equal to 1, we can assume thatnumArrayThe first one is going to be 1.
  • The next number is going to be3,5,7Multiplied by numArray
  • I’m going to take the smallest out of the multiplicationpushTo the array
  • Whenever the number can be3,5,7Divisible, you add the corresponding number of times1operation

Code implementation

/** * @param {number} k * @return {number} */ var getKthMagicNumber = function(k) { let p3 = 0 let p5 = 0 let p7 = 0 let  numArray = new Array(k) numArray[0] = 1 for(let i =1; i < k; i++){ numArray[i] = Math.min(numArray[p3]*3,Math.min(numArray[p5]*5,numArray[p7]*7)) if(numArray[i] % 3 == 0) p3++ if(numArray[i] % 5 == 0) p5++ if(numArray[i] % 7 == 0) p7++ } return numArray[k-1] };Copy the code