共计 2452 个字符，预计需要花费 7 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 1744. 你能在你最喜爱的那天吃到你最喜爱的糖果吗？，难度为 中等 。
Tag :「前缀和」
给你一个下标从 0 开始的正整数数组 candiesCount，其中 candiesCount[i] 示意你领有的第 i 类糖果的数目。
同时给你一个二维数组 queries，其中 $queries[i] = [favoriteType_{i}, favoriteDay_{i}, dailyCap_{i}]$。
你依照如下规定进行一场游戏：
- 你从第
0天开始吃糖果。 - 你在吃完 所有 第
i - 1类糖果之前，不能 吃任何一颗第i类糖果。 - 在吃完所有糖果之前，你必须每天 至多 吃 一颗 糖果。
请你构建一个布尔型数组 answer，满足 answer.length == queries.length。answer[i] 为 true 的条件是：在每天吃 不超过 $dailyCap_i$ 颗糖果的前提下，你能够在第 $favoriteDay_i$ 天吃到第 $favoriteType_i$ 类糖果；否则 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 <= favoriteType_{i} < candiesCount.length$
- $0 <= favoriteDay_{i} <= 10^9$
- $1 <= dailyCap_{i} <= 10^9$
根本剖析
依据题意，在解决某个询问时，每天的吃糖数量为 $[1, queries[i][2]]$，因而咱们能够计算出「最早 / 最晚」吃到第 $queries[i][0]$ 类糖果的工夫，而后判断 $queries[i][1]$ 是否落在范畴内，若落在范畴内返回则有 $ans[i]$ 为 True，否则为 False。
前缀和
问题转换为如何疾速求得「最早 / 最晚」吃到第 $queries[i][0]$ 类糖果的工夫。
咱们须要先预处理出 $candiesCount$ 的前缀和数组 $sum$（下标从 $1$ 开始），不便疾速求得第 $i$ 类糖果之前有多少糖果。
为了不便，在解决某个询问时，咱们令 $t = queries[i][0]，d = queries[i][1] + 1，c = queries[i][2]$。其中 $d = queries[i][1] + 1$ 是因为题目天数是从 $0$ 开始计算，而咱们的计算是从 $1$ 开始。
而后计算「最早 / 最晚」吃到第 $t$ 类糖果的工夫：
- 最早工夫（第一颗 $t$ 类糖的最早工夫）：当以最大速率 $c$ 吃糖时，能够在最早工夫内吃到糖。工夫为吃掉第 $t$ 类糖果 后面 的所有糖果的工夫（下取整）加 $1$：
$$
\left \lfloor \frac{sum[t]}{c} \right \rfloor + 1
$$
- 最晚工夫（最初一颗 $t$ 类糖的最晚工夫）：当以最小速率 $1$ 吃糖时，能够计算出最晚吃糖工夫。工夫为吃掉所有 $t$ 类糖的工夫：
$$
sum[t + 1]
$$
代码：
class Solution {public boolean[] canEat(int[] cs, int[][] qs) {
int n = qs.length, m = cs.length;
boolean[] ans = new boolean[n];
long[] sum = new long[m + 1];
for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] + cs[i - 1];
for (int i = 0; i < n; i++) {int t = qs[i][0], d = qs[i][1] + 1, c = qs[i][2];
long a = sum[t] / c + 1, b = sum[t + 1];
ans[i] = a <= d && d <= b;
}
return ans;
}
}- 工夫复杂度：
cs数组的长度为n，qs数组的长度为m。预处理前缀和的复杂度为 $O(n)$；解决每个询问的复杂度为 $O(1)$，共有 $m$ 个询问，复杂度为 $O(m)$。整体复杂度为 $O(\max(n, m))$ - 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.1744 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布