酒类网站建设,西安软件外包公司,淘宝联盟填网站备案,用jsp做的网站的代码#x1f4cd;前言 #x1f57a;作者#xff1a; 迷茫的启明星 学习路线C语言从0到1C初阶数据结构从0到1 #x1f618;欢迎关注#xff1a;#x1f44d;点赞#x1f64c;收藏✍️留言 #x1f3c7;码字不易#xff0c;你的#x1f44d;点赞#x1f64c;收藏❤️关注对…前言 作者 迷茫的启明星 学习路线C语言从0到1C初阶数据结构从0到1 欢迎关注点赞收藏✍️留言 码字不易你的点赞收藏❤️关注对我真的很重要有问题可在评论区提出感谢阅读 持续更新中~
【二分查找】LCP 18. 早餐组合
在另一篇博客里讲过二分法的模板 《二分法的模板讲解》
题目描述
小扣在秋日市集选择了一家早餐摊位一维整型数组 staple 中记录了每种主食的价格一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料且花费不超过 x 元。请返回小扣共有多少种购买方案。
注意答案需要以 1e9 7 () 为底取模如计算初始结果为请返回 1
解题思路
首先我们需要对主食和饮料的价格进行排序。这样我们可以在遍历主食价格的同时使用二分查找法在有序的饮料价格中找到合适的饮料价格使得主食和饮料的总价格不超过 x 元。
为了实现二分查找我们需要定义左右指针 left 和 right以及中间指针 mid。在每一次循环中我们比较 drinks[mid] 与目标价格 target即 x - staple[i]。如果 drinks[mid] 小于等于 target说明饮料价格还有可能在左侧区间所以我们将 left 指针更新为 mid 1。否则我们将 right 指针更新为 mid - 1。
当遍历完所有的主食价格后我们将得到的购买方案数量 count 对 1e9 7 取模最后返回 count。
代码实现
class Solution {
public:int breakfastNumber(vectorint staple, vectorint drinks, int x) {sort(staple.begin(), staple.end());sort(drinks.begin(), drinks.end());int count 0;for (int i 0; i staple.size(); i) {int target x - staple[i];int left 0, right drinks.size() - 1;while (left right) {int mid left (right - left) / 2;if (drinks[mid] target) {left mid 1;} else {right mid - 1;}}count (count left) % ***;}return count;}
};
总结
这道题目考察了排序和二分查找法在求解组合问题中的应用。通过将主食和饮料的价格排序我们可以在 O(nlogn) 的时间复杂度内完成购买方案的查找。而二分查找法在这里起到了关键作用使得我们可以在 O(logn) 的时间复杂度内找到合适的饮料价格。
