This is the first day of my participation in the more text Challenge. For more details, see: activity link

2021-06-01 LeetCode

Link: leetcode-cn.com/problems/ca…

Tags: Math, prefix and

The title

You are given an array of positive integers starting at 0, candiesCount[I], where candiesCount[I] represents the number of category I candies you have. Queries [I] = [favoriteTypei, favoriteDayi, dailyCapi].

You play a game according to the following rules:

  • You start eating candy on day 0.
  • You must not eat any class I candy until you have eaten all class I-1 candy.
  • You must eat at least one candy every day before you eat all of them.

Please construct a Boolean array answer that satisfies answer.length == queries.length. Answer [I] the favoritetypei-type candy in the day of the day without eating more than one dailyCapi candy. Otherwise, answer[I] is false. Note that you can eat different types of candy on the same day as long as the second of the three rules above is met.

Please return the obtained array answer.

Enter: candiesCount = [7.4.5.3.8], queries = [[0.2.2], [4.2.4], [2.13.1000000000[] Output: [true.false.true] :1- in the first0Day to eat2Candy (type0), the first1Day to eat2Candy (type0), the first2Day you can eat type0The candy.2- You eat at most every day4Candy. Even if the first0Day to eat4Candy (type0), the first1Day to eat4Candy (type0And type1), and you can't do it at no2Day to eat type4The candy. In other words, you can't eat it every day4The limit of candy in the first2Day to eat first4Kind of candy.3- If you eat every day1A piece of candy, you can have at no13Day to eat type2The candy. Enter: candiesCount = [5.2.6.4.1], queries = [[3.1.2], [4.10.3], [3.10.100], [4.100.30], [1.3.1[] Output: [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
Copy the code

Analysis of the

It’s a little bit long, so I need to read it a few more times. In each case, you are given a candy type favoriteTypei. In each case, you are given a candy type favoriteDayi. In each case, you are given a number of days. The favoritetypei-like candy is not favoritetypei. return true if the candy is favoritetypei. otherwise, return false.

Now that you understand what it means, you can solve it. Here you can use the prefix and figure out the total number of sweets in the first N types first, so you can avoid double counting.

The next step is to consider whether a given type of candy can be eaten within a given number of days, considering the boundary case:

  • One candy a day. If the favoriteTypei is eaten all in one day, the favoriteDayi day is not the favoriteTypei day.
  • If you do not finish the favoritetyPEI-1 candy in the favoriteDayi day, then the favoritetypei-1 candy is not in the favoriteDayi.
  • In other cases, the favoriteTypei candy can be eaten on favoriteDayi day.

Note that int overflows should be considered. Because 10^10 is out of the range of int.

coding

class Solution {
    public boolean[] canEat(int[] candiesCount, int[][] queries) {
        boolean[] answer = new boolean[queries.length];
        long[] sum = new long[candiesCount.length + 1];

        for (int i = 1; i <= candiesCount.length; i++) {
            sum[i] = sum[i - 1] + candiesCount[i - 1];
        }

        for (int i = 0; i < queries.length; i++) {
            int favoriteType = queries[i][0] + 1;
            int favoriteDay = queries[i][1];
            int dailyCap = queries[i][2];

            /** * The favoriteType candy */ The favoriteType candy */ The favoriteType candy */
            if (sum[favoriteType] <= favoriteDay) {
                answer[i] = false;
                continue;
            }

            // Do not finish the favoriteType-1 candy during favoriteDay. Do not finish the favoriteType-1 candy
            if ((sum[favoriteType - 1] / dailyCap) >= (favoriteDay + 1)) {
                answer[i] = false;
                continue;
            }
            answer[i] = true;
        }

        returnanswer; }}Copy the code

O(m + n) in time, O(n) in space