leetcode daily question 1744. Can you eat your favorite candy on your favorite day?

My thoughts

For each query in the querie s, you can calculate the minimum number of meals (equal to days) and the maximum number of meals (equal to days) × The maximum number you can eat per day).

According to example 2, we can think that if we calculate the prefix sum of candies and the prefix sum of each corresponding query [0] position is just between the maximum and minimum, we can eat it!

Then there is the first problem! In the first example in the example, since the maxeat of [0,2,2] is 4 and the mineat is 2, 7 is obviously greater than 4. It is not in the interval [2,4], the query is determined to be false, but the actual situation is edible. In this case, the judgment conditions just formulated are problematic! After a series of tests and changes, there is no perfect result.

So I checked Problem solution

After reading it, I found that I missed a very important question! We eat candy from day 0. In this case, the judgment condition should be changed to mineat = day+1, maxeat = (day+1) * dailyCap;

var canEat = function (candiesCount, queries) {
  var prefix = [],
    answer = [];
  prefix[0] = candiesCount[0];
  for (let j = 1; j < candiesCount.length; j++) {
    prefix[j] = prefix[j - 1] + candiesCount[j];
  }
  // console.log(prefix);
  for (var i = 0; i < queries.length; i++) {
    answer[i] = canUEat(queries[i], prefix);
  }
  return answer;
};

var canUEat = function (querie, prefix) {
  // important
  var mineat = querie[1] + 1;
  var maxeat = (querie[1] + 1) * querie[2];
  if (querie[0] == 0 && prefix[querie[0]] >= maxeat) {
    return true;
  } else if (prefix[querie[0]] >= mineat && prefix[querie[0]] <= maxeat) {
    return true;
  } else {
    return false;
  }
};

Ah, is it right or wrong? Go and see it again Problem solution. !!!

Read the solution again

The meaning of the problem solution is that the candy you want most has one interval, and the candy you can eat has another interval. If the two intervals intersect, it proves that answer is true, otherwise it is false. I only thought that there was an interval for the candy I could eat, and then I looked at whether the last candy I wanted to eat was in this interval. I didn't think that as long as I ate what I wanted, I would win! The first candy you may want to eat is in the interval, but the last one is not in the interval.

/**
 * @param {number[]} candiesCount
 * @param {number[][]} queries
 * @return {boolean[]}
 */
var canEat = function (candiesCount, queries) {
  var prefix = [],
    answer = [];
  prefix[0] = candiesCount[0];
  for (let j = 1; j < candiesCount.length; j++) {
    prefix[j] = prefix[j - 1] + candiesCount[j];
  }
  // console.log(prefix[92]);
  for (var i = 0; i < queries.length; i++) {
    // answer[i] = canUEat(queries[i],prefix);
    var mineat = queries[i][1] + 1;
    var maxeat = (queries[i][1] + 1) * queries[i][2];
    // if(prefix[queries[i][0]] >= mineat && prefix[queries[i][0]] <= maxeat){answer[i] = true;}
    // else if(queries[i][0] == 0 && prefix[queries[i][0]]>=maxeat){answer[i] = true;}
    // else{answer[i] = false;}
    var prefixMin = queries[i][0] == 0 ? 1 : prefix[queries[i][0] - 1] + 1;
    var prefixMax = prefix[queries[i][0]];
    if (mineat > prefixMax || maxeat < prefixMin) {
      answer[i] = false;
    } else {
      answer[i] = true;
    }
  }
  return answer;
};

In addition, one was found Problem solution Very good

this Problem solution Although it is python language, the picture is very good and very clear! Worth learning!

Finally, complexity analysis:

Time complexity: O ( n + q ) O(n+q) O(n+q)， O ( n ) O(n) O(n) is the time complexity of calculating the prefix sum, O ( q ) O(q) O(q) is the time complexity of calculating each answer.
Space complexity: O ( n ) O(n) O(n), save the prefix and array. N is the length of candiesCount.