LeetCode 3191.使二进制数组全部等于 1 的最少操作次数 I：模拟（说是最小操作次数，其实不重复翻转就是了）

【LetMeFly】3191.使二进制数组全部等于 1 的最少操作次数 I：模拟（说是最小操作次数，其实不重复翻转就是了）

力扣题目链接：https://leetcode.cn/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-i/

给你一个二进制数组 nums 。

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

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

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

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

 

示例 1：

输出：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：

输出：-1

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

 

提示：

• 3 <= nums.length <= 105
• 0 <= nums[i] <= 1

解题方法：模拟（其实是很不严格的证明）

从前到后遍历数组（遍历到倒数第三个元素），遇见$0$则从当前位置开始连续翻转3个元素。

遍历结束后，若最后两个元素都是$1$，则返回总翻转次数；否则则返回$-1$。

为何这样正常操作就是“最小操作次数”：

因为这样不会把“同样的三个元素”翻转多次（最小性证明），同时又不得不翻转（必要性证明）。

因为是从前向后遍历的，遇到零的话如果往前翻(前面全是1)，则前面的1变成0后还需要额外次数再次翻转回1。

时空复杂度分析

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

/*
011100
100100
100011
111111


011100
100100
111000
111111

0111
1001
1110
*/
class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size() - 2; i++) {
            if (!nums[i]) {
                ans++;
                // nums[i] ^= 1;  // 这个修改与否都无所谓了
                nums[i + 1] ^= 1;
                nums[i + 2] ^= 1;
            }
        }
        return nums[nums.size() - 1] & nums[nums.size() - 2] ? ans : -1;
    }
};

Go

package main

func minOperations(nums []int) int {
    ans := 0
    for i := 0; i < len(nums) - 2; i++ {
        if nums[i] == 0 {
            ans++
            nums[i + 1] ^= 1
            nums[i + 2] ^= 1
        }
    }
    if nums[len(nums) - 1] & nums[len(nums) - 2] == 1 {
        return ans
    } else {
        return -1
    }
}

Java

class Solution {
    public int minOperations(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] == 0) {
                ans++;
                nums[i + 1] ^= 1;
                nums[i + 2] ^= 1;
            }
        }
        return (nums[nums.length - 1] & nums[nums.length - 2]) == 1 ? ans : -1;
    }
}

Python

from typing import List

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

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143064645

原文地址：https://blog.csdn.net/Tisfy/article/details/143064645

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！