LeetCode-LCP 18. 早餐组合(Goland实现)

怼烎@ 2022-12-06 15:54 154阅读 0赞

> LeetCode题号：[LCP 18. 早餐组合][LCP 18.]
> 
> 问题描述：
> 
>       小扣在秋日市集选择了一家早餐摊位，一维整型数组 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；

>  优化前：暴力破解，可惜耗时太久，无法通过官方测试。
> 
> 优化后：采用排序+二分查找，staple数组中的所有数字以staple\[i\]-x为目标值在drinks中二分查找存在重复值，故二分搜索应查找最靠右的目标值。

优化前code：

func breakfastNumber(staple []int, drinks []int, x int) int {
    	const NUMBER = 1000000007
    	var count int = 0
    	sort.Ints(staple)
    	sort.Ints(drinks)
    	for i := 0; i < len(staple); i++ {
    		if staple[i] > x {
    			break
    		}
    		for j := 0; j < len(drinks); j++ {
    			if drinks[j] > x {
    				break
    			}
    			if staple[i]+drinks[j] <= x {
    				count++
    			}
    		}
    	}
    	return count % NUMBER
    }

优化后code：

func breakfastNumber(staple []int, drinks []int, x int) int {
    	const NUMBER = 1000000007
    	var count = 0
    	sort.Ints(staple)
    	sort.Ints(drinks)
    	for i := 0; i < len(staple); i++ {
    		if staple[i] > x {
    			break
    		}
    		var low = 0
    		var high = len(drinks)
    		var target = x - staple[i]
    		//采用二分查找
    		for j := len(drinks) - 1; j >= 0 && low < high; j-- {
    			var mid = (low + high) / 2
    			//比目标值大，说明目标值在当前mid值左边，接着往左分
    			if drinks[mid] > target {
    				high = mid
    			} else {
    				//比目标值小，往右+1查找
    				low = mid + 1
    			}
    		}
    		//找到小于等于目标值(target)的元素下标，即[0，low]中的值都满足。
    		count += low
    	}
    	return count % NUMBER
    }

--------------------

### 往期回顾： ###

【1】[LCP 17. 速算机器人][LCP 17.]

--------------------

> ❤如果文章对您有所帮助，就在文章的右上角或者文章的末尾点个赞吧！(づ￣ 3￣)づ 
> 
> ❤如果喜欢大白兔分享的文章，就给大白兔点个关注吧！(๑′ᴗ‵๑)づ╭❤～
> 
> ❤对文章有任何问题欢迎小伙伴们下方留言或者入群探讨【群号：708072830】
> 
> ❤鉴于个人经验有限，所有观点及技术研点，如有异议，请直接回复讨论(请勿发表攻击言论)

[LCP 18.]: https://leetcode-cn.com/problems/2vYnGI/
[LCP 17.]: https://blog.csdn.net/weixin_43970743/article/details/108579882