Leetcode -1744- Can you eat your favorite candy on your favorite day?

[Blog link]

A path to learning at 🐔

[B].

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 the following 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]] output: [true,false,true] prompt: 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. 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] tip:  1 <= candiesCount.length <= 105 1 <= candiesCount[i] <= 105 1 <= queries.length <= 105 queries[i].length == 3 0 <= favoriteTypei < candiesCount.length 0 <= favoriteDayi <= 109 1 <= dailyCapi <= 109Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: brute force cracking

• Queries [I][0]
• All (queries[I][0]-1) candies should be eaten without exceeding queries[I][3]
• The first step is to find the sum of the first n types of candy
• Then according to the queries [I] [2] * (the queries [I] [1] + 1) > = (map) get (the queries [0] – [I] 1) + 1 | | 1)
• At the same time need to make sure that the queries [1] – [I] 1 < = (map) get (the queries [I] [0]) – 1)

public boolean[] canEat(int[] candiesCount, int[][] queries) {
            Map<Integer, Long> map = new HashMap<>();
            long sum = 0;
            for (int i = 0; i < candiesCount.length; i++) {
                sum += candiesCount[i];
                map.put(i, sum);
            }
            boolean[] res = new boolean[queries.length];
            for (int i = 0; i < res.length; i++) {
                // Does not consider the numerical overbounds problem + the problem trap starts eating candy from day 0
                // Long is required
                // Eat as much as you can each day, with the first type of candy you can eat
                long maxEaten = queries[i][2] * (long) (queries[i][1] + 1);
                If the candy type is 0, eat more than 1 candy. If the candy type is 0, eat more than 1 candy. If the candy type is 0, eat more than 1 candy
                long tempSum1 = queries[i][0] = =0 ? 1 : map.get(queries[i][0] - 1) + 1;
                // Eat only one meal per day
                Map.get (target) >= (queries[I][1] + 1)
                res[i] = maxEaten >= tempSum1 && map.get(queries[i][0]) >= (queries[i][1] + 1);
            }
            return res;
        }
Copy the code

Time complexity O(n+c) n indicates the length of **candiesCount[], and c indicates the length of queries[][]**