小扣在秋日市集选择了一家早餐摊位,一维整型数组 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:
class Solution:
def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:
# for 超时
# while 超时,
# 执行用时: 1396 ms
count = 0
drinks = sorted(drinks)
# 单排序 加 二分查找
for item in staple:
if item > x:
continue
# 对排序的 二分查找
b = x - item # 找到
first = 0
end = len(drinks)
while first < end: # 找到 first = end
mid = (first + end) // 2
if drinks[mid] > b:
end = mid
else:
first = mid + 1
count += first
count = count % (1000000007)
return count
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)