LeetCode 题解工作台
网络空闲的时刻
给你一个有 n 个服务器的计算机网络，服务器编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [u i , v i ] 表示服务器 u i 和 v i 之间有一条信息线路，在 一秒 内它们之间可以传输 任意 数目的信息。再给你一个长度为 n 且下标从 …
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们先根据二维数组 构建无向图 ，其中 表示节点 的所有邻居节点。 然后，我们可以使用广度优先搜索的方式，找出每个节点 距离主服务器的最短距离 ，那么节点 发出信息后，最早能收到回复的时间为 $2 \times d_i$。由于每个数据服务器 每隔 会重发一条信息，因此，每个数据服务器最后一次发出信息的时间为 $(2 \times d_i - 1) / patience[i] \tim…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个有 n 个服务器的计算机网络，服务器编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示服务器 ui 和 vi 之间有一条信息线路，在 一秒 内它们之间可以传输 任意 数目的信息。再给你一个长度为 n 且下标从 0 开始的整数数组 patience 。
题目保证所有服务器都是 相通 的，也就是说一个信息从任意服务器出发，都可以通过这些信息线路直接或间接地到达任何其他服务器。
编号为 0 的服务器是 主 服务器，其他服务器为 数据 服务器。每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按 最优 线路传输，也就是说每个信息都会以 最少时间 到达主服务器。主服务器会处理 所有 新到达的信息并 立即 按照每条信息来时的路线 反方向 发送回复信息。
在 0 秒的开始，所有数据服务器都会发送各自需要处理的信息。从第 1 秒开始，每 一秒最 开始 时，每个数据服务器都会检查它是否收到了主服务器的回复信息（包括新发出信息的回复信息）：
- 如果还没收到任何回复信息，那么该服务器会周期性 重发 信息。数据服务器
i每patience[i]秒都会重发一条信息，也就是说，数据服务器i在上一次发送信息给主服务器后的patience[i]秒 后 会重发一条信息给主服务器。 - 否则，该数据服务器 不会重发 信息。
当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为 空闲 状态。
请返回计算机网络变为 空闲 状态的 最早秒数 。
示例 1：
输入：edges = [[0,1],[1,2]], patience = [0,2,1] 输出：8 解释： 0 秒最开始时， - 数据服务器 1 给主服务器发出信息（用 1A 表示）。 - 数据服务器 2 给主服务器发出信息（用 2A 表示）。 1 秒时， - 信息 1A 到达主服务器，主服务器立刻处理信息 1A 并发出 1A 的回复信息。 - 数据服务器 1 还没收到任何回复。距离上次发出信息过去了 1 秒（1 < patience[1] = 2），所以不会重发信息。 - 数据服务器 2 还没收到任何回复。距离上次发出信息过去了 1 秒（1 == patience[2] = 1），所以它重发一条信息（用 2B 表示）。 2 秒时， - 回复信息 1A 到达服务器 1 ，服务器 1 不会再重发信息。 - 信息 2A 到达主服务器，主服务器立刻处理信息 2A 并发出 2A 的回复信息。 - 服务器 2 重发一条信息（用 2C 表示）。 ... 4 秒时， - 回复信息 2A 到达服务器 2 ，服务器 2 不会再重发信息。 ... 7 秒时，回复信息 2D 到达服务器 2 。 从第 8 秒开始，不再有任何信息在服务器之间传输，也不再有信息到达服务器。 所以第 8 秒是网络变空闲的最早时刻。
示例 2：
输入：edges = [[0,1],[0,2],[1,2]], patience = [0,10,10] 输出：3 解释：数据服务器 1 和 2 第 2 秒初收到回复信息。 从第 3 秒开始，网络变空闲。
提示：
n == patience.length2 <= n <= 105patience[0] == 0- 对于
1 <= i < n，满足1 <= patience[i] <= 105 1 <= edges.length <= min(105, n * (n - 1) / 2)edges[i].length == 20 <= ui, vi < nui != vi- 不会有重边。
- 每个服务器都直接或间接与别的服务器相连。
解题思路
方法一：BFS
我们先根据二维数组 构建无向图 ，其中 表示节点 的所有邻居节点。
然后，我们可以使用广度优先搜索的方式，找出每个节点 距离主服务器的最短距离 ，那么节点 发出信息后，最早能收到回复的时间为 。由于每个数据服务器 每隔 会重发一条信息，因此，每个数据服务器最后一次发出信息的时间为 ，那么最后收到回复的时间为 ，再加上 秒的处理时间，即为该数据服务器变为空闲的最早时间。我们找出最晚的这个时间，即为计算机网络变为空闲的最早时间。
时间复杂度 ，空间复杂度 。其中 为节点数。
class Solution:
def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
g[v].append(u)
q = deque([0])
vis = {0}
ans = d = 0
while q:
d += 1
t = d * 2
for _ in range(len(q)):
u = q.popleft()
for v in g[u]:
if v not in vis:
vis.add(v)
q.append(v)
ans = max(ans, (t - 1) // patience[v] * patience[v] + t + 1)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Understanding BFS traversal and its application to graph problems is key to solving this problem.
- question_mark
The ability to simulate resending based on a time threshold shows the candidate's understanding of dynamic processes.
- question_mark
Being able to optimize for large input sizes, ensuring that the solution can handle up to 10^5 servers, demonstrates scalability.
常见陷阱
外企场景- error
Forgetting to account for the patience array when determining whether to resend a message.
- error
Not simulating the message traffic accurately, which could lead to incorrect idle time calculations.
- error
Overlooking edge cases where multiple servers resend messages at different times due to varying patience values.
进阶变体
外企场景- arrow_right_alt
What if the patience value for all servers was the same?
- arrow_right_alt
How would the solution change if some servers had infinite patience and would resend indefinitely?
- arrow_right_alt
What if we used a different graph traversal method other than BFS, like DFS, to solve the problem?