Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

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
推 wwndbk: 別捲了
→ oin1104: 大師 我好崇拜你