1. 解题思路
这一题的话由于题目限制了road不会交叉,因此我们只需要在每次增加road之后将中间节点删除,剩余的路径节点数目即为路径长度。
2. 代码实现
给出python代码实现如下:
class Solution:
def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
ans = []
arr = [i for i in range(n)]
for u, v in queries:
i, j = bisect.bisect_left(arr, u), bisect.bisect_left(arr, v)
if arr[i] == u and arr[j] == v:
while arr[i+1] != v:
arr.pop(i+1)
ans.append(len(arr)-1)
return ans
提交代码评测得到:耗时4402ms,占用内存53MB。
标签:Distance,arr,Addition,After,bisect,ans,Shortest From: https://blog.csdn.net/codename_cys/article/details/140911391