leetcode
leetcode 2751 ~ 2800
拾起 K 个 1 需要的最少行动次数

拾起 K 个 1 需要的最少行动次数

难度:

标签:

题目描述

You are given a binary array nums of length n, a positive integer k and a non-negative integer maxChanges.

Alice plays a game, where the goal is for Alice to pick up k ones from nums using the minimum number of moves. When the game starts, Alice picks up any index aliceIndex in the range [0, n - 1] and stands there. If nums[aliceIndex] == 1 , Alice picks up the one and nums[aliceIndex] becomes 0(this does not count as a move). After this, Alice can make any number of moves (including zero) where in each move Alice must perform exactly one of the following actions:

  • Select any index j != aliceIndex such that nums[j] == 0 and set nums[j] = 1. This action can be performed at most maxChanges times.
  • Select any two adjacent indices x and y (|x - y| == 1) such that nums[x] == 1, nums[y] == 0, then swap their values (set nums[y] = 1 and nums[x] = 0). If y == aliceIndex, Alice picks up the one after this move and nums[y] becomes 0.

Return the minimum number of moves required by Alice to pick exactly k ones.

 

Example 1:

Input: nums = [1,1,0,0,0,1,1,0,0,1], k = 3, maxChanges = 1

Output: 3

Explanation: Alice can pick up 3 ones in 3 moves, if Alice performs the following actions in each move when standing at aliceIndex == 1:

  •  At the start of the game Alice picks up the one and nums[1] becomes 0. nums becomes [1,1,1,0,0,1,1,0,0,1].
  • Select j == 2 and perform an action of the first type. nums becomes [1,0,1,0,0,1,1,0,0,1]
  • Select x == 2 and y == 1, and perform an action of the second type. nums becomes [1,1,0,0,0,1,1,0,0,1]. As y == aliceIndex, Alice picks up the one and nums becomes [1,0,0,0,0,1,1,0,0,1].
  • Select x == 0 and y == 1, and perform an action of the second type. nums becomes [0,1,0,0,0,1,1,0,0,1]. As y == aliceIndex, Alice picks up the one and nums becomes [0,0,0,0,0,1,1,0,0,1].

Note that it may be possible for Alice to pick up 3 ones using some other sequence of 3 moves.

Example 2:

Input: nums = [0,0,0,0], k = 2, maxChanges = 3

Output: 4

Explanation: Alice can pick up 2 ones in 4 moves, if Alice performs the following actions in each move when standing at aliceIndex == 0:

  • Select j == 1 and perform an action of the first type. nums becomes [0,1,0,0].
  • Select x == 1 and y == 0, and perform an action of the second type. nums becomes [1,0,0,0]. As y == aliceIndex, Alice picks up the one and nums becomes [0,0,0,0].
  • Select j == 1 again and perform an action of the first type. nums becomes [0,1,0,0].
  • Select x == 1 and y == 0 again, and perform an action of the second type. nums becomes [1,0,0,0]. As y == aliceIndex, Alice picks up the one and nums becomes [0,0,0,0].

 

Constraints:

  • 2 <= n <= 105
  • 0 <= nums[i] <= 1
  • 1 <= k <= 105
  • 0 <= maxChanges <= 105
  • maxChanges + sum(nums) >= k

代码结果

运行时间: 112 ms, 内存: 27.2 MB

/*
题目思路：
1. 首先找到所有为1的索引，记录在一个列表中。
2. 如果这些1的数量已经大于等于k，则直接在这些1中选择相隔最远的k个1即可。
3. 如果1的数量少于k，则需要利用maxChanges将0变为1，再进行选择。
4. 使用滑动窗口的方法计算最小行动次数。
*/

import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public int minMoves(int[] nums, int k, int maxChanges) {
        List<Integer> ones = IntStream.range(0, nums.length)
                                       .filter(i -> nums[i] == 1)
                                       .boxed()
                                       .collect(Collectors.toList());
        if (ones.size() >= k) {
            return ones.get(k - 1) - ones.get(0);
        }
        int additional = k - ones.size();
        int minMoves = Integer.MAX_VALUE;
        for (int i = 0; i + k - 1 < nums.length; i++) {
            int moves = 0;
            int changes = 0;
            for (int j = i; j < i + k; j++) {
                if (nums[j] == 0) {
                    changes++;
                }
            }
            if (changes <= maxChanges) {
                minMoves = Math.min(minMoves, moves);
            }
        }
        return minMoves;
    }
}

解释

方法:

这道题的解题思路可以分为几个部分。首先，检查连续三个位置中最多有几个连续的1，并将其存储在变量c中。如果c大于等于k，直接返回k-1，因为Alice可以直接在连续的1中拾取。接下来，如果maxChanges加上c大于等于k，意味着Alice可以通过改变0为1和移动1来拾取k个1，每个1需要两次操作，因此返回c-1加上(k-c)*2。如果上述情况都不满足，说明Alice需要使用第二种操作（移动1）来拾取剩余的1，这时问题转化为一个货仓选址问题，即在nums的1的位置数组idx中选择连续的k-maxChanges个1，并将它们移动到中位数位置，使得总移动距离最小。最后返回这个最小移动距离加上maxChanges*2。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
题解中提到检查连续三个位置的连续1，为什么选择长度为3的窗口来进行这个检查？
▷
选择长度为3的窗口主要是基于优化算法的性能和简化问题的处理。在考虑拾取1的最优策略时，较小的窗口（如3个位置）可以有效地评估局部最优（即连续的1的局部最大数量），从而快速决定是否可以通过简单操作（如直接拾取或少量修改）达成目标。此外，3个位置的窗口也足够捕捉到问题中的关键信息，而不至于过度复杂化算法。
🦆
题解中提到如果连续1的数量c大于等于k则直接返回k-1，这里为什么要减1？
▷
当连续的1的数量c大于等于k时，Alice可以在这些连续的1中直接拾取所需的k个1，不需要任何额外的移动。因此，理论上拾取动作只需要进行k次。但是，题目可能隐含了Alice在拾取过程中的位置调整，每次从一个1跳到下一个1视为一次行动，这样总共需要k-1次跳跃。因此，在连续的1足够多时，返回k-1表示Alice在拾取完这k个1后的最小行动次数。
🦆
题解中使用前缀和数组来计算最小移动距离，请问为什么使用前缀和数组会有助于解决这个问题？
▷
使用前缀和数组能够快速计算任意子数组的和，这在处理连续元素的移动和位置调整问题时尤其有效。在该问题中，需要计算特定长度的子数组（即连续的1的位置）中的元素向中位数移动的总距离。通过前缀和，可以快速获取任意区间内1的位置和，从而计算出移动到中位数的成本。这样就可以遍历所有可能的子数组，找到移动成本最小的配置，显著减少了计算的复杂性和时间消耗。

相关问题

在带权树网络中统计可连接服务器对数目执行操作使数据元素之和大于等于 K