推 SecondRun: 大師 11/13 12:39
推 NTHUlagka: 大師好猛 11/13 19:03
Weekly Contest 319
1.溫度轉換
蛤?
2.又中計跑去想 2-pointer 了
簡單的 O(n^2)
3.分層 sort binary tree
對每層的 node 先把他們排序之後的結果求出來
如果目前 node 的 index 和他排序之後的 index 不一樣
就直接和佔住他 index 的 node 交換
直到每個 node 都到他目標的 index
4.大中計 沒想好就開始寫了 吃了很多次TLE
可以用 greedy 發現有大於等於 k 的回文 substring 就直接抓就好
維護一個左界 對每個 i 去和他到左界中距離 >= k 的配對 看是不是回文
是的話就 res+=1 並且推進左界到 i+1
我檢查回文是直接 s[i:j] == s[i:j][::-1]
複雜度變成 O(n^3) 不過還是過了
應該是要先把所有回文 substring (i,j) 找出來再搞
複雜度 O(n^2)
--
可憐
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.212.49 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1668314169.A.88B.html