【试一试】问题之隐式二分问题 2020-07-27（未允禁转）

2020-07-27  本文已影响0人  9_SooHyun

1.前言

二分查找，我们接触最多的是，给定一个完全有序的数组（最普通的二分查找）或者一个局部有序的数组（leetcode搜索旋转数组），然后从整个数组中搜索一个值。往往整个待搜索数组的全体元素显式地展现在我们眼前。但有些时候，这个“数组”给出的方式不会那么直接，而是“隐式”地给出

2.【试一试】问题之隐式二分问题

875. 爱吃香蕉的珂珂
1011. 在 D 天内送达包裹的能力
410. 分割数组的最大值
通过上面3个经典题阐述一下，啥是【试一试】问题

875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫离开了，将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）
示例 1：
输入: piles = [3,6,7,11], H = 8
输出: 4
解释：第1小时吃掉3，第2、3小时吃掉6，第4、5小时吃掉7，第6、7、8小时吃掉11

思路：
首先最直接和自然的思路是正向思维，就是我有没有一个方法，通过某种公式规则直接推导出答案，似乎比较难。那么我们换一个思路，试
——我们先拿一个数作为假想答案，然后去试试看照这样吃需要多少小时，如果时间超了就每小时再多吃一点，否则可以尝试每小时再少吃一点，这小学生都会
再深入一下，珂珂最少每小时得吃一根吧，最多可以吃无数根，但因为一堆香蕉不够吃的话，也得花一小时，因此最多吃max(piles)就可以了，多吃无益。那么最终的答案必然落在[1, max(piles)]里面。这个区间是我们分析出来的，不是显式给出的；然后这个区间显然是一个有序区间，有序区间搜索一个数，妥妥地标准二分查找题

class Solution:
    def minEatingSpeed(self, piles: List[int], H: int) -> int:
        low, high = 1, max(piles)
        while low < high:
            mid = low + (high - low) // 2
            cnt = 0
            for i in range(len(piles)):
                remain = 0
                if piles[i] % mid != 0:
                    remain = 1
                cnt += (piles[i] // mid + remain)
                if cnt > H:
                    low = mid + 1
                    break
            else:
                high = mid
        return low

回顾总结：

1011. 在 D 天内送达包裹的能力

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。

示例 1：
输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10
请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。

找到运载能力的上下界，形成搜索区间[max(weights), sum(weights)]

class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        low, high = max(weights), sum(weights)
        while low < high:
            mid = low + (high-low) // 2
            day = 1
            temp_sum = 0
            for i in range(len(weights)):
                if temp_sum + weights[i] > mid:
                    day += 1
                    temp_sum = weights[i]
                else:
                    temp_sum += weights[i]
            if day > D:
                low = mid + 1
            else:
                high = mid
        return low

410. 分割数组的最大值

给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。

注意:
数组长度 n 满足以下条件:
1 ≤ n ≤ 1000
1 ≤ m ≤ min(50, n)

示例:
输入:
nums = [7,2,5,10,8]
m = 2
输出:
18
解释:
一共有四种方法将nums分割为2个子数组。
其中最好的方式是将其分为[7,2,5] 和 [10,8]，
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小

思路：
这题实际上和吃香蕉、运货物的本质是一样的，只不过没有场景背景，晦涩了一点。H小时吃香蕉 = D天运完 = m个子数组
那么这个题的搜索区间就是[min(nums), sum(nums)]，然后通过二分查找判断mid能否把nums分成m个子数组

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        def isValid(n):
            cur_sum, group_count = 0, 1
            for i in range(len(nums)):
                if cur_sum + nums[i] <= n:
                    cur_sum += nums[i]
                else:
                    cur_sum = nums[i]
                    group_count += 1
            return group_count <= m
        
        low = max(nums)
        high = sum(nums)
        while low < high:
            mid = low + (high - low) // 2
            if isValid(mid):
                high = mid
            else:
                low = mid + 1
        return low

3.小结

上一篇下一篇

猜你喜欢

热点阅读