[閒聊] LeetCode Weekly Contest 338
剛開賽時有超長一段時間網站根本就連不上
應該會 unrated 吧
看排名 LCCN 好像沒壞的樣子
1. K Items With the Maximum Sum
分成以下三種情形
1) k <= numOnes
2) k <= numOnes + numZeros
3) k <= numOnes + numZeros + numNegOnes
2. Prime Subtraction Operation
可以 greedy 的把 nums[i] 取越小越好
記得要大於前一個人
這題應該只是要考怎麼列出質數
3. Minimum Operations to Make All Array Elements Equal
可以發現對於 query q
令 L 是比 q 小的那些數，R 是比 q 大的那些數
則 q 的答案是：
(q * |L| - sum(L)) + (sum(R) - q * |R|)
所以用 map 紀錄 x --> {比 x 小的個數, 比 x 小的數的和}
這可以先 sort 後用 prefix sum 算出
最後 query 時用內建的 upper_bound 來求即可
如果你的語言沒有酷酷的函式庫的話
可能就要先 sort 好 queries 再用 two-pointer 了
4. Collect Coins in a Tree
我只想的到換根的作法
總之就是不斷維護好各節點最遠的 coin 深度
在換根的時候只需要知道最深的兩個鄰點就能算出新的深度
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.198.173.41 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1679803865.A.98A.html
推
03/26 12:16,
2年前
, 1F
03/26 12:16, 1F
推
03/26 12:23,
2年前
, 2F
03/26 12:23, 2F