推 NTHUlagka: 之前不知道聽誰說好像抓10的七次方最準 03/19 12:16
推 NTHUlagka: 大師O(n)解法777 03/19 16:15
又爛了
https://i.imgur.com/TXbugzB.png
1. Number of Even and Odd Bits
總共最多十個 bit, 一個一個檢查就好
2. Check Knight Tour Configuration
存 move --> (row, col) 的陣列
然後檢查相鄰的 move 是不是合法的走法
沒發現一定要從 (0, 0) 開始吃一次 penalty
3. The Number of Beautiful Subsets
隨手寫一個 O(2^n * n) 的結果 TLE
蠻讓我意外的，畢竟 n = 20 的話感覺還好
不過 LeetCode 也沒說多少時間才叫 TLE
最後只好乖乖寫 O(2^n) 的 DFS
不過因為 DFS 其實開銷蠻大的
所以要寫之前有點猶豫 想說會不會是有其他寫法
不過考慮到這題只是 medium
最後還是直接寫 DFS
賽後是有想到一個 O(n) 的方法
因為如果 mod k 不同的話一定是獨立的
所以把 mod k 不同的分成各自一群最後再乘回來就好
而對於 mod k 相同的，可以排序後用 DP 做
紀錄取或不取的答案
最後會是線性的
https://leetcode.com/contest/weekly-contest-337/submissions/detail/917867920/
4. Smallest Missing Non-negative Integer After Operations
可以不斷加減 value
所以只跟 nums[i] mod value 有關
計算每個 nums[i] mod value 出現的次數
然後就從 0 開始看能不能造出來就好
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.198.173.41 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1679198456.A.BBE.html