Leetcode 3244. Shortest Distance After Road Addition Queries II

• Leetcode 3244. Shortest Distance After Road Addition Queries II
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3244. Shortest Distance After Road Addition Queries II

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。