关于后端:面试高频题难度-155简单前缀和经典运用

这是 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 多平台公布

关于后端:面试高频题难度-155简单前缀和经典运用

题目形容

根本剖析

前缀和

最初