全面潰敗==
第二題就卡了好久 好白癡
最後用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