力扣 - LCP 18. 早餐组合

2023-10-09 16:50
文章标签 组合 力扣 18 lcp 早餐

本文主要是介绍力扣 - 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

提示:

1 <= staple.length <= 10^5
1 <= drinks.length <= 10^5
1 <= staple[i],drinks[i] <= 10^5
1 <= x <= 2*10^5

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/2vYnGI

分析

暴力法

直接双层循环,来遍历就好了

int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x)
{int i = 0;int j = 0;int count = 0;for(i = 0; i < stapleSize; i++){for(j = 0; j < drinksSize; j++){if(x >= staple[i] + drinks[j]){count++;count = count % 1000000007;}}}return count;
}

很显然,结果超时
在这里插入图片描述

排序 + 双指针

其实我们很容易想到先排序,然后再进行查找后遍历。来优化算法。
这里使用C语言库函数qsort,时间复杂度为On*log (n),我们写的遍历时间复杂度为O(n2)

int compare_int(const void* e1, const void* e2) //比较函数
{return *(int*)e1 - *(int*)e2;
}int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x)
{int i = 0;int j = 0;int count = 0;int start = 0;int end = 0;int mid = 0;// 调用<stdlib.h>库函数 排序函数qsort(staple, stapleSize, sizeof(staple[0]), compare_int);qsort(drinks, drinksSize, sizeof(drinks[0]), compare_int);for (i = 0; i < stapleSize && staple[i] < x; i++){for(j = 0; j < drinksSize && drinks[j] <= x - staple[i]; j++){count++;count = count % 1000000007;}}return count;
}

在这里插入图片描述
居然还超时,我们再想想,这里我们没有考虑到排序后的数据是有序的特性。接下来我们通过二分法继续优化。

排序 + 二分法

我们根据staple的值只需要找到drinks数组中临界值。通过drinks的下标就可以一次知道了,前面都是符合的值,那么我们就可以用二分法来查找第一个不符合的。但是这里还有一个小坑,如果所有数据都成立那么通过二分法得到的也仅仅为下标最大值,所以这里我们可以把所有数据都成立的情况特殊列出来。

这样我们的时间复杂度就是O (log 2 n)与qsort库函数复杂度相同。空间复杂度为1.

int compare_int(const void* e1, const void* e2) //升序排序的比较函数
{return *(int*)e1 - *(int*)e2;
}int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x)
{int i = 0;int j = 0;int count = 0;int start = 0;int end = 0;int mid = 0;// 调用<stdlib.h>库函数 排序函数qsort(staple, stapleSize, sizeof(staple[0]), compare_int);qsort(drinks, drinksSize, sizeof(drinks[0]), compare_int);for (i = 0; i < stapleSize && staple[i] < x; i++){//考虑到最优情况(特殊情况) 所有数据都符合就直接终止if (drinks[drinksSize - 1] <= x - staple[i]){count += drinksSize;continue;}start = 0;end = drinksSize - 1;while (start < end){mid = (start + end) / 2;if (drinks[mid] <= x - staple[i]){start = mid + 1;}else{end = mid;}}count += start;count = count % 1000000007;}return count;
}

在这里插入图片描述
功夫不负有心人,终于能跑了。这里我又想到一个点,俩个数组的值都是逐渐增大,而x不变。所以drinks数组的上限end应该小于等于上一个上限

排序 + 优化二分法

俩个数组的值都是逐渐增大,而x不变。所以drinks数组的上限end应该小于等于上一个上限。如果没懂建议多读几遍。所以我们可以再增加一个变量来记录上次的上限用于更新。

int compare_int(const void* e1, const void* e2) //升序排序的比较函数
{return *(int*)e1 - *(int*)e2;
}int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x)
{int i = 0;int j = 0;int count = 0;int start = 0;int end = 0;int mid = 0;int upper = drinksSize - 1; // 用于记录上次所取区间的上限int len = 0;                // 计算相同价格的主食有几种// 调用<stdlib.h>库函数 排序函数qsort(staple, stapleSize, sizeof(staple[0]), compare_int);qsort(drinks, drinksSize, sizeof(drinks[0]), compare_int);for (i = 0; i < stapleSize && staple[i] < x; i++){// 考虑到最优情况 所有数据都符合就直接终止if (drinks[drinksSize - 1] <= x - staple[i]){count += drinksSize;continue;}// 正常情况start = 0;end = upper;mid = (start + end) / 2;while (start < end){if (drinks[mid] <= x - staple[i]){start = mid + 1;}else{end = mid;}mid = (start + end) / 2;}count += start;upper = end;count = count % 1000000007;}return count;
}

在这里插入图片描述

排序 + 二次优化二分法

上面优化了drinks数组,同样是不是可以优化staple数组?是的。我们可以将staple相同的数据统计起来一次计算。这里我们又增加了len一个变量,用来计算staple数组中重复的数据。

int compare_int(const void* e1, const void* e2) //升序排序的比较函数
{return *(int*)e1 - *(int*)e2;
}int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x)
{int i = 0;int j = 0;int count = 0;int start = 0;int end = 0;int mid = 0;int upper = drinksSize - 1; // 用于记录上次所取区间的上限int len = 0;                // 计算相同价格的主食有几种// 调用<stdlib.h>库函数 排序函数qsort(staple, stapleSize, sizeof(staple[0]), compare_int);qsort(drinks, drinksSize, sizeof(drinks[0]), compare_int);for (i = 0; i < stapleSize && staple[i] < x; i++){len = 1;while (i < stapleSize - 1 && staple[i] == staple[i + 1]){i++;len++;}// 考虑到最优情况 所有数据都符合就直接终止if (drinks[drinksSize - 1] <= x - staple[i]){count += drinksSize * len;continue;}// 正常情况start = 0;end = upper;mid = (start + end) / 2;while (start < end){if (drinks[mid] <= x - staple[i]){start = mid + 1;}else{end = mid;}mid = (start + end) / 2;}count += start * len;upper = end;count = count % 1000000007;}return count;
}

在这里插入图片描述

空间换时间,复杂度直接降为O(n)

因为早餐的价格均为整数,我们有x的资金。即我们早餐主食的选择有:1 2 3 … x-1。我们可以用一个n[x]的数组来实现,数组中存放的是当前下标价位的早餐种类。一次遍历主食staple数组,获取到符合要求的主食种类。当我们主食价格为2元的搭配都符合时,那么主食为1元的也不是符合吗?
所有我们还需要遍历一次,n[i] += n[i - 1] + n[i - 2] + ... n[1];
最后我们只需要对drinks数组遍历,n[x - drinks[i]]里面存放的值就是当前饮料对应主食的种类。
让我们实现吧。

int breakfastNumber(int* staple, int stapleSize, int* drinks, int drinksSize, int x)
{int n[x];int i = 0;int count = 0;memset(n, 0, sizeof(int) * x);// 将主食价格小于x的放入数组对应的下标,下标里面放的数字表示当前下标出现的次数for(i = 0; i < stapleSize; i++){if(staple[i] < x)//主食价格小于总金额{n[staple[i]]++;}}// 因为前面的价格必然小于等于后面的价格,也就是只要符合当前下标的话,你前面也都符合,// 所以我们直接累加。假如现在主食8元。n[8]中放的是主食{1...8}的所有种数for(i = 2; i < x; i++){n[i] += n[i - 1];}for(i = 0; i < drinksSize; i++){if(x - drinks[i] > 0){count += n[x - drinks[i]];count = count % 1000000007;}}return count;
}

在这里插入图片描述
这样我们的时间复杂度只有O(n),空复杂度也为O(n)

本章完!

这篇关于力扣 - LCP 18. 早餐组合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/174219

相关文章

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

Go组合

摘要 golang并非完全面向对象的程序语言,为了实现面向对象的继承这一神奇的功能,golang允许struct间使用匿名引入的方式实现对象属性方法的组合 组合使用注意项 使用匿名引入的方式来组合其他struct 默认优先调用外层方法 可以指定匿名struct以调用内层方法 代码 package mainimport ("fmt")type People struct{}type Pe

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

react笔记 8-18 事件 方法 定义方法 获取/改变数据 传值

1、定义方法并绑定 class News extends React.Component {constructor(props) {super(props)this.state = {msg:'home组件'}}run(){alert("我是一个run") //方法写在类中}render() {return (<div><h2>{this.state.msg}</h2><button onCli

组合c(m,n)的计算方法

问题:求解组合数C(n,m),即从n个相同物品中取出m个的方案数,由于结果可能非常大,对结果模10007即可。       共四种方案。ps:注意使用限制。 方案1: 暴力求解,C(n,m)=n*(n-1)*...*(n-m+1)/m!,n<=15 ; int Combination(int n, int m) { const int M = 10007; int

代码随想录训练营day37|52. 携带研究材料,518.零钱兑换II,377. 组合总和 Ⅳ,70. 爬楼梯

52. 携带研究材料 这是一个完全背包问题,就是每个物品可以无限放。 在一维滚动数组的时候规定了遍历顺序是要从后往前的,就是因为不能多次放物体。 所以这里能多次放物体只需要把遍历顺序改改就好了 # include<iostream># include<vector>using namespace std;int main(){int n,m;cin>>n>>m;std::vector<i

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

INDEX+SMALL+IF+ROW函数组合使用解…

很多人在Excel中用函数公式做查询的时候,都必然会遇到的一个大问题,那就是一对多的查找/查询公式应该怎么写?大多数人都是从VLOOKUP、INDEX+MATCH中入门的,纵然你把全部的多条件查找方法都学会了而且运用娴熟,如VLOOKUP和&、SUMPRODUCT、LOOKUP(1,0/....,但仍然只能对这种一对多的查询望洋兴叹。   这里讲的INDEX+SMALL+IF+ROW的函数组合,

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调