LEETCODE 1176. Diet Plan Performance 解题思路分析

题目大意:

健身计划评估

calories[i] 给出了健身者在第 i 天需要消耗的卡路里总量,对于每连续的 k 天,消耗的总卡路里为 T:

  • 如果 T < lower,那么这份计划相对糟糕,并失去 1 分;
  • 如果 T > upper,那么这份计划相对优秀,并获得 1 分;
  • 否则,分值不做变动。

请返回统计完所有 calories.length 天后得到的总分作为评估结果。

注意:总分可能是负数。

示例1:

输入:calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
输出:0
解释:calories[0], calories[1] < lower 而 calories[3], calories[4] > upper, 总分 = 0.

示例2:

输入:calories = [3,2], k = 2, lower = 0, upper = 1
输出:1
解释:calories[0] + calories[1] > upper, 总分 = 1.

示例3:

输入:calories = [6,5,0,0], k = 2, lower = 1, upper = 5
输出:0
解释:calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, 总分 = 0.

提示:

  • 1 <= k <= calories.length <= 10^5
  • 0 <= calories[i] <= 20000
  • 0 <= lower <= upper

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1176

解题思路分析:

将题目简单的翻译一下,就是要求出所有连续区间长度为k的和,如果和大于 upper 加一分,若小于 lower 减一分。求最后的总分数。

对于连续区间求和问题,我们应该想到使用前缀和数组preSum[],先遍历一遍数组,求出每个元素到首元素区间内所有元素之和,然后如果想求出任意区间的和,

sum[i,j] = preSum[j]-preSum[i-1];

实现代码:

public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
    int[] preSum = new int[calories.length+1]; // 前缀和数组
    for(int i=0;i<calories.length;i++){ // 计算前缀和
        preSum[i+1]=preSum[i]+calories[i];
    }
    int res=0; // 返回结果
    for(int i=k;i<preSum.length;i++){
        // 计算以下标i结尾并长度为k区间的和
        int consume = preSum[i]-preSum[i-k];
        // 若和小于lower,结果减一
        if(consume<lower) res--;
        // 若和大于upper,结果加一
        if(consume>upper) res++;
    }
    return res;
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 66.92% of Java online submissions for Diet Plan Performance.

Memory Usage: 45.8 MB, less than 100.00% of Java online submissions for Diet Plan Performance.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1176-diet-plan-performance-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。