Re: [閒聊] LeetCode Weekly Contest 409

看板Marginalman作者DJYOMIYAHINA (通通打死)時間1年前 (2024/08/04 12:08)推噓3(3推 0噓 4→)

留言7則, 7人參與討論串1/2 (看更多)

全面潰敗== 第二題就卡了好久好白癡最後用dijkstra過了第三題就始終TLE 一生就這樣了就大概知道要maintain目前shortest path 但沒有找到很好的pop方法 def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]: shortest_path = set() for i in range(n): shortest_path.add(i) ans = [] dis = n-1 for start,end in queries: # print(shortest_path) if start in shortest_path and end in shortest_path: remove_cnt = 0 for i in range(start+1, end): if i in shortest_path: shortest_path.remove(i) remove_cnt += 1 dis -= remove_cnt ans.append(dis) return ans 就有想過如果有個有序的container 可以讓我logN內查到要remove的start跟end就可以了但我不知道哪來那個東西結果看答案才知道有SortedList這種東西什麼鬼 def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]: shortest_path = SortedList([i for i in range(n)]) ans = [] for start,end in queries: start_idx = shortest_path.bisect_right(start) end_idx = shortest_path.bisect_left(end) for i in reversed(range(start_idx, end_idx)): shortest_path.pop(i) ans.append(len(shortest_path)-1) return ans -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 37.19.205.170 (日本) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722744534.A.C45.html

→

Apache

08/04 12:09, 1年前 , 1^F

08/04 12:09, 1^F

推

dont

08/04 12:13, 1年前 , 2^F

08/04 12:13, 2^F

→

sixB

08/04 12:13, 1年前 , 3^F

08/04 12:13, 3^F