LeetCode 题解工作台
阈值距离内邻居最少的城市
有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges ，其中 edges[i] = [from i , to i , weight i ] 代表 from i 和 to i 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold 。 返回在路径距离限制为 …
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们可以枚举每个城市 作为起点，使用 Dijkstra 算法求出从 到其他城市的最短距离，然后统计距离不超过阈值的城市个数，最后取最小的个数且编号最大的城市。 时间复杂度 ，空间复杂度 。其中 为城市个数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。
返回在路径距离限制为 distanceThreshold 以内可到达城市最少的城市。如果有多个这样的城市，则返回编号最大的城市。
注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。
示例 1：
输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 输出：3 解释：城市分布图如上。 每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是： 城市 0 -> [城市 1, 城市 2] 城市 1 -> [城市 0, 城市 2, 城市 3] 城市 2 -> [城市 0, 城市 1, 城市 3] 城市 3 -> [城市 1, 城市 2] 城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。
示例 2：
输入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2 输出：0 解释：城市分布图如上。 每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是： 城市 0 -> [城市 1] 城市 1 -> [城市 0, 城市 4] 城市 2 -> [城市 3, 城市 4] 城市 3 -> [城市 2, 城市 4] 城市 4 -> [城市 1, 城市 2, 城市 3] 城市 0 在阈值距离 2 以内只有 1 个邻居城市。
提示：
2 <= n <= 1001 <= edges.length <= n * (n - 1) / 2edges[i].length == 30 <= fromi < toi < n1 <= weighti, distanceThreshold <= 10^4- 所有
(fromi, toi)都是不同的。
解题思路
方法一：Dijkstra 算法
我们可以枚举每个城市 作为起点，使用 Dijkstra 算法求出从 到其他城市的最短距离，然后统计距离不超过阈值的城市个数，最后取最小的个数且编号最大的城市。
时间复杂度 ，空间复杂度 。其中 为城市个数。
class Solution:
def findTheCity(
self, n: int, edges: List[List[int]], distanceThreshold: int
) -> int:
def dijkstra(u: int) -> int:
dist = [inf] * n
dist[u] = 0
vis = [False] * n
for _ in range(n):
k = -1
for j in range(n):
if not vis[j] and (k == -1 or dist[k] > dist[j]):
k = j
vis[k] = True
for j in range(n):
# dist[j] = min(dist[j], dist[k] + g[k][j])
if dist[k] + g[k][j] < dist[j]:
dist[j] = dist[k] + g[k][j]
return sum(d <= distanceThreshold for d in dist)
g = [[inf] * n for _ in range(n)]
for f, t, w in edges:
g[f][t] = g[t][f] = w
ans, cnt = n, inf
for i in range(n - 1, -1, -1):
if (t := dijkstra(i)) < cnt:
cnt, ans = t, i
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n^3) |
| 空间 | O(n^2) |
面试官常问的追问
外企场景- question_mark
The candidate should show understanding of graph algorithms, specifically Floyd-Warshall or Dijkstra.
- question_mark
Look for the ability to identify the most efficient approach for all-pairs shortest path calculation.
- question_mark
Test if the candidate can optimize space and time by leveraging dynamic programming techniques.
常见陷阱
外企场景- error
Misunderstanding the problem’s threshold condition can lead to incorrect results when counting neighbors.
- error
Not considering the possibility of ties in the number of reachable neighbors can result in returning the wrong city.
- error
Failing to apply the correct graph algorithm, leading to inefficiency or incorrect shortest path calculations.
进阶变体
外企场景- arrow_right_alt
Changing the graph representation (e.g., adjacency matrix vs adjacency list) could affect the implementation.
- arrow_right_alt
Increasing the number of cities could require considering optimizations in the graph algorithm used.
- arrow_right_alt
Allowing varying threshold values for different cities introduces a challenge in dynamic adjustment of the problem constraints.