動機

下次處理flip就要這樣處理

Problem

You are given a binary array nums and an integer k.

A k-bit flip is choosing a subarray of length k from nums 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.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [0,1,0], k = 1Output: 2Explanation: Flip nums[0], then flip nums[2].

Example 2:

Input: nums = [1,1,0], k = 2Output: -1Explanation: No matter how we flip subarrays of size 2, we cannot make the array become [1,1,1].

Example 3:

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

 

Constraints:

  • 1 <= nums.length <= 3 * 104
  • 1 <= k <= nums.length

Sol

不難看出要用greedy，把不用改的去掉，把需要flip的flip

但是反覆的flip很花時間，所以要想辦法處理這段

這裡用queue的長度代表被flip的次數，這樣只要放開始flip的index就可以找出什麼時候結束

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        q = deque()
        ret = 0
        for (i,n) in enumerate(nums):
            if q and i >= q[0]+k:
                q.popleft()
            if n == (len(q) % 2):
                if i+k <= len(nums):
                    q.append(i)
                else:
                    return -1
                ret += 1
        return ret