【LetMeFly】3192.使二进制数组全部等于 1 的最少操作次数 II:位运算模拟
力扣题目链接:https://leetcode.cn/problems/minimum-operations-to-make-binary-array-elements-equal-to-one-ii/
给你一个二进制数组 nums
。
你可以对数组执行以下操作 任意 次(也可以 0 次):
- 选择数组中 任意 一个下标
i
,并将从下标i
开始一直到数组末尾 所有 元素 反转 。
反转 一个元素指的是将它的值从 0 变 1 ,或者从 1 变 0 。
请你返回将 nums
中所有元素变为 1 的 最少 操作次数。
示例 1:
输入:nums = [0,1,1,0,1]
输出:4
解释:
我们可以执行以下操作:
- 选择下标
i = 1
执行操作,得到nums = [0,0,0,1,0]
。 - 选择下标
i = 0
执行操作,得到nums = [1,1,1,0,1]
。 - 选择下标
i = 4
执行操作,得到nums = [1,1,1,0,0]
。 - 选择下标
i = 3
执行操作,得到nums = [1,1,1,1,1]
。
示例 2:
输入:nums = [1,0,0,0]
输出:1
解释:
我们可以执行以下操作:
- 选择下标
i = 1
执行操作,得到nums = [1,1,1,1]
。
提示:
1 <= nums.length <= 105
0 <= nums[i] <= 1
解题方法:位运算模拟
类似于LeetCode 3191.使二进制数组全部等于 1 的最少操作次数 I,本题也从前到后模拟,遇到0则翻转一次即可。
但是不用真的翻转,因为翻转偶数次相当于没有翻转,所以使用一个变量 o r i g i n a l original original记录是否未翻转即可。
需要翻转 ⇔ (n XOR original)为true
用 n n n代表当前元素, o o o代表是否为原始值,则有:
n | o | 是否需要翻转 |
---|---|---|
0 | 0 | × |
0 | 1 | √ |
1 | 0 | √ |
1 | 1 | × |
翻转只需要(original XOR= 1)
一旦需要翻转,则original的值需要由0变1或1变0,也就是说original异或一个1即可。
时空复杂度分析
- 时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))
- 空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C++
/*
01101
10010
11101
11110
11111
n o
0 1 翻
0 0 不
1 1 不
1 0 翻
*/
class Solution {
public:
int minOperations(vector<int>& nums) {
int ans = 0, original = 1;
for (int t : nums) {
if (t ^ original) {
ans++;
original ^= 1;
}
}
return ans;
}
};
Go
package main
func minOperations(nums []int) int {
ans, original := 0, 1
for _, t := range nums {
if t ^ original == 1 {
ans++
original ^= 1
}
}
return ans
}
Java
class Solution {
public int minOperations(int[] nums) {
int ans = 0, original = 1;
for (int t : nums) {
if ((t ^ original) == 1) {
ans++;
original ^= 1;
}
}
return ans;
}
}
Python
from typing import List
class Solution:
def minOperations(self, nums: List[int]) -> int:
ans, original = 0, 1
for t in nums:
if t ^ original:
ans += 1
original ^= 1
return ans
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/143066863