使二进制数组全部等于 1 的最少操作次数 I 图解题解

翻转连续三个数，要把数组凑成全 1

给一个只含 0 和 1 的数组 nums，一次操作能任选连续的三个元素、把它们同时反转（0 变 1、1 变 0），操作次数不限。要用最少操作把整个数组变成全 1，做不到就返回 -1。题面 nums=[0,1,1,1,0,0] 答案是 3，而 nums=[0,1,1,1] 怎么翻都会留下一个 0，只能返回 -1。

操作次数不限，为什么不能把所有翻法都试一遍

操作次数不限、每一步又能落在任意连续三个位置上，可拼出的序列是指数级的，真去枚举所有序列再挑最短的，数组稍大就跑不完。搜索空间里还塞满冗余：同一处翻两次等于没翻，分支互相抵消。穷举走不通，得看清每一步'该怎么翻'其实并不自由、而是被前面结果锁死。

最左边那个 0，其实只有一种翻法能救它

把目光放到从左数第一个 0 上。能盖住它的三连窗口有好几个，可只要不是以它为最左端，窗口就必然向左伸出去、把已经弄成 1 的位置又翻回 0。而它再往左没有元素了，不破坏左侧的选择就独剩一个：以它为首、连翻它和右边两位。这一步是被逼的，没有第二种走法。既然每个 0 怎么处理都被它左边已固定的部分锁定，从左往右照此翻，总次数就压到了最少。

从左扫到右、遇 0 就翻，什么时候会翻不下去

做法很直白：指针从下标 0 往右走，遇 1 跳过、遇 0 就以它为左端翻转连续三个并计一次数。翻转会连带改动右边两位，可能又冒出新的 0，指针继续右移照常处理即可。真正会卡住的只有一种情形：扫到一个 0 时，它右边不足两个元素、下标 i 加 2 已越出数组，凑不出以它为左端的合法窗口，只能判无解、返回 -1。

把题面两组数据的翻转一步步走出来

手算这两组时老实翻整段三位、盯着数组一步步变；代码只翻右边两位是个结果等价的简写，留到末尾再说。先走 nums=[0,1,1,1,0,0]。第 0 位是 0，翻下标 0、1、2，得 [1,0,0,1,0,0]，一次。第 1 位又是 0，翻 1、2、3，得 [1,1,1,0,0,0]，两次。第 2 位是 1，跳过。第 3 位是 0，翻 3、4、5，得 [1,1,1,1,1,1]，三次。第 4、5 位都已是 1，扫完，答案 3。再走反例 nums=[0,1,1,1]：第 0 位翻出 [1,0,0,1]、一次，第 1 位翻出 [1,1,1,0]、两次，第 2 位是 1 跳过，第 3 位却又是 0，而它右边只剩不到两个数、下标加 2 等于 5 已越界，凑不出以它为左端的窗口，返回 -1。

别急着翻，先问一句右边还够不够三个

复杂度上，指针从头到尾只走一遍、每处最多一次翻转加一次判断，时间 O(n)；就地异或翻转、只用计数和下标几个变量，空间 O(1)。几处易错：翻转前先查 i 加 2 是否越界，右边不足三个还硬翻，会把本该 -1 的算成操作数；窗口必须严格贴着当前 0 的左端，套到它中间或右侧就翻坏左边已固定成 1 的位置。还有个反直觉处：参考代码只翻右边两位、没动 nums[i]，因为指针只右移不回看，这个 0 留着也不干扰后面的判断，翻不翻它答案都一样。本就全是 1 时答案 0，[0,0,0] 一次翻转搞定。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans = 0
        for i, x in enumerate(nums):
            if x == 0:
                if i + 2 >= len(nums):
                    return -1
                nums[i + 1] ^= 1
                nums[i + 2] ^= 1
                ans += 1
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                if (i + 2 >= n) {
                    return -1;
                }
                nums[i + 1] ^= 1;
                nums[i + 2] ^= 1;
                ++ans;
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int minOperations(int[] nums) {
        int ans = 0;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 0) {
                if (i + 2 >= n) {
                    return -1;
                }
                nums[i + 1] ^= 1;
                nums[i + 2] ^= 1;
                ++ans;
            }
        }
        return ans;
    }
}