class Solution {
public:
int minimumLevels(vector<int>& possible) {
}
};
100250. 得到更多分数的最少关卡数目
给你一个长度为 n 的二进制数组 possible 。
莉叩酱和冬坂五百里正在玩一个有 n 个关卡的游戏，游戏中有一些关卡是 困难 模式，其他的关卡是 简单 模式。如果 possible[i] == 0 ，那么第 i 个关卡是 困难 模式。一个玩家通过一个简单模式的关卡可以获得 1 分，通过困难模式的关卡将失去 1 分。
游戏的一开始，莉叩酱将从第 0 级开始 按顺序 完成一些关卡，然后冬坂五百里会完成剩下的所有关卡。
假设两名玩家都采取最优策略，目的是 最大化 自己的得分，莉叩酱想知道自己 最少 需要完成多少个关卡，才能获得比冬坂五百里更多的分数。
请你返回莉叩酱获得比冬坂五百里更多的分数所需要完成的 最少 关卡数目，如果 无法 达成，那么返回 -1 。
注意，每个玩家都至少需要完成 1 个关卡。
示例 1：
输入：possible = [1,0,1,0]
输出：1
解释：
我们来看一下莉叩酱可以完成的关卡数目：
莉叩酱需要完成至少一个关卡获得更多的分数。
示例 2：
输入：possible = [1,1,1,1,1]
输出：3
解释：
我们来看一下莉叩酱可以完成的关卡数目：
莉叩酱需要完成至少三个关卡获得更多的分数。
示例 3：
输入：possible = [0,0]
输出：-1
解释：
两名玩家只能各完成 1 个关卡，莉叩酱完成关卡 0 得到 -1 分，冬坂五百里完成关卡 1 得到 -1 分。两名玩家得分相同，所以莉叩酱无法得到更多分数。
提示：
2 <= n == possible.length <= 105possible[i] 要么是 0 要么是 1 。原站题解
rust 解法, 执行用时: 28 ms, 内存消耗: 2.7 MB, 提交时间: 2024-07-19 09:20:17
impl Solution {
pub fn minimum_levels(possible: Vec<i32>) -> i32 {
// s = cnt1 - cnt0 = cnt1 - (n - cnt1) = cnt1 * 2 - n
let s = possible.iter().sum::<i32>() * 2 - possible.len() as i32;
let mut pre = 0;
for i in 0..possible.len() - 1 {
pre += if possible[i] == 1 { 2 } else { -2 };
if pre > s {
return (i + 1) as _;
}
}
-1
}
}
javascript 解法, 执行用时: 140 ms, 内存消耗: 63.7 MB, 提交时间: 2024-07-19 09:19:26
/**
* @param {number[]} possible
* @return {number}
*/
var minimumLevels = function(possible) {
const n = possible.length;
// s = cnt1 - cnt0 = cnt1 - (n - cnt1) = cnt1 * 2 - n
const s = _.sum(possible) * 2 - n;
let pre = 0;
for (let i = 0; i < n - 1; i++) {
pre += possible[i] ? 2 : -2;
if (pre > s) {
return i + 1;
}
}
return -1;
};
golang 解法, 执行用时: 256 ms, 内存消耗: 8.1 MB, 提交时间: 2024-03-31 21:49:28
func minimumLevels(possible []int) int {
// cnt1 - cnt0 = cnt1 - (n - cnt1) = cnt1 * 2 - n
n := len(possible)
s := 0
for _, x := range possible {
s += x
}
s = s*2 - n
pre := 0
for i, x := range possible[:n-1] {
pre += x*4 - 2
if pre > s {
return i + 1
}
}
return -1
}
python3 解法, 执行用时: 133 ms, 内存消耗: 20.5 MB, 提交时间: 2024-03-31 21:49:13
class Solution:
def minimumLevels(self, possible: List[int]) -> int:
# cnt1 - cnt0 = cnt1 - (n - cnt1) = cnt1 * 2 - n
s = sum(possible) * 2 - len(possible)
pre = 0
for i, x in enumerate(possible[:-1]):
pre += 2 if x else -2
if pre > s:
return i + 1
return -1
java 解法, 执行用时: 4 ms, 内存消耗: 58.3 MB, 提交时间: 2024-03-31 21:48:59
class Solution {
public int minimumLevels(int[] possible) {
// cnt1 - cnt0 = cnt1 - (n - cnt1) = cnt1 * 2 - n
int n = possible.length;
int s = 0;
for (int x : possible) {
s += x;
}
s = s * 2 - n;
int pre = 0;
for (int i = 0; i < n - 1; i++) {
pre += possible[i] == 1 ? 2 : -2;
if (pre > s) {
return i + 1;
}
}
return -1;
}
}
cpp 解法, 执行用时: 188 ms, 内存消耗: 254.2 MB, 提交时间: 2024-03-31 21:48:44
class Solution {
public:
int minimumLevels(vector<int> &possible) {
// cnt1 - cnt0 = cnt1 - (n - cnt1) = cnt1 * 2 - n
int n = possible.size();
int s = accumulate(possible.begin(), possible.end(), 0) * 2 - n;
int pre = 0;
for (int i = 0; i < n - 1; i++) {
pre += possible[i] ? 2 : -2;
if (pre > s) {
return i + 1;
}
}
return -1;
}
};