→ rainkaras: 大師 06/25 00:40
推 Hinapig0519: 別卷了 06/25 00:41
推 CanIndulgeMe: 技術大神 06/25 00:44
推 wu10200512: 別卷了 06/25 00:46
推 oin1104: 大師 06/25 00:48
推 sustainer123: 剩我不會寫hard 06/25 01:16
姆咪
怎麼是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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.76.3.7 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719246945.A.9F9.html