得到连续 K 个 1 的最少相邻交换次数Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个整数数组 nums 和一个整数 k 。 nums 仅包含 0 和 1 。每一次移动，你可以选择 相邻 两个数字并将它们交换。
请你返回使 nums 中包含 k 个 连续 1 的 最少 交换次数。
示例 1：
输入：nums = [1,0,0,1,0,1], k = 2
输出：1
解释：在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。
示例 2：
输入：nums = [1,0,0,0,0,0,1,1], k = 3
输出：5
解释：通过 5 次操作，最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。
示例 3：
输入：nums = [1,1,0,1], k = 2
输出：0
解释：nums 已经有连续 2 个 1 了。
提示：
- 1 <= nums.length <= 105
- nums[i] 要么是 0 ，要么是 1 。
- 1 <= k <= sum(nums)
# 思路
贪心算法
# 解法
class Solution {
public int minMoves(int[] nums, int k) {
int n = nums.length,l = 0,idx = 0;
int res = Integer.MAX_VALUE,cnt = 0,t = 1,mid = k >> 1;
int[] pos = new int[n + 1];
for(int i = 0;i < n;i++) if(nums[i] == 1) pos[idx++] = i;
while(t < k) cnt += (pos[l + t] - pos[l + t - 1] - 1) * Math.min(t,k - t++);//计算第一个窗口大小
while(l + k <= idx){
res = Math.min(res,cnt);
cnt -= pos[l + mid] - pos[l];
cnt += pos[l + k] - pos[l + k - mid];
l++;
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 总结
- 分析出几种情况，然后分别对各个情况实现
