[每日一题]吃糖果(前缀和+区间)

122 阅读 0 评论 81 点赞

我是靠谱客的博主勤恳夕阳，这篇文章主要介绍[每日一题]吃糖果(前缀和+区间)，现在分享给大家，希望可以做个参考。

题目地址：力扣

题目表述

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
给你一个下标从 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 。

输入：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]


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/can-you-eat-your-favorite-candy-on-your-favorite-day
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路::

前缀和计算节省后面多组数据时间
注意数据范围爆int
先计算可以吃的范围=>1*天数->最高要求*天数，这里注意天数从零开始
再计算i天需要的范围前缀和=>S[i]->S[i+1]，这里注意边界判断
两个范围交集存在即可

代码::

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
        //前缀和：
        vector<long long> cand_ans;
        vector<bool> ans;
        long long i = 0;
        cand_ans.push_back(i);
        for(auto j:candiesCount)
        {
            i += j; 
            cand_ans.push_back(i);
        }
        

        for(i = 0; i < queries.size(); ++i)
        {
            long long l=queries[i][0]==0?1:cand_ans[queries[i][0]]+1;
            ans.push_back(!(queries[i][1]+1>cand_ans[queries[i][0]+1]||(long long)(queries[i][1]+1)*queries[i][2]<l));
        }
        return ans;
    }
};