【LeetCode】每一轮都要把输入数组看一遍的二分

写在前面

这里是小飞侠Pan🥳，立志成为一名优秀的前端程序媛！！！

本篇文章同时收录于我的github前端笔记仓库中，持续更新中，欢迎star~

👉https://github.com/mengqiuleo/myNote

---

475. 供暖器

475. 供暖器

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

说明：所有供暖器都遵循你的半径标准，加热的半径也一样。

示例 1:

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
1
2
3

示例 2:

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
1
2
3

示例 3：

输入：houses = [1,5], heaters = [2]
输出：3
1
2

题解思路

• 对于每个房屋，应该选择离该房屋最近的供暖器覆盖该房屋，最近的供暖器和房屋的距离即为该房屋需要的供暖器的最小加热半径。
• 所有房屋需要的供暖器的最小加热半径中的最大值即为可以覆盖所有房屋的最小加热半径。这里使用贪心的思想
• 为了得到距离每个房屋最近的供暖器，可以将供暖器数组 heaters 排序，然后通过二分查找得到距离最近的供暖器。
• 对于每一个房屋：
  • 先使用二分查找，拿到离这个房屋最近的左边的供暖器，这里就相当于查找小于指定元素的位置，也可以相当于查找一个右边界，使用二分查找
  • 如果拿到了左边的供暖器，那么离这个房屋最近的右边的供暖器应该是：用左边的供暖器+1

var findRadius = function(houses, heaters) {
  //这个函数用来找到，离指定房屋最近的左边的房屋，可以先跳过这个函数的代码，看主代码
    const binarySearch = function(heaters,target){
        let left = 0, right = heaters.length - 1;
        if(heaters[0] > target){ //如果第一个供暖器的位置要比房屋大，说明这个房屋没有左边的供暖器
            return -1;
        }
        while(left < right){
            let mid = left + ((right - left + 1)>>1);
            if(heaters[mid] > target){//如果mid代表的供暖器位置大于房屋，就要往左搜索
                right = mid - 1;
            }else{
                left = mid;
            }
        }
        return left;
    }

    let ans = 0; //保存最后的半径
    heaters.sort((a,b) => a - b); //先对供暖器升序排序，用来二分查找
    houses.forEach(house => { //遍历每一个房屋
        let i = binarySearch(heaters, house);//左边的供暖器
        let j = i + 1;//右边的供暖器
        let leftDistance = i < 0 ? Number.MAX_VALUE : house - heaters[i]; //左半径，如果没有左半径，赋值为无穷大
        let rightDistance = j >= heaters.length ? Number.MAX_VALUE : heaters[j] - house;//右半径，同上
        let curDistance = Math.min(leftDistance,rightDistance); //左右半径取最小值
        ans = Math.max(ans,curDistance);//每个房屋的半径取大值
    })
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

875. 爱吃香蕉的珂珂

875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。

珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

示例 1：

输入：piles = [3,6,7,11], h = 8
输出：4
1
2

示例 2：

输入：piles = [30,11,23,4,20], h = 5
输出：30
1
2

示例 3：

输入：piles = [30,11,23,4,20], h = 6
输出：23
1
2

题解思路

题目要求返回一个最小速度，使用二分查找，我们首先要确定二分查找的范围，那么他吃香蕉的最小速度应该为1，最大速度应该为所有香蕉中的最大值。

每堆香蕉吃完的耗时 = 这堆香蕉的数量 / 珂珂一小时吃香蕉的数量

但是要注意：使用上取整，因为比如你用了2.5h,但是在剩下的那半个小时内，珂珂将不会再吃香蕉，这个要求题目中已经说明：如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

上取整使用：Math.ceil

我们每找到一个速度mid，都要求出在这个mid下，吃完所有香蕉花费的总时间，所以我们自定义一个求总时间的函数totalTime

• 在if中，如果花费的总时间太大，说明吃得太慢了，我们要将速度加快，所以在右边搜索：left = mid + 1

var minEatingSpeed = function(piles, h) {
    let left = 1, right = Math.max(...piles);
    const totalTime = function(piles,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){ //吃得太慢啦
            left = mid + 1;
        }else{
            right = mid;
        }
    }
    return left;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19