同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
你的好友是一位健身爱好者。前段日子,他给自己制定了一份健身计划。现在想请你帮他评估一下这份计划是否合理。
他会有一份计划消耗的卡路里表,其中 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
我们先预处理出长度为 $n+1$ 的前缀和数组 $s$,其中 $s[i]$ 表示前 $i$ 天的卡路里总和。
然后遍历前缀和数组 $s$,对于每个位置 $i$,计算 $s[i+k]-s[i]$,即为第 $i$ 天开始的连续 $k$ 天的卡路里总和。根据题意,对于每个 $s[i+k]-s[i]$,判断值与 $lower$ 和 $upper$ 的关系,更新答案即可。
时间复杂度 $O(n)$,空间复杂度 $O(n)$。其中 $n$ 为数组 calories
的长度。
class Solution:
def dietPlanPerformance(
self, calories: List[int], k: int, lower: int, upper: int
) -> int:
s = list(accumulate(calories, initial=0))
ans, n = 0, len(calories)
for i in range(n - k + 1):
t = s[i + k] - s[i]
if t < lower:
ans -= 1
elif t > upper:
ans += 1
return ans
class Solution {
public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
int n = calories.length;
int[] s = new int[n + 1];
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + calories[i];
}
int ans = 0;
for (int i = 0; i < n - k + 1; ++i) {
int t = s[i + k] - s[i];
if (t < lower) {
--ans;
} else if (t > upper) {
++ans;
}
}
return ans;
}
}
class Solution {
public:
int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {
int n = calories.size();
int s[n + 1];
s[0] = 0;
for (int i = 0; i < n; ++i) {
s[i + 1] = s[i] + calories[i];
}
int ans = 0;
for (int i = 0; i < n - k + 1; ++i) {
int t = s[i + k] - s[i];
if (t < lower) {
--ans;
} else if (t > upper) {
++ans;
}
}
return ans;
}
};
func dietPlanPerformance(calories []int, k int, lower int, upper int) (ans int) {
n := len(calories)
s := make([]int, n+1)
for i, x := range calories {
s[i+1] = s[i] + x
}
for i := 0; i < n-k+1; i++ {
t := s[i+k] - s[i]
if t < lower {
ans--
} else if t > upper {
ans++
}
}
return
}
function dietPlanPerformance(calories: number[], k: number, lower: number, upper: number): number {
const n = calories.length;
const s: number[] = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + calories[i];
}
let ans = 0;
for (let i = 0; i < n - k + 1; ++i) {
const t = s[i + k] - s[i];
if (t < lower) {
--ans;
} else if (t > upper) {
++ans;
}
}
return ans;
}
我们维护一个长度为 $k$ 的滑动窗口,窗口内元素之和记为 $s$。如果 $s \lt lower$,则分数减 $1$;如果 $ s \gt upper$,则分数加 $1$。
时间复杂度 $O(n)$,其中 $n$ 为数组 calories
的长度。空间复杂度 $O(1)$。
class Solution:
def dietPlanPerformance(
self, calories: List[int], k: int, lower: int, upper: int
) -> int:
def check(s):
if s < lower:
return -1
if s > upper:
return 1
return 0
s, n = sum(calories[:k]), len(calories)
ans = check(s)
for i in range(k, n):
s += calories[i] - calories[i - k]
ans += check(s)
return ans
class Solution {
public int dietPlanPerformance(int[] calories, int k, int lower, int upper) {
int s = 0, n = calories.length;
for (int i = 0; i < k; ++i) {
s += calories[i];
}
int ans = 0;
if (s < lower) {
--ans;
} else if (s > upper) {
++ans;
}
for (int i = k; i < n; ++i) {
s += calories[i] - calories[i - k];
if (s < lower) {
--ans;
} else if (s > upper) {
++ans;
}
}
return ans;
}
}
class Solution {
public:
int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {
int n = calories.size();
int s = accumulate(calories.begin(), calories.begin() + k, 0);
int ans = 0;
if (s < lower) {
--ans;
} else if (s > upper) {
++ans;
}
for (int i = k; i < n; ++i) {
s += calories[i] - calories[i - k];
if (s < lower) {
--ans;
} else if (s > upper) {
++ans;
}
}
return ans;
}
};
func dietPlanPerformance(calories []int, k int, lower int, upper int) (ans int) {
n := len(calories)
s := 0
for _, x := range calories[:k] {
s += x
}
if s < lower {
ans--
} else if s > upper {
ans++
}
for i := k; i < n; i++ {
s += calories[i] - calories[i-k]
if s < lower {
ans--
} else if s > upper {
ans++
}
}
return
}
function dietPlanPerformance(calories: number[], k: number, lower: number, upper: number): number {
const n = calories.length;
let s = calories.slice(0, k).reduce((a, b) => a + b);
let ans = 0;
if (s < lower) {
--ans;
} else if (s > upper) {
++ans;
}
for (let i = k; i < n; ++i) {
s += calories[i] - calories[i - k];
if (s < lower) {
--ans;
} else if (s > upper) {
++ans;
}
}
return ans;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。