2025-01-22: The minimum number of operations to make all binary arrays equal to 1 II. In Go language, given a binary array nums, you can perform the following operations on the array any number of times (including 0 times):
Select any index i and reverse all elements starting from that index to the end of the array. Inversion means turning 0 into 1, or turning 1 into 0.
Calculate the minimum number of operations required to change all elements in the nums array to 1.
1 <= <= 100000。
0 <= nums[i] <= 1。
Input: nums = [0,1,1,0,1].
Output: 4.
explain:
We can do the following:
Select index i = 1 and perform the operation, getting nums = [0,0,0,1,0] .
Selecting the index i = 0 and performing the operation yields nums = [1,1,1,0,1] .
Select index i = 4 and perform the operation, getting nums = [1,1,1,0,0] .
Select the index i = 3 and perform the operation, getting nums = [1,1,1,1,1] .
Answer 2025-01-22:
chatgpt
The question comes from leetcode3192.
The general steps are as follows:
1. The initial array is[0, 1, 1, 0, 1], the number of initial operationsops = 0。
2. During the traversal process, decide whether to increase the number of operations based on the parity of the current element and the number of operations.
3. Traverse to the first element 0. At this time, the number of operations is an even number, so it needs to be reversed. At this time, the array becomes[1, 1, 1, 0, 1], the number of operations is increased by 1.
4. Continue traversing. The next element is 1. At this time, the number of operations is an odd number. There is no need to reverse it, and the number of operations remains unchanged.
5. Traverse to the next element 1, still no need to reverse, the number of operations remains unchanged.
6. The next element is 0, the number of operations is an odd number, and needs to be reversed. At this time, the array becomes[1, 1, 1, 1, 0], the number of operations is increased by 1.
7. The last element is 1, the number of operations is an even number, and needs to be reversed. At this time, the array becomes[1, 1, 1, 1, 1], the number of operations is increased by 1.
The final number of operations is 4. It takes 4 operations to change all elements in the array to 1.
Overall time complexity: Traversing the array takes O(n) time complexity, where n is the length of the array.
Total extra space complexity: In solving the problem, only a constant level of extra space is used, and the extra space complexity is O(1).
The complete Go code is as follows:
package main
import (
"fmt"
)
func minOperations(nums []int) int {
ops := 0
for _, num := range nums {
if (num == 0 && ops%2 == 0) || (num == 1 && ops%2 == 1) {
ops++
}
}
return ops
}
func main() {
nums := []int{0, 1, 1, 0, 1}
result := minOperations(nums)
(result)
}
The complete Rust code is as follows:
fn min_operations(nums: Vec<i32>) -> i32 {
let mut ops = 0;
for &num in &nums {
if (num == 0 && ops % 2 == 0) || (num == 1 && ops % 2 == 1) {
ops += 1;
}
}
ops
}
fn main() {
let nums = vec![0, 1, 1, 0, 1];
let result = min_operations(nums);
println!("{}", result);
}
The complete python code is as follows:
# -*-coding:utf-8-*-
def min_operations(nums):
ops = 0
for num in nums:
if (num == 0 and ops % 2 == 0) or (num == 1 and ops % 2 == 1):
ops += 1
return ops
if __name__ == "__main__":
nums = [0, 1, 1, 0, 1]
result = min_operations(nums)
print(result)
The complete code of solidity is as follows:
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
contract MinOperations {
function minOperations(uint256[] memory nums) public pure returns (uint256) {
uint256 ops = 0;
for (uint256 i = 0; i < ; i++) {
if ((nums[i] == 0 && ops % 2 == 0) || (nums[i] == 1 && ops % 2 == 1)) {
ops++;
}
}
return ops;
}
}
