Description
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.
在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。
返回所需的 K 位翻转的次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。
题目链接：https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/
Difficulty: hard
Example 1:
Input: A = [0,1,0], K = 1
Output: 2
Explanation: Flip A[0], then flip A[2].
Example 2:
Input: A = [1,1,0], K = 2
Output: -1
Explanation: 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 = 3
Output: 3
Explanation:
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 <= A.length <= 30000
- 1 <= K <= A.length
分析
- 用li记录每个位需要翻转的情况（初始为零），遍历每个位，index记录当前位的翻转情况；
- 遇到某一位反转之后为0，则说明该点需要翻转以此，首先将index对1取异或（相当于0变成1，1变成0），再将K位之后对应的li对1取异或，若超出li的长度说明，不能将所有的数字翻转成1，返回-1，Sum加一；
- 遇到某一位反转之后为1，继续下一位；
- 遍历完成，返回记录的翻转次数Sum。
- 时间复杂度为O(n).
- 错误分析：用li记录每个位翻转情况，遍历，遇到需要翻转的位，将后续K位的翻转情况记录，即对应li中的记录取异或，答案正确，但是时间复杂度为O(nk),时间超限。
参考代码
class Solution(object):
def minKBitFlips(self, A, K):
index=0
Sum=0
li=[0]*len(A)
i=0
while(i < (len(A))):
index ^= li[i]
if(A[i]^index == 0):
Sum += 1
index ^= 1
if(i+K<len(A)):
li[i+K] ^= 1
if(i+K>len(A)):
return -1
i+=1
return Sum