[閒聊] LeetCode Weekly Contest 329

精美的圖 https://i.imgur.com/988BWlv.png 就在我以為這次又能在 20 分內完成時 最後一題吃了十次 penalty，幾乎都是 TLE 到最後怎麼過的呢 我把一模一樣的演算法用 python 寫一次就過了 第二個 accept 是我認真把有可能變慢的所有東西都改一改 還是能用 C++ 過 https://i.imgur.com/zNkYOs2.png 加CN進來之後應該會到3000名左右 QQ 1. Alternating Digit Sum 轉成字串再一加一減即可 2. Sort the Students by Their Kth Score 寫一個自己的 sort compare 函數即可 sort(score.begin(), score.end(), [=](auto &v, auto& w){ return v[k] > w[k]; }); 3. Apply Bitwise Operations to Make Strings Equal 可以發現: 00 --> 00 10 --> 11 01 --> 11 11 --> 10 也就是，存在 1 的陣列(1 的數目不限)可以轉化成任何存在 1 的陣列 所以只要看兩邊是否都有 1 或都沒有 1 即可 4. Minimum Cost to Split an Array DP[i] = min_j(DP[j] + trim(nums[j:i]) + k) 可以提前花 O(n^2) 算出所有 trim(nums[j:i]) 所以最後複雜度還是 O(n^2) 只是我到最後還是不知道為什麼一開始過不了 最後過的 python 版本跟一開始的 C++ 演算法一模一樣 我還檢查好幾次確定 n <= 1000 可能時間壓蠻緊的吧 比完之後把一些能加速的東西修一修也能用 C++ 過就是了 QQ --
※ 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1674360072.A.B32.html

→ Firstshadow: 大師 01/22 12:02

推 pandix: 大師 01/22 12:06

→ HuiXillya: 大師 01/22 12:34

→ NCKUEECS: 大師 01/22 12:40