This is the first day of my participation in Gwen Challenge

Today is Children’s Day! Happy holidays to you all! Let’s brush together!

Topic describes

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]] 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. Source: LeetCode Link: https://leetcode-cn.com/problems/can-you-eat-your-favorite-candy-on-your-favorite-day Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thought analysis

  • This question is quite long and requires careful reading to understand the meaning of the question.
  • A. favoriteType B. favoriteType C. favoriteType D. favoriteType Thus, a range can be obtained, the maximum number of sweets is favoriteDay + 1, and the maximum number of sweets is favoriteDay + 1 * dailyCap. The cumulative number of sweets within this range satisfies the condition, and returns true;

AC code

public class DayCode {
    public static void main(String[] args) {
        int[] candiesCount = new int[] {7.4.5.3.8};
        int[][] queries = new int[] [] {{0.2.2}, {4.2.4}, {2.13.1000000000}};
        boolean[] ans = new DayCode().canEat(candiesCount, queries);
        System.out.println(Arrays.toString(ans));

        int[] candiesCount1 = new int[] {5.2.6.4.1};
        int[][] queries1 = new int[] [] {{3.1.2}, {4.10.3}, {3.10.100}, {4.100.30}, {1.3.1}};
        boolean[] ans1 = new DayCode().canEat(candiesCount1, queries1);
        System.out.println(Arrays.toString(ans1));
    }

    public boolean[] canEat(int[] candiesCount, int[][] queries) {
        int m = candiesCount.length;
        long[] sum = new long[m];
        sum[0] = candiesCount[0];
        for (int i = 1; i < m; ++i) {
            sum[i] = sum[i - 1] + candiesCount[i];
        }

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

            long x1 = favoriteDay + 1;
            long y1 = (long) (favoriteDay + 1) * dailyCap;
            long x2 = favoriteType == 0 ? 1 : sum[favoriteType - 1] + 1;
            longy2 = sum[favoriteType]; ans[i] = ! (x1 > y2 || y1 < x2); }returnans; }}Copy the code

Submit the test

AC smoothly!

conclusion

  • The time complexity of the above algorithm code is O(n) and the space complexity is O(1).
  • The method of prefix sum is used to calculate the number of candies. Prefix sum is an important preprocessing, which can greatly reduce the time complexity of query.
  • The prefix sum code is very classic, master can improve the efficiency of solving problems.
  • Stick to the daily question, come on!