Leetcode 995 Minimum Number of K Consecutive Bit Flips

发表于 |

在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。
返回所需的 K 位翻转的次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。

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

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

示例 3：
输入：A = [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. 1 <= A.length <= 30000
  2. 1 <= K <= A.length

思路分析：
我们想一想，对于数组中最左边的0（不妨定义下标为i），我们如果想将其翻转为1的话，那么这k个翻转数该选哪个作为起点呢。如果以某个下标j(j < i)进行翻转，那么又会在更左边产生0，这样下去会一直到左边界，这显然是不合理的。我们应当就以i为起点来进行翻转。
这也就是贪心的思想！

从左至右进行遍历，每遍历到0就进行一次翻转，但是考虑到后面k个数也会进行翻转，我们如何对其进行记录呢

这里使用一个列表，将每次翻转所影响到的最右下标记录。对于当前判断的位置来说，使用二分法找到其到底被多少次翻转所影响，然后计算即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minKBitFlips(self, A, K):
        res = 0
        s = []
        for i in range(len(A)):
            index = bisect.bisect_right(s, i)
            # if influenced, flip it and then judge
            if (len(s) - index) % 2 == 1:
                A[i] = 1 - A[i]
            # only consider it when A[i] == 0
            if A[i] == 1: continue
            if len(A)-i < K: return -1
            res += 1
            s.append(i + K)
        return res