leetcode
leetcode 1101 ~ 1150
健身计划评估

健身计划评估

难度:

标签:

题目描述

代码结果

运行时间: 36 ms, 内存: 26.8 MB


/*
 * Leetcode 1176: 健身计划评估
 * 题目思路:
 * 给定一个整数数组 calories 和一个整数 k,
 * 求在任意连续的 k 天中,卡路里总和严格大于 upper 的子数组数量和严格小于 lower 的子数组数量之和。
 * 
 * 使用Java Stream实现:
 * 1. 使用IntStream对数组进行滑动窗口处理。
 * 2. 通过sum函数计算每个窗口的卡路里总和。
 * 3. 过滤出总和大于 upper 或者小于 lower 的窗口。
 * 4. 计数并返回结果。
 */
import java.util.stream.IntStream;

public class Solution {
    public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
        return (int) IntStream.rangeClosed(0, calories.length - k)
                .mapToObj(i -> IntStream.range(i, i + k).map(j -> calories[j]).sum())
                .filter(sum -> sum > upper || sum < lower)
                .count();
    }
}

解释

方法:

本题解采用滑动窗口和前缀和的方法来解决问题。首先计算出所有卡路里的前缀和数组 cumsum,其中 cumsum[i] 表示从开始到第 i-1 个元素的卡路里总和。这样,任意长度为 k 的子数组的卡路里和可以通过 cumsum[i+k] - cumsum[i] 快速计算得出,避免了重复计算。接着,遍历数组,对于每个长度为 k 的连续子数组,比较其卡路里总和与给定的 lower 和 upper 值,根据比较结果更新得分。如果总和小于 lower,则将 score 减一,如果大于 upper,则将 score 加一。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么在构建前缀和数组时,数组的长度设置为 `n + k` 而不是仅为 `n`?
在题解中,前缀和数组的长度错误地设置为 `n + k`,实际上这是不必要的。前缀和数组的长度应当只需要为 `n + 1`,这是为了保证能够包括从第0个元素到第n-1个元素的所有前缀和,且使用从1开始的索引方式来方便计算。设置为 `n + k` 可能是对其他类型问题的通用处理误用,或者是错误,因为在这个特定问题中我们只需要计算到 `cumsum[n]`,即从第0个元素到最后一个元素的总和。
🦆
在计算子数组卡路里总和时,使用 `cumsum[i + k] - cumsum[i]` 表达式的正确性是基于什么假设?
该表达式的正确性基于前缀和数组的定义,即 `cumsum[i]` 表示从数组开始到第i-1个元素的卡路里总和。因此,`cumsum[i + k]` 表示从数组开始到第i+k-1个元素的总和。当我们计算 `cumsum[i + k] - cumsum[i]` 时,实际上得到的是第i个元素到第i+k-1个元素的总和,即长度为k的子数组的卡路里总和。这个计算是基于索引从0开始连续的数组序列这一假设。
🦆
前缀和数组 `cumsum` 的初始化为什么从索引1开始计算而非索引0?
在前缀和数组中,`cumsum[0]` 被初始化为0是为了方便计算任意子区间的和,包括从数组第一个元素开始的区间。从索引1开始计算是因为,`cumsum[1]` 代表第一个元素的值,`cumsum[2]` 代表第一个和第二个元素的总和,依此类推。这种初始化方式使得任何从第i个到第j个元素的子数组和都可以简单地通过 `cumsum[j+1] - cumsum[i]` 来计算,其中i和j是基于0的索引。
🦆
如何处理数组 `calories` 的长度小于 k 的情况,这种情况下如何计算得分?
如果数组 `calories` 的长度小于 k,那么根据题目逻辑,不存在长度为 k 的子数组,因此不能形成一个有效的评估窗口来比较与 lower 和 upper 的值。在这种情况下,可以直接返回得分为0,因为没有任何子数组可以用来评估得分。这应该在算法实现的开始部分进行检查,如果 `n < k`,直接返回0。

相关问题