→ oin1104: 大師 送我模型 06/24 18:05
→ JIWP: 我偷看答案的 06/24 18:08
→ JIWP: 我不是大師 不用送你模型 06/24 18:09
→ SecondRun: 大師 送我秘書 06/24 18:22
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
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.75.61.206 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719223488.A.407.html