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

这道题到底在问什么

输入

nums = [0,1,1,1,0,0]

输出

3

输入

nums = [0,1,1,1]

输出

-1

最优解：一步一步想明白

1. 3记住这一句:从左往右,谁是 0 就把从它开始的连续三个翻过来,数一次操作。为什么必须从左往右、为什么这样一定最省,下面用画面讲给你看。
2. 4先看这个二进制数组 [0,1,1,1,0,0]。红色标出来的是 0,我们的任务是把所有 0 都变成 1。每次操作能任选连续的三个数,把它们同时翻转,0 变 1、1 变 0。
3. 5像这样框住连续的三个位置,一按开关,这三个数同时翻个面。有个关键想法:最左边那个 0,只有以它为左端的这一个框能翻到它,再往左没有数了。所以处理顺序只能从左往右,一个都躲不掉。
4. 6指针走到第 0 位,这里是 0,必须动手。能翻到它、又不去动它左边已经弄好的部分的,只有以它为左端的那个框。
5. 7把框放在第 0 到第 2 位这三个数上。因为下标 i 加 2 等于 2,还落在数组里,框放得下,可以翻。
6. 8开关一按,这三个数全翻了面。第 0 位如愿变成 1,后面两位也跟着翻。操作次数加一,现在是 1 次。第 0 位从此定死是 1,指针放心往右挪。
7. 9指针走到第 1 位,这里是 0,必须动手。能翻到它、又不去动它左边已经弄好的部分的,只有以它为左端的那个框。
8. 10把框放在第 1 到第 3 位这三个数上。因为下标 i 加 2 等于 3,还落在数组里,框放得下,可以翻。
9. 11开关一按,这三个数全翻了面。第 1 位如愿变成 1,后面两位也跟着翻。操作次数加一,现在是 2 次。第 1 位从此定死是 1,指针放心往右挪。
10. 12指针走到第 2 位,这里已经是 1 了,不用管它,直接往右走。
11. 13指针走到第 3 位,这里是 0,必须动手。能翻到它、又不去动它左边已经弄好的部分的,只有以它为左端的那个框。
12. 14把框放在第 3 到第 5 位这三个数上。因为下标 i 加 2 等于 5,还落在数组里,框放得下,可以翻。
13. 15开关一按,这三个数全翻了面。第 3 位如愿变成 1,后面两位也跟着翻。操作次数加一,现在是 3 次。第 3 位从此定死是 1,指针放心往右挪。
14. 16指针走到第 4 位,这里已经是 1 了,不用管它,直接往右走。
15. 17指针走到第 5 位,这里已经是 1 了,不用管它,直接往右走。
16. 18扫到头了,整个数组变成了 [1,1,1,1,1,1],全是 1。一路上一共动手 3 次,这就是最少操作次数,答案 3。
17. 19再看一个反例 [0,1,1,1]。只有开头一个 0,看着好像很好办,咱们按同样的规矩走一遍,看会遇到什么。
18. 20第 0 位是 0,右边还够三个,框住第 0 到第 2 位翻转。
19. 21翻完第 0 位变成 1,可注意后面两位也被翻了,说不定又冒出新的 0,接着往下看。
20. 22第 1 位是 0,右边还够三个,框住第 1 到第 3 位翻转。
21. 23翻完第 1 位变成 1,可注意后面两位也被翻了,说不定又冒出新的 0,接着往下看。
22. 24第 2 位是 1,略过,继续往右。
23. 25走到第 3 位,它还是 0,可它右边只剩不到两个数了,下标 i 加 2 等于 5,已经超出数组。没有以第 3 位为左端、长度为三的合法窗口;能盖住它的窗口都得从更左边伸过来,一翻就会破坏已经固定好的前缀,所以在保持前缀全 1 的前提下这个 0 变不成 1。
24. 26所以这组数据没救,直接返回 -1。这也是判无解的唯一情形:某个 0 落在末尾不足三个的位置上,凑不出以它为左端的合法窗口,而任何盖住它的窗口都得从左边伸过来、又会翻坏已固定的前缀。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问