早餐组合

518 次访问 2020-09-22

Walker

小扣在秋日市集选择了一家早餐摊位，一维整型数组 staple 中记录了每种主食的价格，一维整型数组 drinks 中记录了每种饮料的价格。
小扣的计划选择一份主食和一款饮料，且花费不超过 x 元。请返回小扣共有多少种购买方案。
注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1

示例 1：
输入：staple = [10,20,5], drinks = [5,5,2], x = 15
输出：6
解释：小扣有 6 种购买方案，所选主食与所选饮料在数组中对应的下标分别是：
第 1 种方案：staple[0] + drinks[0] = 10 + 5 = 15；
第 2 种方案：staple[0] + drinks[1] = 10 + 5 = 15；
第 3 种方案：staple[0] + drinks[2] = 10 + 2 = 12；
第 4 种方案：staple[2] + drinks[0] = 5 + 5 = 10；
第 5 种方案：staple[2] + drinks[1] = 5 + 5 = 10；
第 6 种方案：staple[2] + drinks[2] = 5 + 2 = 7。
示例 2：
输入：staple = [2,1,1], drinks = [8,9,5,1], x = 9
输出：8
解释：小扣有 8 种购买方案，所选主食与所选饮料在数组中对应的下标分别是：
第 1 种方案：staple[0] + drinks[2] = 2 + 5 = 7；
第 2 种方案：staple[0] + drinks[3] = 2 + 1 = 3；
第 3 种方案：staple[1] + drinks[0] = 1 + 8 = 9；
第 4 种方案：staple[1] + drinks[2] = 1 + 5 = 6；
第 5 种方案：staple[1] + drinks[3] = 1 + 1 = 2；
第 6 种方案：staple[2] + drinks[0] = 1 + 8 = 9；
第 7 种方案：staple[2] + drinks[2] = 1 + 5 = 6；
第 8 种方案：staple[2] + drinks[3] = 1 + 1 = 2；

提示：

1 <= staple.length <= 10^{5

1 <= drinks.length <= 10}5
1 <= staple[i],drinks[i] <= 10^{5

1 <= x <= 2*10}5

自我解答

需要找出主食+饮料，价格不超过 x 的所有组合数。这又让我联想到了"twoSum"，不用拿每个组合的和去试，
可以通过计算差来进行。然而这里就是要找出小于等于差的数量，这个完全可以通过二分查找实现。

class Solution2():
    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:
        case_num = 0
        staple.sort()
        drinks.sort()
        self.drinks = drinks
        self.drink_limit_map = dict()
        last_max_index = len(drinks) - 1
        for s in staple:
            if s >= x:
                continue
            drink_limit = x - s
            max_drink_index = self.find_max_drink_index(last_max_index, drink_limit)
            last_max_index = max_drink_index
            if last_max_index < 0:
                break
            case_num += (max_drink_index + 1)

        return case_num % 1000000007

    def find_max_drink_index(self, last_max_index, drink_limit):
        if drink_limit in self.drink_limit_map:
            return self.drink_limit_map[drink_limit]

        op_stack = [(0, last_max_index)]
        while op_stack:
            start_index, end_index = op_stack.pop(-1)
            if start_index == end_index:
                break

            mid = (start_index + end_index) // 2
            if self.drinks[mid] <= drink_limit:
                if self.drinks[mid + 1] <= drink_limit:
                    op_stack.append((mid + 1, end_index))
                else:
                    return mid
            else:
                op_stack.append((start_index, mid))

        max_drink_index = start_index if self.drinks[start_index] <= drink_limit else -1
        self.drink_limit_map[drink_limit] = max_drink_index
        return max_drink_index

这种方法有用，但是执行效率比较低。原因在于每个drink_limit都要进行二分查找，假如要查找出来的目标
就在上一个的旁边，二分查找却依然按部就班地从中间开始寻找。
尝试优化：
既然已经对两个列表进行了排序，这样按顺序查找出来的目标值就绝对小于等于上一个，
所以就不用每次都在整个数组中进行二分查找，但即使如此，
每次二分查找对比的次数和上次其实相差无几，并没有解决问题。

题解

一开始考虑过使用类似“插入排序”的方法，即拿到 drink_limit，插入到排序后 drink数组中，
但是插入排序需要每次都从末尾开始一个个找，相比二分效率要低多了，的确尝试写了一个，超时了，
那时候就完全否定了这个方法。可事实并不是这样的，其实使用插入排序 + 上面自己思考的优化策略，
就可以避免插入排序“每次都从末尾开始一个个找”带来的问题了。而且数组事先排过序了，“插入排序” 效率很高

class Solution4():
    def breakfastNumber(self, staple, drinks, x):
        staple.sort()
        drinks.sort()
        j = len(drinks) - 1
        case_num = 0
        for s in staple:
            if s >= x:
                break
            diff = x - s
            while j >= 0 and drinks[j] > diff:
                j -= 1
            case_num += (j + 1)
        return case_num % 1000000007

总结

1、二分法查找在初次查找时效率很高，但若每次都二分查找的话，效率就不高了，因为存在多个查找的话，每个查找
的数值间必定存在联系，可以通过这份联系寻找其他解决办法。
2、”插入排序“策略一开始是被我否定的，但是经过优化后，实现了算法性能上的飞跃。优化的方法是在使用二分法
时想到的，没想到能用在一开始被否定的方案中。所以不用完全否定某个方案，在考虑别的方案，优化无果时，
可以带着新的思路回顾之前的方案。

原题链接：https://leetcode-cn.com/problems/2vYnGI