【LeetCode】 Look at the input array twice in each round

Write it at the front

This is xiaofeixia Pan🥳, Determined to become an excellent front-end program yuan ！！！

This article is also included in my github In the front-end note warehouse , Ongoing update , welcome star~

https://github.com/mengqiuleo/myNote

475. heater

475. heater

Winter has come . Your task is to design a heater with fixed heating radius to heat all houses .

Every house within the heating radius of the heater can be heated .

Now? , Give the house on a horizontal line houses And heater heaters The location of , Please find and return the minimum heating radius that can cover all houses .

explain ： All heaters follow your radius standard , The radius of the heating is the same .

Example 1:

 Input : houses = [1,2,3], heaters = [2]
 Output : 1
 explain :  Only in position 2 There's a heater on it . If we set the heating radius to 1, Then all the houses will be heated .

Example 2:

 Input : houses = [1,2,3,4], heaters = [1,4]
 Output : 1
 explain :  In position 1, 4 There are two heaters on it . We need to set the heating radius to 1, So that all the houses can be heated .

Example 3：

 Input ：houses = [1,5], heaters = [2]
 Output ：3

Solution to the problem

• For every house , The nearest heater to the house should be selected to cover the house , The distance between the nearest heater and the house is the minimum heating radius of the heater required by the house .
• The maximum of the minimum heating radius of the heater required by all houses is the minimum heating radius that can cover all houses . Greedy thoughts are used here
• In order to get the nearest heater to each house , You can array the heaters heaters Sort , Then find the nearest heater through binary search .
• For every house ：
  • Use binary search first , Get the heater on the left nearest to the house , This is equivalent to finding a position smaller than the specified element , It can also be equivalent to finding a right boundary , Use binary search
  • If you get the heater on the left , Then the heater on the right nearest to the house should be ： Use the heater on the left +1

var findRadius = function(houses, heaters) {
    
  // This function is used to find , The house on the left nearest to the designated house , You can skip the code of this function first , Look at the main code 
    const binarySearch = function(heaters,target){
    
        let left = 0, right = heaters.length - 1;
        if(heaters[0] > target){
     // If the location of the first heater is larger than the house , It means that this house doesn't have a heater on the left 
            return -1;
        }
        while(left < right){
    
            let mid = left + ((right - left + 1)>>1);
            if(heaters[mid] > target){
    // If mid The location of the representative heater is larger than that of the house , Search to the left 
                right = mid - 1;
            }else{
    
                left = mid;
            }
        }
        return left;
    }

    let ans = 0; // Save the last radius 
    heaters.sort((a,b) => a - b); // First, sort the heaters in ascending order , Used for binary search 
    houses.forEach(house => {
     // Traverse every house 
        let i = binarySearch(heaters, house);// The heater on the left 
        let j = i + 1;// The heater on the right 
        let leftDistance = i < 0 ? Number.MAX_VALUE : house - heaters[i]; // Left radius , If there is no left radius , The assignment is infinite 
        let rightDistance = j >= heaters.length ? Number.MAX_VALUE : heaters[j] - house;// Right radius , ditto 
        let curDistance = Math.min(leftDistance,rightDistance); // The left and right radii are the minimum 
        ans = Math.max(ans,curDistance);// The radius of each house is taken as the larger value 
    })
    return ans;
};

875. Coco, who loves bananas

875. Coco, who loves bananas

Coco likes bananas . Here you are n Make bananas , The first i There is... In the pile piles[i] A banana . The guards have left , Will be in h Come back in hours .

Coco can decide how fast she eats bananas k （ Company ： root / Hours ）. Every hour , She will choose a bunch of bananas , Eat from it k root . If this pile of bananas is less than k root , She will eat all the bananas in this pile , Then I won't eat more bananas in an hour .

Coco likes to eat slowly , But still want to eat all the bananas before the guards come back .

She can go back to h Minimum speed to eat all bananas in hours k（k Integers ）.

Example 1：

 Input ：piles = [3,6,7,11], h = 8
 Output ：4

Example 2：

 Input ：piles = [30,11,23,4,20], h = 5
 Output ：30

Example 3：

 Input ：piles = [30,11,23,4,20], h = 6
 Output ：23

Solution to the problem

The question requires that a minimum speed be returned , Use binary search , We first need to determine the range of binary search , Then the minimum speed at which he eats bananas should be 1, The maximum speed should be the maximum of all bananas .

It takes time to finish each pile of bananas = The number of bananas in this pile / How many bananas does Koko eat in an hour

But be careful ： Use rounding , Because, for example, you used 2.5h, But in the remaining half an hour , Koko will no longer eat bananas , This requirement has been stated in the title ： If this pile of bananas is less than k root , She will eat all the bananas in this pile , Then I won't eat more bananas in an hour .

Round up to use ：Math.ceil

Every time we find a speed mid, It's all about this mid Next , The total time spent eating all bananas , So we customize a function to calculate the total time totalTime

• stay if in , If the total time spent is too large , It means eating too slowly , We need to speed up , So search on the right ：left = mid + 1

var minEatingSpeed = function(piles, h) {
    
    let left = 1, right = Math.max(...piles);
    const totalTime = function(piles,speed){
     // Find the total time at the current speed 
        let sum = 0;
        piles.forEach(pile => {
    
            sum += Math.ceil(pile/speed);
        })
        return sum;
    }
    while(left < right){
    
        let mid = left + ((right - left)>>1);
        if(totalTime(piles,mid) > h){
     // Eat too slowly 
            left = mid + 1;
        }else{
    
            right = mid;
        }
    }
    return left;
};