Re: [閒聊] Leetcode

看板Marginalman作者pandix (麵包屌)時間3年前 (2022/11/07 02:18)推噓4(4推 0噓 1→)

留言5則, 5人參與討論串10/20 (看更多)

Weekly Contest 318 第四題想不出來就去看世界賽了第一次當Q3 gang 1.簡單說就是操作後把不為0的元素加到新陣列裡最後再補滿0 看到有人用 sort(key = lambda x : not x) 去把0移到最後好耶我下次也要用 2.用 2-pointer iterate右界維護一個set去記目前區間有哪些元素如果右界元素存在於目前的set就不停拿出左界元素直到拿出和右界一樣的元素如果右界-左界==k 就能更新答案小於的話就繼續推進右界大於的話也是拿出左界元素總之就是需要保證左界右界沒有重複元素 3.就是左右各維護一個 heap 就這麼簡單每輪看哪邊的 top 比較小要注意的就是一樣小時先拿左邊的還有就是邊界可以記一下不要取到重覆的 4.竟然是DP... contest時沒想出來主要是沒想到機器人的順序會和工廠的順序保持一致也就是如果機器人 r1 < r2 那可以保證最佳解中工廠 f1 <= f2 一樣可以討論每種相對位置的可能性去證明之前好像有寫過類似的概念總之這樣就能從左到右對每個工廠更新加進(0~工廠容量)個機器人的結果可以想像成把機器人切成很多塊一塊是屬於一個工廠 dp[i][j] 代表前i個機器人被配到前j個工廠並且第j個工廠不能再加入去 iterate k in range(0~第j+1工廠的容量) 更新 dp[i+k][j+1] = min(dp[i+k][j+1], dp[i][j]+新增的distance) 就是代表第j+1個工廠加入k個機器人 k也可以是0 複雜度是O(機器人數量*工廠數量*工廠容量) 想了很多做法就是沒想到DP 有空來把 https://youtu.be/FLbqgyJ-70I