class Solution {
public:
long long numberOfWeeks(vector<int>& milestones) {
}
};
1953. 你可以工作的最大周数
给你 n 个项目，编号从 0 到 n - 1 。同时给你一个整数数组 milestones ，其中每个 milestones[i] 表示第 i 个项目中的阶段任务数量。
你可以按下面两个规则参与项目中的工作：
一旦所有项目中的全部阶段任务都完成，或者仅剩余一个阶段任务都会导致你违反上面的规则，那么你将 停止工作 。注意，由于这些条件的限制，你可能无法完成所有阶段任务。
返回在不违反上面规则的情况下你 最多 能工作多少周。
示例 1：
输入：milestones = [1,2,3] 输出：6 解释：一种可能的情形是： - 第 1 周，你参与并完成项目 0 中的一个阶段任务。 - 第 2 周，你参与并完成项目 2 中的一个阶段任务。 - 第 3 周，你参与并完成项目 1 中的一个阶段任务。 - 第 4 周，你参与并完成项目 2 中的一个阶段任务。 - 第 5 周，你参与并完成项目 1 中的一个阶段任务。 - 第 6 周，你参与并完成项目 2 中的一个阶段任务。 总周数是 6 。
示例 2：
输入：milestones = [5,2,1] 输出：7 解释：一种可能的情形是： - 第 1 周，你参与并完成项目 0 中的一个阶段任务。 - 第 2 周，你参与并完成项目 1 中的一个阶段任务。 - 第 3 周，你参与并完成项目 0 中的一个阶段任务。 - 第 4 周，你参与并完成项目 1 中的一个阶段任务。 - 第 5 周，你参与并完成项目 0 中的一个阶段任务。 - 第 6 周，你参与并完成项目 2 中的一个阶段任务。 - 第 7 周，你参与并完成项目 0 中的一个阶段任务。 总周数是 7 。 注意，你不能在第 8 周参与完成项目 0 中的最后一个阶段任务，因为这会违反规则。 因此，项目 0 中会有一个阶段任务维持未完成状态。
提示：
n == milestones.length1 <= n <= 1051 <= milestones[i] <= 109原站题解
rust 解法, 执行用时: 7 ms, 内存消耗: 3.6 MB, 提交时间: 2024-05-16 09:18:41
impl Solution {
pub fn number_of_weeks(milestones: Vec<i32>) -> i64 {
// 耗时最长工作所需周数
let mut longest = 0;
let mut rest: i64 = 0;
for &count in milestones.iter() {
longest = std::cmp::max(longest, count);
rest += count as i64;
}
// 其余工作共计所需周数
rest -= longest as i64;
if longest as i64 > rest + 1 {
// 此时无法完成所耗时最长的工作
rest * 2 + 1
} else {
// 此时可以完成所有工作
longest as i64 + rest
}
}
}
javascript 解法, 执行用时: 77 ms, 内存消耗: 62.4 MB, 提交时间: 2024-05-16 09:18:28
/**
* @param {number[]} milestones
* @return {number}
*/
var numberOfWeeks = function(milestones) {
// 耗时最长工作所需周数
const longest = Math.max(...milestones);
// 其余工作共计所需周数
const rest = milestones.reduce((acc, cur) => acc + cur, 0) - longest;
if (longest > rest + 1) {
// 此时无法完成所耗时最长的工作
return rest * 2 + 1;
} else {
// 此时可以完成所有工作
return longest + rest;
}
};
java 解法, 执行用时: 2 ms, 内存消耗: 54.6 MB, 提交时间: 2024-05-16 09:18:12
class Solution {
public long numberOfWeeks(int[] milestones) {
int longest = milestones[0]; // 耗时最长工作所需周数
long rest = 0;
for (int count : milestones) {
longest = Math.max(longest, count);
rest += count;
}
// 其余工作共计所需周数
rest -= longest;
if (longest > rest + 1) {
// 此时无法完成所耗时最长的工作
return rest * 2 + 1;
} else {
// 此时可以完成所有工作
return longest + rest;
}
}
}
python3 解法, 执行用时: 120 ms, 内存消耗: 27.8 MB, 提交时间: 2023-09-06 23:38:08
class Solution:
def numberOfWeeks(self, milestones: List[int]) -> int:
sum_, max_ = 0, 0
for v in milestones:
sum_ += v
if v > max_:
max_ = v
if sum_ < max_*2:
return (sum_-max_)*2 + 1
return sum_
cpp 解法, 执行用时: 112 ms, 内存消耗: 73.8 MB, 提交时间: 2023-09-06 23:36:31
using LL = long long;
class Solution {
public:
// 由于要求不能连续两周参加同一个项目中的任务，所以我们直接将任务最多的项目求出来，然后与剩余的项目进行交叉完成工作
// 若 mx>sum-mx，那么mx中必定有项目剩余，那么我们最多做(sum-mx)*2+1个任务（交叉做任务，最后多做mx中的一个任务）
// 若 mx<=sum-mx，那么每次选两个任务最多的项目进行配对，最终能将所有任务进行配对完成；
long long numberOfWeeks(vector<int>& a) {
LL sum=accumulate(a.begin(),a.end(),0LL);
LL mx=*max_element(a.begin(),a.end());
return mx>sum-mx?(sum-mx)*2+1:sum;
}
};
golang 解法, 执行用时: 100 ms, 内存消耗: 9.2 MB, 提交时间: 2023-09-06 23:36:16
// 贪心的方案是，每周选择一个剩余任务数最多的项目（且与上一周不同）
func numberOfWeeks(milestones []int) int64 {
sum, max := 0, 0
for _, v := range milestones {
sum += v
if v > max {
max = v
}
}
if sum < max*2 {
return int64((sum-max)*2 + 1)
}
return int64(sum)
}