[閒聊] LeetCode Weekly Contest 333

作者: fxfxxxfxx (愛麗絲)   2023-02-19 12:01:29
加罰時 44:26,不過排名比想像中好很多
排 50 名,史上最好的一次
https://i.imgur.com/Cl32lr7.png
1. Merge Two 2D Arrays by Summing Values
用 map 收集起來就好,而且 map 會自己幫你排好序
反正 n <= 200, O(nlogn) 綽綽有餘,不需要麻煩的用 two-pointer
2. Minimum Operations to Reduce an Integer to 0
隨手寫了一個每個 node 有 34 條邊的 BFS
(+1, +2, ..., +2^16, -1, ..., -2^16)
但 TLE 了,蠻意外的 應該是因為我用 set 而不是 vector 來存走過的點
改成只有 +- least significant bit 才過
仔細想想,好像可以分成若干 1111 的 group
如果長度 >= 2 就花兩步,如果長度 == 1 則只花一步
3. Count the Number of Square-Free Subsets
會被 > 1 的平方數整除等價於會被某個質數的平方整除
例如會被 a^2 整除,a 的所有質因數的平方還是可以整除
因為 nums[i] <= 30,用手算可以發現 <= 30 的有 10 個質數:
[2, 3, 5, 7, 11, 13, 17, 19, 21, 23, 29]
想要保持以上十個數的平方都不能整除的話
質因數分解以後上面出現的次數要 <= 1
因此只會有 2^10 總共 1024 種狀態
n <= 1000 所以 dp 做狀態轉移即可
狀態轉移:
oldstate | bit
作者: peter6666712 (18公分亞洲巨砲)   2023-02-19 12:02:00
大師
作者: NTHUlagka (拉卡)   2023-02-19 12:03:00
大師 恭喜好猛前50
作者: MurasakiSion (紫咲シオン)   2023-02-19 12:03:00
大師
作者: NTHUlagka (拉卡)   2023-02-19 12:05:00
第三題我用hash map一直TLE 後來優化才有辦法過orz
作者: YukihanaLami (lami snowflake)   2023-02-19 12:06:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com