Re: [閒聊] 每日leetcode
2134. Minimum Swaps to Group All 1's Together II
nums矩陣由0、1組成，且nums為circular array
你可以任意將nums裡面的兩個元素互換位置
請問要將所有1元素集中在一起，最少需要交換幾次
思路:
用sliding window
先計算1的數量，假設有n個
接著用大小為n的window去遍歷nums
你要交換的次數就是n-window內1的數量
所以找出1最多的地方就好
然後因為nums是circular array所以要記得檢查頭尾連接的地方
golang code :
func minSwaps(nums []int) int {
total, cnt, maxnum, n, idx := 0, 0, 0, len(nums), 0
for _, val := range nums {
total += val
}
for i := 0; i < total; i++ {
cnt += nums[i]
}
maxnum = cnt
for i := total; i < n; i++ {
cnt += nums[i] - nums[idx]
idx++
maxnum = max(maxnum, cnt)
}
for i := 0; i < total-1; i++ {
cnt += nums[i] - nums[idx]
idx++
maxnum = max(maxnum, cnt)
}
return total - maxnum
}
--
https://i.imgur.com/r9FBAGO.gif
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.212.3 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722601686.A.5AB.html
推
08/02 20:29,
1年前
, 1F
08/02 20:29, 1F
→
08/02 20:30,
1年前
, 2F
08/02 20:30, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 618 之 1554 篇)：