姆咪
怎麼是hard 想到快睡著還是沒想出來
一生就這樣了
其實直覺知道要怎麼做 就遇到0翻 紀錄被翻的次數這樣
但O(NK)感覺不是很ok
雖然我看C++可以車過去就是了
最後是看安殺才知道可以記diff
第i個的翻面次數 = 第i-1的的翻面次數 + diff[i]
這樣就可以從0一直走下去 搭配持續更新diff
學到了==
def minKBitFlips(self, nums: List[int], k: int) -> int:
n = len(nums)
diff = [0 for _ in range(n)]
flips_cur, flips_times = 0, 0
for i in range(n-k+1):
flips_cur += diff[i]
if (flips_cur%2) ^ nums[i] == 0:
flips_cur += 1
flips_times += 1
if i+k < n:
diff[i+k] -= 1
for i in range(n-k+1, n):
# can't flip anymore
flips_cur += diff[i]
if (flips_cur%2) ^ (nums[i]) == 0:
return -1
return flips_times