Leetcode 1151:最少交换次数来组合所有的 1(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1151:最少交换次数来组合所有的 1(超详细的解法!!!)

in leetcode with 0 comment

给出一个二进制数组 data,你需要通过交换位置,将数组中 任何位置 上的 1 组合到一起,并返回所有可能中所需 最少的交换次数

示例 1:

输入:[1,0,1,0,1]
输出:1
解释: 
有三种可能的方法可以把所有的 1 组合在一起:
[1,1,1,0,0],交换 1 次;
[0,1,1,1,0],交换 2 次;
[0,0,1,1,1],交换 1 次。
所以最少的交换次数为 1。

示例 2:

输入:[0,0,0,1,0]
输出:0
解释: 
由于数组中只有一个 1,所以不需要交换。

示例 3:

输入:[1,0,1,0,1,0,0,1,1,0,1]
输出:3
解释:
交换 3 次,一种可行的只用 3 次交换的解决方案是 [0,0,0,0,0,1,1,1,1,1,1]。

提示:

  1. 1 <= data.length <= 10^5
  2. 0 <= data[i] <= 1

解题思路

一个很容易想到的思路就是先统计总共有多少个1,我们假设有m个。然后以m为滑动窗口的长度,通过滑动窗口的方式判断窗口中有多少个1(假设为n个),那么此时我们需要移动的次数就是m-n,我们只需要找最小值即可。

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        n, m = len(data), sum(data)
        cur, res = sum(data[:m]), m
        
        for i in range(m, n):
            res = min(res, m - cur)
            if data[i] == 1:
                cur += 1
            if data[i - m] == 1:
                cur -= 1
        return res

当然我们也可以通过前缀和的方式统计区间内1的个数。

class Solution:
    def minSwaps(self, data: List[int]) -> int:
        n = len(data)
        pre = [0] * (n + 1)
        for i in range(1, n + 1):
            pre[i] = pre[i - 1] + data[i - 1]
        
        res = m = pre[-1]
        for i in range(m, n):
            res = min(res, m - (pre[i] - pre[i-m]))
        return res

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses