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:
输入: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 <= 105
0 <= nums[i] <= 1
解题方法:模拟(其实是很不严格的证明)
从前到后遍历数组(遍历到倒数第三个元素),遇见$0$则从当前位置开始连续翻转3个元素。
遍历结束后,若最后两个元素都是$1$,则返回总翻转次数;否则则返回$-1$。
为何这样正常操作就是“最小操作次数”:
因为这样不会把“同样的三个元素”翻转多次(最小性证明),同时又不得不翻转(必要性证明)。
因为是从前向后遍历的,遇到零的话如果往前翻(前面全是1),则前面的1变成0后还需要额外次数再次翻转回1。
时空复杂度分析
- 时间复杂度$O(len(nums))$
- 空间复杂度$O(1)$
AC代码
C++
1 |
|
Go
1 |
|
Java
1 |
|
Python
1 |
|
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/143064645
3191.使二进制数组全部等于 1 的最少操作次数 I
https://blog.letmefly.xyz/2024/10/18/LeetCode 3191.使二进制数组全部等于1的最少操作次数I/