leetcode 1151.最少交换次数来组合所有的 1

leetcode 1151. 最少交换次数来组合所有的 1

• 给出一个二进制数组 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]。

解题：

func leastSwapOne(_ target: [Int]) -> Int {
        //1. 把所有的1组合到一起，那么可以得到所有 1的长度 lengthOne，剩下的都是 0
        //2. 题中的要求，其实是把长度范围是lengthOne内的 0 变成1，就达到了把1组合到一起的目的
        //3. 那么我们定义滑动窗口长度是 lengthOne，在这个范围内，统计0的个数，个数最小的，就是要变换的最小次数，就是想得到的答案
        
        //定义变量
        var minLength = -1
        var lengthOne = 0
        let count = target.count
        var countOfZero = 0
        
        for i in 0..<count {
            if target[i] == 1 {
                lengthOne += 1
            }
        }
        
        if lengthOne == 1 {
            return 0
        }
        
        //定义窗口
        var start = 0
        for end in 0..<count {
            //更新变量
            if target[end] == 0 {
                countOfZero += 1
            }
            if end - start + 1 == lengthOne {
                if minLength == -1 {
                    minLength = countOfZero
                } else {
                    minLength = min(minLength, countOfZero)
                }
                
                //更新窗口
                if target[start] == 0 {
                    countOfZero -= 1
                }
                start += 1
            }
        }
        
        return minLength
    }