3191. 使二进制数组全部等于 1 的最少操作次数 I

🟠   🔖  位运算 队列 数组 前缀和 滑动窗口  🔗 力扣 LeetCode

题目

You are given a binary array nums.

You can do the following operation on the array any number of times (possibly zero):

• Choose any 3 consecutive elements from the array and flip all of them.

Flipping an element means changing its value from 0 to 1, and from 1 to 0.

Return the minimum number of operations required to make all elements in nums equal to 1. If it is impossible, return -1.

Example 1:

Input: nums = [0,1,1,1,0,0]

Output: 3

Explanation:
We can do the following operations:

• Choose the elements at indices 0, 1 and 2. The resulting array is nums = [1, 0, 0, 1, 0, 0].
• Choose the elements at indices 1, 2 and 3. The resulting array is nums = [1, 1, 1, 0, 0, 0].
• Choose the elements at indices 3, 4 and 5. The resulting array is nums = [1, 1, 1, 1, 1, 1].

Example 2:

Input: nums = [0,1,1,1]

Output: -1

Explanation:
It is impossible to make all elements equal to 1.

Constraints:

• 3 <= nums.length <= 10^5
• 0 <= nums[i] <= 1

题目大意

给你一个二进制数组 nums 。

你可以对数组执行以下操作 任意 次（也可以 0 次）：

• 选择数组中 任意连续 3 个元素，并将它们 全部反转 。

反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。

请你返回将 nums 中所有元素变为 1 的 最少 操作次数。如果无法全部变成 1 ，返回 -1 。

示例 1：

输入： nums = [0,1,1,1,0,0]

输出： 3

解释：
我们可以执行以下操作：

• 选择下标为 0 ，1 和 2 的元素并反转，得到 nums = [1, 0, 0, 1, 0, 0] 。
• 选择下标为 1 ，2 和 3 的元素并反转，得到 nums = [1, 1, 1, 0, 0, 0] 。
• 选择下标为 3 ，4 和 5 的元素并反转，得到 nums = [1, 1, 1, 1, 1, 1] 。

示例 2：

输入： nums = [0,1,1,1]

输出： -1

解释：
无法将所有元素都变为 1 。

提示：

• 3 <= nums.length <= 10^5
• 0 <= nums[i] <= 1

解题思路

我们使用贪心算法，从左到右遍历数组：

1. 维护一个 flip 数组：flip[i] 表示索引 i 处是否经历了奇数次翻转。
2. 判断当前位置是否为 0：
   • 若 nums[i] 在当前翻转状态下是 0，则必须翻转 nums[i]、nums[i+1]、nums[i+2] 这三个元素，使 nums[i] 变 1。
   • 记录翻转次数 flipCount。
3. 遍历到 n-2 后检查最后两个元素：
   • 若 nums[n-2] 或 nums[n-1] 仍然是 0，则无法转化为全 1，返回 -1。

复杂度分析

• 时间复杂度：O(n)，遍历数组一次。
• 空间复杂度：O(n)，flip 数组占 O(n) 额外空间。
  • 目前的解法使用了 flip 数组来记录是否被翻转，实际上我们可以使用两个布尔变量 flip_0, flip_1 代替 flip 数组，从而优化空间复杂度至 O(1)。

代码

贪心算法

/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function (nums) {
	const n = nums.length;
	let flipCount = 0;
	let flip = new Array(n).fill(false);
	const isZero = (i) => (nums[i] == 0 && !flip[i]) || (nums[i] == 1 && flip[i]);
	for (let i = 0; i < n - 2; i++) {
		if (isZero(i)) {
			flip[i] = !flip[i];
			flip[i + 1] = !flip[i + 1];
			flip[i + 2] = !flip[i + 2];
			flipCount += 1;
		}
	}
	if (n - 2 >= 0 && (isZero(n - 2) || isZero(n - 1))) return -1;
	return flipCount;
};

压缩状态的贪心算法

/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function (nums) {
	const n = nums.length;
	let flipCount = 0;
	let flip_0 = false;
	let flip_1 = false;

	for (let i = 0; i < n - 2; i++) {
		if ((nums[i] === 0) !== flip_0) {
			flipCount++;
			flip_0 = !flip_1;
			flip_1 = true;
		} else {
			flip_0 = flip_1;
			flip_1 = false;
		}
	}

	// 最后两个元素检查是否能全部变为 1
	if ((nums[n - 2] === 0) !== flip_0 || (nums[n - 1] === 0) !== flip_1) {
		return -1;
	}

	return flipCount;
};

相关题目

题号	标题	题解	标签	难度	力扣
995	K 连续位的最小翻转次数		位运算 队列 数组 2+	🔴	🀄️ 🔗