“This is the first day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

Today we learned about the pigeon nest principle and special uses that sort() didn’t know about

Topic describes

Today’s topic is 539 on LeetCode. Minimum time difference difficulty is medium

  • Given a 24-hour time list (hour: minute “HH:MM”), find the minimum time difference between any two times in the list in minutes.

Example 1:

Enter: timePoints = ["23:59."."Prefer"] output:1
Copy the code

Example 2:

Enter: timePoints = ["Prefer"."23:59."."Prefer"] output:0
Copy the code

Tip:

  • 2 <= timePoints.length <= 2 * 104
  • TimePoints [I] Format: “HH:MM”

Answer key

To convert the list data to a specific number, write a simple conversion function getMinutes(t) by analyzing four characters.

const getMinutes = (t){
    return ((t[0].charCodeAt() - '0'.charCodeAt()) * 10 + (t[1].charCodeAt()  
            - '0'.charCodeAt())) * 60 + (t[3].charCodeAt() - '0'.charCodeAt())  
            * 10 + (t[4].charCodeAt() - '0'.charCodeAt())
}
Copy the code

This will be easier for us to do later.

Violent solution

First of all, a very simple solution to the problem is, seemingly time comparison between will have trouble, but we through the above method into specific minutes, can be to sort all the time, and then by comparing the gap between adjacent time, each can get how much is the minimum of time apart, it must be pay attention to the minimum and maximum time, There may be 00:00 and 23:59 cases, so it is necessary to compare the first and last digits.

var findMinDifference = function(timePoints) {
    let arr =[]
    for(o of timePoints){
        arr.push(getMinutes(o)) // Save the converted minutes with a new array
    }
     console.log(arr)
    arr.sort(function(a, b){return a - b})  / / sorting
    console.log(arr)
    let ans = 1440;
    let oneMinutes = arr[0];
    let preMinutes = oneMinutes;
    for (let i = 1; i < arr.length; ++i) {
        const minutes = arr[i];
        ans = Math.min(ans, minutes - preMinutes); // The time difference between adjacent times
        preMinutes = minutes;
    }
    ans = Math.min(ans, oneMinutes + 1440 - preMinutes); // Time difference between beginning and end
    return ans;
};
Copy the code

Using the pigeon nest principle to optimize

We can also use the pigeon nest principle to optimize our code:

  • If there are ten apples but only nine boxes, one apple will not fit inside. By extension, if you have n+1 elements to put into n sets, then one of them must have two elements.

In this case, since there are at most 1440 different times of time, when n is greater than this number, there must be two times of the same time, and we can simply return 0

To do this, we can add an optimization to the code above:

const n = timePoints.length; if (n > 1440) { return 0; }
Copy the code

Optimization – Sort the original array directly

Create a new array to store the converted minutes, which is a waste of memory. We can use sort() on the original array.

var findMinDifference = function(timePoints) { timePoints.sort(); . . };Copy the code

The default sorting mechanism because of the sort () is the element as a contrast to the string, specific can see official Array. The prototype. The sort () – JavaScript | MDN (mozilla.org) so we don’t have to create a new Array to save minutes after the transformation, Just iterate through the sorted array and convert it at assignment time. Next, attach the optimized final code:

var findMinDifference = function(timePoints) {
    const n = timePoints.length;
    if (n > 1440) {
        return 0;
    }
    timePoints.sort(); / / sorting
    let ans = 1440;
    let oneMinutes = getMinutes(timePoints[0]);
    let preMinutes = oneMinutes;
    for (let i = 1; i < n; ++i) {
        const minutes = getMinutes(timePoints[i]);
        ans = Math.min(ans, minutes - preMinutes); // The time difference between adjacent times
        preMinutes = minutes;
    }
    ans = Math.min(ans, oneMinutes + 1440 - preMinutes); // Time difference between beginning and end
    return ans;
};
Copy the code