小鲸鱼的梦境
0%

『LeetCode』1744 你能在你最喜欢的那天吃到你最喜欢的糖果吗

发表于 更新于 分类于 Valine：
本文字数： 4.2k 阅读时长 ≈ 4 分钟

题目

1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？

难度: 中等

给你一个下标从 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\) 。

\(/quad\)

示例 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\)

解析

大家儿童节快乐呀~

今天你吃了甜甜的糖果🍭吗?

题目有点长，先梳理清楚题意：

在一排格子中，每个格子放了一些糖果，格子中糖果的数量记录在 candiesCount 中，现在我们必须按顺序吃掉格子中的糖果，在当前格子的糖果没吃完之前不能吃下一个格子中的糖果，现在请回答一个问题：

  • 假设每天最多吃 z 颗糖果, 最少也要吃 1 颗糖果，第 y 天是我的生日了，请问我能不能在生日那天吃到放在第 x 个格子中的我最喜欢吃的糖果呢？

但是除了我以外，我的朋友们也想在生日那天吃到他们喜欢的糖果，所以请对上述问题给出一个通用的解决方案，对于每个人对应的 (x,y,z) 值放在了二维数组参数 queries 中

前缀和

不难看出，想要吃到第 i 个格子中的糖果，就必须吃光前 i - 1 个格子中的糖果，所以我们得先计算出前 i - 1 个格子中的糖果总数 s[i], 但是呢也不能在 y 天之前就把第 i 个格子的糖果吃完了，所以要求前 y 天吃掉的糖果总数在 \((s[i],s[i + 1]]\) 区间范围内我们才能在喜欢的日子吃掉喜欢的糖果

另一方面，我们考察我们到第 y 天能吃多少颗糖果，按照要求每天最少吃一颗糖果，最多吃 z 颗糖果，所以第 y 天能吃糖果的数量范围为 \([y+1,z * (y+1)]\) (注意天数是从0开始的)

显然，只要上述的两个区间有交集那么我们就能在喜欢的日子吃掉喜欢的糖果啦~

为了避免在多次查询时重复计算前 n 个格子中糖果总数，我们使用前缀和数组 \(s\) 记录 前 i 个格子中糖果的总数，\(s[i]\) 表示前 i-1 类糖果的数量和, 这样我们就能在 \(O(1)\) 时间查询到前 i 个格子中糖果的总数

再提一句，如果两区间 A,B 有交集，那么必定有 \(A\\_left < B\\_right \\&\\& A\\_right > B\\_left\), 或者考察对立事件 A,B 没有交集，有 \(A\\_left > B\\_right || A\\_right < B\\_left\)

复杂度

  • 时间复杂度: \(O(n+m)\), 计算前缀和数组 \(O(n)\), \(queries\) 中 \(m\) 个查询每次都是 \(O(1)\)
  • 空间复杂度: \(O(n)\), 前缀和数组的空间

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Code language: Python
class Solution:
    def canEat(self, candiesCount: List[int], queries: List[List[int]]) -> List[bool]:
        # candiesCount[i] 表示你拥有的第 i 类糖果的数目
        # queries[i] = [favoriteTypei, favoriteDayi, dailyCapi]
        # 即 喜欢的糖果下标， 喜欢的天数， 每天最多吃糖
        # 在每天吃 不超过 dailyCapi 颗糖果的前提下, 你可以在第 favoriteDayi 天吃到第 favoriteTypei 类糖果
        n, m = len(candiesCount), len(queries)
        # s[i] 表示前 i-1 类糖果的数量和
        s = [0 for _ in range(n + 1)]
        ans = [0 for _ in range(m)]
        for i in range(n):
            s[i + 1] = s[i] + candiesCount[i]
        for i in range(m):
            # min, max 表示喜欢那天最少要吃的糖果数量和最多能吃的糖果数量
            min, max = queries[i][1], queries[i][2] * (queries[i][1] + 1)
            # 只要(s[q], s[q + 1])与(min, max)区间有交集，即可在喜欢那天吃到喜欢的糖果
            ans[i] = (min < s[queries[i][0] + 1]) and (max > s[queries[i][0]])
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* Code language: C++ */
class Solution {
public:
    vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
        // candiesCount[i] 表示你拥有的第 i 类糖果的数目
        // queries[i] = [favoriteTypei, favoriteDayi, dailyCapi]
        // 即 喜欢的糖果下标， 喜欢的天数， 每天最多吃糖
        // 在每天吃 不超过 dailyCapi 颗糖果的前提下 你可以在第 favoriteDayi 天吃到第 favoriteTypei 类糖果
        int n = candiesCount.size(), m = queries.size();
        // s[i] 表示前 i-1 类糖果的数量和
        vector<long> s(n + 1);
        vector<bool> ans(m);
        for (int i = 0; i < n; ++i)
            s[i + 1] = s[i] + candiesCount[i];
        for (int i = 0; i < m; ++i) {
            // min, max 表示喜欢那天最少要吃的糖果数量和最多能吃的糖果数量
            long min = queries[i][1], max = (long)queries[i][2] * (queries[i][1] + 1);
            // 只要(s[q], s[q + 1])与(min, max)区间有交集，即可在喜欢那天吃到喜欢的糖果
            ans[i] = (min < s[queries[i][0] + 1]) && (max > s[queries[i][0]]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* Code language: Java */
class Solution {
    public boolean[] canEat(int[] candiesCount, int[][] queries) {
        // candiesCount[i] 表示你拥有的第 i 类糖果的数目
        // queries[i] = [favoriteTypei, favoriteDayi, dailyCapi]
        // 即 喜欢的糖果下标， 喜欢的天数， 每天最多吃糖
        // 在每天吃 不超过 dailyCapi 颗糖果的前提下, 你可以在第 favoriteDayi 天吃到第 favoriteTypei 类糖果
        int n = candiesCount.length, m = queries.length;
        // s[i] 表示前 i-1 类糖果的数量和
        long[] s = new long[n + 1];
        boolean[] ans = new boolean[m];
        for (int i = 0; i < n; ++i)
            s[i + 1] = s[i] + candiesCount[i];
        for (int i = 0; i < m; ++i) {
            // min, max 表示喜欢那天最少要吃的糖果数量和最多能吃的糖果数量
            long min = queries[i][1], max = (long) queries[i][2] * (queries[i][1] + 1);
            // 只要(s[q], s[q + 1])与(min, max)区间有交集，即可在喜欢那天吃到喜欢的糖果
            ans[i] = (min < s[queries[i][0] + 1]) && (max > s[queries[i][0]]);
        }
        return ans;
    }
}
--- ♥ end ♥ ---

欢迎关注我呀~