Prefix and solve eat 🍭 problem

This is the first day of my participation in Gwen Challenge

Topic describes

This is 1744 on LeetCode. Can you have your favorite candy on your favorite day? The difficulty is medium.

Tag: prefix and

Give you an array of positive integers with subscripts starting from 0, candiesCount[I], where candiesCount[I] represents the number of class I candies you own. Queries [I] = [favoriteTypei, favoriteDayi, dailyCapi]

You play a game according to these rules:

• You start eating candy on day 0.
• You should not eat any Category I candy until you have eaten all category I-1 candy.
• You must eat at least one candy a day before eating all the candy.

Create a Boolean array answer that answers. Length == queries.length. Answer [I] iS true if you eat no more than dailyCapi candy every day. You can eat favoriteTypei candy on favoriteDayi day. Otherwise answer[I] is false. Note that you can eat different types of candy on the same day as long as you meet the second of the three rules above.

Please return the array answer you got.

Example 1:

Enter: candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]] 1- Eat 2 sweets on day 0 (type 0), 2 sweets on day 1 (type 0), and on day 2 you can eat sweets of type 0. 2- You can't eat more than four candies a day. Even if you eat 4 sweets on day 0 (type 0) and 4 sweets on day 1 (type 0 and type 1), you will not be able to eat sweets of type 4 on day 2. In other words, you can't eat category 4 candy the next day under the limit of 4 candy a day. 3- If you eat 1 candy every day, you can eat type 2 candy on day 13.Copy the code

Example 2:

Input: candiesCount =,2,6,4,1 [5], the queries = [,1,2 [3], [4,10,3], [3,10,100], 4100, 30], [[1,3,1]] output: [false,true,true,false,false]Copy the code

Tip:

• 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$

Fundamental analysis

[queries[I][2]][1,queries[I][2]][1,queries[I][2]][1,queries[I][2]] Queries [I][I][I][0] [I][I][0] [I][0] [I][0] Ans [I]ans[I]ans[I] is True if it falls within a range, otherwise False.

The prefix and

Queries [I][0]queries[I][0] Queries [I][0] Queries [I][0]queries[I][0]

We need to pretreatment sumsumsum candiesCountcandiesCountcandiesCount prefix and array (subscript since 111), the obtained rapid iii class before how many candy sweets.

Queries [I][0], d=queries[I][1]+1, C =queries[I][2]t =queries[I][0], d=queries[I][1]+1, C = the queries [2] [I] t = the queries [I] [0], d = the queries [I] [1] + 1, c = the queries [I] [2]. D =queries[I][1]+ 1D =queries[I][1]+ 1D =queries[I][1]+1d =queries[I][1]+1 =queries[I][1]+1

Then calculate the “earliest/latest” time to eat the TTT type candy:

• Earliest time (the earliest time of the first TTT sugar) : when sugar is eaten at the maximum rate CCC, sugar can be eaten in the earliest time. Time is the time to eat all the candies in front of TTT category (rounded down) plus 111:

• Last time (last time of TTT type candy) : When eating candy at the minimum rate 111, the last time to eat candy can be calculated. Time is the time to eat all TTT sugars:

Code:

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;
        }
        returnans; }}Copy the code

• Time complexity:csThe length of the array isn.qsThe length of the array ism. The complexity of preprocessing prefix sum is
  $O(n)$; The complexity of processing each query is
  $O(1)$, a total of
  $m$Query, the complexity is
  $O(m)$. The overall complexity is
  $O(\max(n, m))$
• Space complexity: O(n)O(n)O(n)

The last

This is the No.1744 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.