Problem: [3192. 使二进制数组全部等于 1 的最少操作次数 II]
Problem: [3192. 使二进制数组全部等于 1 的最少操作次数 II]
思路
求最小值是多少，我们则可以假设最小值是多少，由此推导出利用二分查找得到结果。
我们用一个二分筛选我们可能的答案，然后在`f`方法中利用**贪心**进行反转。
遇到的每一个0我们都将其转换为1，再将flag进行变化，对于每一个1都将其转换为0
也就是说当flag=0，我们一旦遇到0就进行转换，然后跳跃到下一个1，同时将flag置1
当flag=1，我们一旦遇到1就进行转换，然后跳跃到下一个0，同时将flag置0
如此往复，直到遍历完成或反转次数`m`用完，根据结果进行二分区间的变换。
Code
```Go []
package main
import "math"
func f(nums []int, mid int) bool {
i, cnt0, cnt1 := 0, 0, 0
flag := false
for _, n := range nums {if n == 0 {cnt0++} else {cnt1++}}
for i<len(nums) && nums[i]==1 {i++; cnt1--}
for i<len(nums){
if !flag{
if mid==0 {break}
for i<len(nums) && nums[i]==0 {i++;cnt0--}
mid--;flag=true
if mid==0 {break}
} else {
if mid==0 {break}
for i<len(nums) && nums[i]==1 {i++;cnt1--}
mid--;flag=false
if mid==0 {break}
}
}
if i < len(nums) {if !flag {for i<len(nums) && nums[i]==1 {i++;cnt1--}} else {for i<len(nums) && nums[i]==0 {i++;cnt0--}}}
return cnt0 == 0 && cnt1 == 0
}
func minOperations(nums []int) int {
left, right, ans := 0, math.MaxInt32, 0
for left < right {
mid := left + (right - left)/2
if f(nums, mid) {
right, ans = mid, mid
} else {
left = mid + 1
}
}
return ans
}
class Solution {
public:
int f(vector<int> &nums, int m) {
int cnt0=0,cnt1=0,temp,flag=0,i=0;
for(auto &n:nums)if(n)++cnt1;else++cnt0;
while(i<nums.size()&&nums[i])++i,--cnt1;
for (; i < nums.size();) {
if (!flag) {
if(!m)break;
while(i<nums.size()&&!nums[i])++i,--cnt0;
--m,flag=1;
if(!m)break;
} else {
if(!m)break;
while(i<nums.size()&&nums[i])++i,--cnt1;
--m;flag=0;
if(!m)break;
}
}
if(i<nums.size()){
if(!flag){while(i<nums.size()&&nums[i])--cnt1,++i;}
else{while(i<nums.size()&&!nums[i])--cnt0,++i;}
}
return cnt1==0 && cnt0==0;
}
int minOperations(vector<int>& nums) {
int left = 0, right = INT_MAX, ans=0;
while (left < right) {
int m = left + (right - left) / 2;
if (f(nums, m))right=m, ans=m;
else left = m + 1;
}
return ans;
}
};
- 微信
- 赶快加我聊天吧
- 赶快加我聊天吧
2025年11月22日 16:16:54 1楼
(○´･д･)ﾉ