Medium

题目描述

给你一个二进制数组 nums。

你可以对数组执行以下操作任意次（可能为零次）：

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

翻转一个元素意味着将其值从 0 变为 1，从 1 变为 0。

返回使 nums 中所有元素都等于 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

提示：

  • 如果 nums[0] 是 0，那么改变它为 1 的唯一方法是对数组的前 3 个元素执行操作。
  • 将 nums[0] 改为 1 后，对剩余数组使用相同逻辑。

解题思路

解题思路

这是一个贪心算法题目。关键观察是：我们必须从左到右处理数组，因为一旦某个位置变成1，我们不希望再去改变它。

核心思想

  1. 贪心策略：从左到右扫描数组，遇到0就必须进行翻转操作
  2. 唯一选择：当 nums[i] == 0 时，我们只能选择从位置 i 开始的连续3个元素进行翻转
  3. 边界条件：如果在位置 n-2 或 n-1 遇到0，由于无法形成3个连续元素，返回-1

算法步骤

  1. 遍历数组到倒数第三个位置（因为需要3个连续元素）
  2. 如果当前位置是0，执行翻转操作：
    • 将当前位置及后两个位置的值都进行翻转
    • 操作计数器加1
  3. 检查最后两个位置是否都为1，如果不是则返回-1
  4. 返回总操作次数

这种贪心策略是正确的，因为：

  • 我们总是尽可能早地处理0
  • 一旦某个位置变成1，我们不会再去改变它
  • 这样能保证使用最少的操作次数

时间复杂度：O(n)，只需要遍历一次数组 空间复杂度：O(1)，只使用常量额外空间

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int n = nums.size();
        int operations = 0;
        
        // 遍历到倒数第三个位置
        for (int i = 0; i <= n - 3; i++) {
            if (nums[i] == 0) {
                // 翻转连续三个元素
                nums[i] = 1 - nums[i];
                nums[i + 1] = 1 - nums[i + 1];
                nums[i + 2] = 1 - nums[i + 2];
                operations++;
            }
        }
        
        // 检查最后两个元素是否都为1
        if (nums[n - 2] == 0 || nums[n - 1] == 0) {
            return -1;
        }
        
        return operations;
    }
};

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        operations = 0
        
        # 遍历到倒数第三个位置
        for i in range(n - 2):
            if nums[i] == 0:
                # 翻转连续三个元素
                nums[i] = 1 - nums[i]
                nums[i + 1] = 1 - nums[i + 1]
                nums[i + 2] = 1 - nums[i + 2]
                operations += 1
        
        # 检查最后两个元素是否都为1
        if nums[n - 2] == 0 or nums[n - 1] == 0:
            return -1
        
        return operations

public class Solution {
    public int MinOperations(int[] nums) {
        int n = nums.Length;
        int operations = 0;
        
        // 遍历到倒数第三个位置
        for (int i = 0; i <= n - 3; i++) {
            if (nums[i] == 0) {
                // 翻转连续三个元素
                nums[i] = 1 - nums[i];
                nums[i + 1] = 1 - nums[i + 1];
                nums[i + 2] = 1 - nums[i + 2];
                operations++;
            }
        }
        
        // 检查最后两个元素是否都为1
        if (nums[n - 2] == 0 || nums[n - 1] == 0) {
            return -1;
        }
        
        return operations;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function(nums) {
    const n = nums.length;
    let operations = 0;
    
    // 遍历到倒数第三个位置
    for (let i = 0; i <= n - 3; i++) {
        if (nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历一次数组，每次操作都是常数时间
空间复杂度O(1)只使用常量额外空间，直接在原数组上修改

相关题目