用微信怎么做商城网站吗,海口网站运营托管公司,wordpress用户注册邮箱验证码,住房和城乡建设部网站八大员文章目录1. 题目2. 解题1. 题目
给你一个下标从 0 开始的正整数数组 candiesCount #xff0c;其中 candiesCount[i] 表示你拥有的第 i 类糖果的数目。 同时给你一个二维数组 queries #xff0c;其中 queries[i] [favoriteTypei, favoriteDayi, dailyCapi] 。
你按照如下…
文章目录1. 题目2. 解题1. 题目
给你一个下标从 0 开始的正整数数组 candiesCount 其中 candiesCount[i] 表示你拥有的第 i 类糖果的数目。 同时给你一个二维数组 queries 其中 queries[i] [favoriteTypei, favoriteDayi, dailyCapi] 。
你按照如下规则进行一场游戏
你从第 0 天开始吃糖果。你在吃完 所有 第 i - 1 类糖果之前不能 吃任何一颗第 i 类糖果。在吃完所有糖果之前你必须每天 至少 吃 一颗 糖果。
请你构建一个布尔型数组 answer 满足 answer.length queries.length 。 answer[i] 为 true 的条件是在每天吃 不超过 dailyCapi 颗糖果的前提下 你可以在第 favoriteDayi 天吃到第 favoriteTypei 类糖果否则 answer[i] 为 false 。 注意只要满足上面 3 条规则中的第二条规则你就可以在同一天吃不同类型的糖果。
请你返回得到的数组 answer 。
示例 1
输入candiesCount [7,4,5,3,8], queries [[0,2,2],[4,2,4],[2,13,1000000000]]
输出[true,false,true]
提示
1- 在第 0 天吃 2 颗糖果(类型 0第 1 天吃 2 颗糖果类型 0第 2 天你可以吃到类型 0 的糖果。
2- 每天你最多吃 4 颗糖果。即使第 0 天吃 4 颗糖果类型 0第 1 天吃 4 颗糖果类型 0 和类型 1你也没办法在第 2 天吃到类型 4 的糖果。换言之你没法在每天吃 4 颗糖果的限制下在第 2 天吃到第 4 类糖果。
3- 如果你每天吃 1 颗糖果你可以在第 13 天吃到类型 2 的糖果。示例 2
输入candiesCount [5,2,6,4,1], queries [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
输出[false,true,true,false,false]提示
1 candiesCount.length 10^5
1 candiesCount[i] 10^5
1 queries.length 10^5
queries[i].length 3
0 favoriteTypei candiesCount.length
0 favoriteDayi 10^9
1 dailyCapi 10^9来源力扣LeetCode 链接https://leetcode-cn.com/problems/can-you-eat-your-favorite-candy-on-your-favorite-day 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
见注释前缀和思想
class Solution {
public:vectorbool canEat(vectorint candiesCount, vectorvectorint q) {vectorlong long presum(candiesCount.size());for(int i 0 ;i candiesCount.size(); i)presum[i] candiesCount[i];for(int i 1; i candiesCount.size(); i) {presum[i] presum[i-1];//前缀和}int n q.size();vectorbool ans(n, false);for(int i 0; i n; i){int idx q[i][0];// 要吃的类型int day q[i][1];// 前面要吃多少天int eat q[i][2];//每天最多吃多少long long l (idx 0 ? (presum[idx-1]1) : 1), r presum[idx];// l, r 需要吃到 [l, r] 这个范围内才行long long L day*1LL1, R (day1LL)*eat;// L, R 最少最多能吃的范围// 两者有交集 即可if((l L l R)||(r L r R))ans[i] true;else if((L l L r)||(R l R r))ans[i] true;}return ans;}
};372 ms 118.1 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
