姆咪
怎么是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