0995：K 连续位的最小翻转次数（1835 分）

力扣第 124 场周赛第 3 题

题目

给定一个二进制数组 nums 和一个整数 k 。

k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 ，同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 。

返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能，则返回 -1 。

子数组 是数组的 连续 部分。

示例 1：

输入：nums = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。

示例 2：

输入：nums = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

示例 3：

输入：nums = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]

提示：

• 1 <= nums.length <= 105
• 1 <= k <= nums.length

相似问题：

• 0319：灯泡开关
• 2167：移除所有载有违禁货物车厢所需的最少时间（2219 分）
• 2450：应用操作后不同二进制字符串的数量
• 3191：使二进制数组全部等于 1 的最少操作次数 I（1311 分）

分析

• 遍历 nums[i]，假如 nums[i] 为 0，必须翻转 nums[i:i+k-1]
• 每次都实际翻转太耗时，考虑只记录翻转的 i 的列表 Q
• 计算 Q 中有多少个 >i-k 的下标，即可知道 nums[i] 当前实际的值

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        res, Q = 0, deque()
        for j,x in enumerate(nums):
            if Q and Q[0]==j-k:
                Q.popleft()
            if len(Q)%2^x==0:
                if j+k>len(nums):
                    return -1
                Q.append(j)
                res += 1
        return res

62 ms