【Leetcode Daily】2134最少交换次数来组合所有的1II

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个由 1 和 0 组成的数组，求把所有的 1 放在一起所需要的最少交换次数。注意数组视为环形数组，即第一个和最后一个相邻，且交换可以是数组中任意两个位置的交换。

思路分享

• 阅读题，先不看环形数组来试着解决一下，实际上，由于数组中 1 的个数固定，可以确定对一个数组，最后连续 1 的长度是确定的。这个 1 的长度，就可以是窗口的定长。由于交换是任意两个位置，只要计算出窗口内最少的 0 的个数，就是所谓的最小交换次数了。

• 那么环形数组的问题如何解决呢？其实也简单，只要把当前数组双倍拼接一下就行。然后使用的时候就不用考虑坐标的变换啥的，直接延长遍历的位置。在这一点上，陆爻齐相对灵茶山艾府做了点优化，灵茶山艾府直接遍历完加长后的数组，而经简单思考就能得知，其实需要多遍历的部分就是一个窗口长度，所以其实遍历原长度加上窗口长度即可，复杂度不变。

代码解答（强烈建议自行解答后再看）

• 陆爻齐的解法

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int n = nums.size();
        int win_size = reduce(nums.begin(), nums.end());
        nums.insert(nums.end(), nums.begin(), nums.end());
        int min_swap = INT_MAX;
        int one_count = 0;

        for (int i = 0; i < n+win_size; i++) {
            //cout << i << endl;
            one_count += nums[i];

            if (i < win_size-1) continue;

            min_swap = min(min_swap, win_size-one_count);

            one_count -= nums[i-win_size+1];
        }

        return min_swap;
    }
};

• 灵茶山艾府的go解法

func minSwaps(nums []int) int {
	tot1 := 0
	for _, num := range nums {
		tot1 += num
	}
	cnt1, maxCnt1 := 0, 0
	nums = append(nums, nums...) // 断环成链
	for i, num := range nums {
		cnt1 += num
		if i >= tot1 { // 滑窗
			cnt1 -= nums[i-tot1]
			if cnt1 > maxCnt1 {
				maxCnt1 = cnt1
			}
		}
	}
	return tot1 - maxCnt1
}

https://leetcode.cn/problems/minimum-swaps-to-group-all-1s-together-ii/solutions/1200295/duan-huan-cheng-lian-hua-dong-chuang-kou-ws80/