2024-10-13: In go, given a binary array nums, of length n, the
The goal is for Alice to pick up k 1s from the nums by the minimum number of actions.
Alice can choose any index aliceIndex, and if the corresponding nums[aliceIndex] is a 1, Alice will pick up a 1 and set it to 0.
After that, Alice can choose one of the following two actions:
Changes a 0 to a 1 (perform maxChanges at most once), or swaps two neighboring numbers (one is a 1 and one is a 0).
Returns the minimum number of actions required to pick up k 1s.
importation：nums = [1,1,0,0,0,1,1,0,0,1], k = 3, maxChanges = 1。
Output: 3.
Explanation: If Alice is at aliceIndex == 1 at the start of the game, and performs each action as follows, he can use 3 actions to pick up 3 1s:
At the beginning of the game Alice picks up a 1 and nums[1] becomes 0. At this point nums becomes [1,0,0,0,0,0,1,1,0,0,1].
Choose j == 2 and perform the first type of action. nums becomes [1,0,1,0,0,0,1,1,0,0,1].
Select x == 2 and y == 1, and perform the second type of action. nums becomes [1,1,0,0,0,0,1,1,0,0,1]. Since y == aliceIndex, Alice picks up a 1 and nums becomes [1,0,0,0,0,0,1,1,0,0,1].
Select x == 0 and y == 1 and perform the second type of action. nums becomes [0,1,0,0,0,0,1,1,0,0,1]. Since y == aliceIndex, Alice picks up a 1 and nums becomes [0,0,0,0,0,0,1,1,0,0,1].
Note that Alice may also perform other 3-action sequences to pick up 3 1s.
Answer 2024-10-13:
chatgpt
Title from leetcode3086.
The broad steps are as follows:
1. First defined an auxiliary function f(i) used to calculate the sum of the number around the index i (including itself).
2. In the main function minimumMoves, double pointers are used to realize the logic of the solution.
3. Initialize the left and right pointers left, right to 0, -1, left and right sides and left and right sides count and sum leftCount, rightCount, leftSum, rightSum are initialized to 0.
4. Define the variable res as the maximum value of type int64 math.
5. Iterate through each element of the array nums and determine the condition in turn:
-
If f(i) + maxChanges is greater than or equal to k, the following logic is executed.
-
Compare the size of k and f(i) and choose whether to take k or f(i).
-
If k is less than or equal to maxChanges, continue traversing to the next number.
6. Enter the loop of the double pointer logic:
-
Loop until the distance between the right pointer, right, and the left pointer, left, is less than or equal to the distance between the left pointer and i, and the sum of the left and right numbers is less than k.
-
If the number pointed to by the right pointer is 1, count, and increase the right side.
7. Next, adjust the left and right pointer positions within a while loop so that the sum of the left and right sides does not exceed k.
8. For each loop, calculate the minimum number of actions required to pick up k 1's in the current situation and update res.
9. Finally, in the loop, make a series of adjustments to the left and right counts, and the
10. Return res as the final result.
Total time complexity:
- The whole thing is a nesting of two loops, the outer loop iterates over each element in the array, and the inner loop is double pointer logic, so the time complexity is O(n^2).
Total extra space complexity:
- Only some constant-level extra space is used to store a few variables, so the extra space complexity is O(1).
The full Go code is below:
package main
import (
"fmt"
"math"
)
func minimumMoves(nums []int, k int, maxChanges int) int64 {
n := len(nums)
f := func(i int) int {
x := nums[i]
if i-1 >= 0 {
x += nums[i-1]
}
if i+1 < n {
x += nums[i+1]
}
return x
}
left, right := 0, -1
leftSum, rightSum := int64(0), int64(0)
leftCount, rightCount := int64(0), int64(0)
var res int64 = math.MaxInt64
for i := 0; i < n; i++ {
if f(i)+maxChanges >= k {
if k <= f(i) {
res = min(res, int64(k-nums[i]))
} else {
res = min(res, int64(2*k-f(i)-nums[i]))
}
}
if k <= maxChanges {
continue
}
for right+1 < n && (right-i < i-left || leftCount+rightCount+int64(maxChanges) < int64(k)) {
if nums[right+1] == 1 {
rightCount++
rightSum += int64(right) + 1
}
right++
}
for leftCount+rightCount+int64(maxChanges) > int64(k) {
if right-i < i-left || right-i == i-left && nums[left] == 1 {
if nums[left] == 1 {
leftCount--
leftSum -= int64(left)
}
left++
} else {
if nums[right] == 1 {
rightCount--
rightSum -= int64(right)
}
right--
}
}
res = min(res, leftCount*int64(i)-leftSum+rightSum-rightCount*int64(i)+2*int64(maxChanges))
if nums[i] == 1 {
leftCount++
leftSum += int64(i)
rightCount--
rightSum -= int64(i)
}
}
return res
}
func main() {
nums := []int{1, 1, 0, 0, 0, 1, 1, 0, 0, 1}
k := 3
maxChanges := 1
(minimumMoves(nums, k, maxChanges))
}
