【贪心】力扣3191-使二进制数组全部等于1的最少操作次数I

摘要: 一道平平无奇的贪心

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，今天我们来看一个在一个二进制串上翻转的问题，经过分析后可以找到贪心算法。

题目

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

给你一个二进制数组 nums 。

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

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

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

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

提示：

3 <= nums.length <= 1e5
0 <= nums[i] <= 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 。

题解

算法: 贪心

假设数组长度为 $n$，如果一次操作将 $s[i], s[i+1], s[i+2]$ 翻转，称其为以 $i$ 为起点的翻转，记为为 $flip(i)$。那么就有命题：

• 命题：在最优操作序列中，$flip(i)$ 最多有一个。

因为如果 $flip(i)$ 出现了两次，那相当于没操作，把这两次 $flip(i)$ 从操作序列中去掉会使得操作序列更短。有了这个命题，考虑二进制串的最左边元素 $s[0]$，

• 如果 $s[0] = 1$，那么操作序列一定不含 $flip(0)$，因为如果有一个 $flip(0)$ 会使得 $s[0]$ 变为 0，那么必须再来一个 $flip(0)$ 将其变回 1，与命题矛盾。也就是说如果 $s[0] = 1$，则 $s[0..n-1]$ 上的答案取决于 $s[1..n-1]$ 上的答案，与 $s[0]$ 无关。
• 如果 $s[0] = 0$，那么需要一次 $f(0)$ 将其变为 1，又由以上命题，$flip(0)$ 最多有一次。也就是说，执行一次 $flip(0)$ 将 $s[0]$ 变为 1 后，后续的操作序列就与 $s[0]$ 无关了，仅需考虑 $s[1..n-1]$（其中 $s[1], s[2]$ 翻转了）上的最短操作序列。

综上，我们可以总结出以下谈心算法：

枚举 $i=0,1,\cdots,n-1$，依次考虑操作序列中是否需要一次 $flip(i)$，记操作序列最短长度为 $ans$：

• 若 $s[i] = 1$，则直接跳过，考察 $i+1$；
• 若 $s[i] = 0$，则 $ans$ 加 1，然后将 $s[i+1], s[i+2]$ 翻转后，进入 $i+1$。

代码 (Python)

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        for i in range(n - 2):
            if nums[i] == 1:
                continue
            ans += 1
            nums[i + 1] ^= 1
            nums[i + 2] ^= 1
        if nums[i + 1] == 1 and nums[i + 2] == 1:
            return ans
        else:
            return -1

---