题目如下：

In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of K-bit flips required so that there is no 0 in the array.  If it is not possible, return -1.

 

Example 1:

Input: A = [0,1,0], K = 1Output: 2Explanation: Flip A[0], then flip A[2].

Example 2:

Input: A = [1,1,0], K = 2Output: -1Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].

Example 3:

Input: A = [0,0,0,1,0,1,1,0], K = 3Output: 3Explanation:Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

 

Note:

1. 1 <= A.length <= 30000
2. 1 <= K <= A.length

解题思路：如果A[0]是0，那么A[0]一定要翻转一次，当然翻转三次也是可以的，但是效果和翻转一次是一样的。接下来就可以忽略A[0]了，假设把A[0]删掉，那么A[1]就变成A[0]，和之前对A[0]的操作是一样的，这也意味着可以从头遍历数组，遇到元素值为0就执行依次翻转操作。因为翻转A[i]意味着自身以及后面的K-1个元素都要翻转一次，所有可以把执行了翻转操作的下标存入列表flip_path，很显然flip_path的元素是升序排列的。最后从头开始遍历A,假设当前遍历到的元素为A[i]，先从flip_path中找出前面执行的翻转操作有几个对自身有影响，有几个则翻转几次。如果翻转玩后恰好是1则继续遍历下一个元素，如果是0则判断i+K是否大于A的长度，大于表示无法翻转，返回-1，小于的话翻转次数加1，同时把i存入flip_path，继续下一个元素。

代码如下：

class Solution(object):    def minKBitFlips(self, A, K):        """        :type A: List[int]        :type K: int        :rtype: int        """        import bisect        flip = []        res = 0        for i in range(len(A)):            if len(flip) > 0 and flip[0] + K <= i:                flip.pop(0)            inx = bisect.bisect_left(flip,i)            if inx % 2 == 1:                A[i] = 0 if A[i] == 1 else 1            if A[i] == 1:                continue            else :                if i + K > len(A):                    return -1                A[i] = 1                flip.append(i)                res += 1        return res