995. Minimum Number of K Consecutive Bit Flips
給一個binary array nums
可以選擇長度k的subarray，將裡面的元素反轉
請問最少要翻轉幾次，才能讓整個array的元素都是1
如果不行就回傳-1
思路:
這題概念應該滿簡單的
假設nums[i]==0就將i~i+k-1的元素全部反轉
一直這樣重複下去就可以得到答案了
而當nums[i]==0且i+k>n的時候就沒辦法把整個nums都變成1了
不過暴力解會超出時間
所以要想個辦法紀錄，當前元素的反轉情況
用flipcnt紀錄反轉次數
再建立一個diff矩陣
因為你每次反轉只能反轉k個元素
所以當你反轉的時候，要將diff[i+k]++，紀錄i+k以後的元素跟flipcnt相差幾次反轉
每次就判斷(nums[i]+flipcnt)&1==0
golang code :
func minKBitFlips(nums []int, k int) int {
n, res, flipcnt := len(nums), 0,0
diff := make([]int, n+1)
for i := 0; i < n; i++ {
flipcnt-=diff[i]
if (nums[i]+flipcnt)&1 == 0 {
if i+k>n{
return -1
}
res++
flipcnt++
diff[i+k]++
}
}
return res
}