Re: [閒聊] Leetcode
Weekly Contest 320
今天蠻慘的，第四題在最後一分鐘才寫出來
唯一的好消息是連續三場一次過，沒有吃到 penalty
1. Number of Unequal Triplets in Array
看到 n <= 100 就無腦用三層迴圈，懶的想
2. Closest Nodes Queries in a Binary Search Tree
不想管他的樹，直接 dfs 抽出來到一個陣列後
再對每個 query 做 binary search (upper_bound, lower_bound)
3. Minimum Fuel Cost to Report to the Capital
最佳解是每個 node 都等人到齊之後再一起出發
所以這個 node 要花的就是 ceil(子樹大小/座位大小)
記得 root 不需要加就好
4. Number of Beautiful Partitions
這題我搞很久，主要是沒發現我的作法最後一段沒超過 minLength 也會算進去
debug 超久，搞到差點寫不完
首先，頭一定要是質數，尾一定不能是質數
接著，找出那些可以當分割點的質數位置
可以當分割點的條件就是前面不能是質數，否則切下去你前一個人的結尾就變成質數
找出所有分割點的 index，例如 [0, 4, 7, 9]
接著就用 dp
定義 dp[i][j] 是考慮到 j 為止做成 i 個切割的切割法
則 dp[i][j] = dp[i][j-1] + dp[i-1][pre[j]]
^^^^^^^^^^^^^^^ -> 這項代表真的切 j 的方法總數
其中 pre[j] 指的是離 j 最近但距離 >= minLength 的 index
複雜度是算好 pre 的 O(n^2) 加上更新 dp 的 O(nk)
總共 O(n^2 + nk)
這次排 536 名，不知道會不會扣分
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1668919794.A.DBC.html
→
11/20 12:52,
3年前
, 1F
11/20 12:52, 1F
推
11/20 12:56,
3年前
, 2F
11/20 12:56, 2F
推
11/20 12:56,
3年前
, 3F
11/20 12:56, 3F
推
11/20 13:16,
3年前
, 4F
11/20 13:16, 4F
推
11/20 23:55,
3年前
, 5F
11/20 23:55, 5F
討論串 (同標題文章)
