LeetCode 题解工作台
恢复网络路径
给你一个包含 n 个节点（编号从 0 到 n - 1 ）的有向无环图。图由长度为 m 的二维数组 edges 表示，其中 edges[i] = [u i , v i , cost i ] 表示从节点 u i 到节点 v i 的单向通信，恢复成本为 cost i 。 一些节点可能处于离线状态。给定一个…
7
题型
0
代码语言
3
相关题
当前训练重点
困难 · 二分查找
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分查找 题型思路
题目描述
给你一个包含 n 个节点（编号从 0 到 n - 1）的有向无环图。图由长度为 m 的二维数组 edges 表示，其中 edges[i] = [ui, vi, costi] 表示从节点 ui 到节点 vi 的单向通信，恢复成本为 costi。
一些节点可能处于离线状态。给定一个布尔数组 online，其中 online[i] = true 表示节点 i 在线。节点 0 和 n - 1 始终在线。
从 0 到 n - 1 的路径如果满足以下条件，那么它是 有效 的：
- 路径上的所有中间节点都在线。
- 路径上所有边的总恢复成本不超过
k。
对于每条有效路径，其 分数 定义为该路径上的最小边成本。
返回所有有效路径中的 最大 路径分数（即最大 最小 边成本）。如果没有有效路径，则返回 -1。
示例 1:
输入: edges = [[0,1,5],[1,3,10],[0,2,3],[2,3,4]], online = [true,true,true,true], k = 10
输出: 3
解释:
-
图中有两条从节点 0 到节点 3 的可能路线：
-
路径
0 → 1 → 3-
总成本 =
5 + 10 = 15，超过了 k (15 > 10)，因此此路径无效。
-
-
路径
0 → 2 → 3-
总成本 =
3 + 4 = 7 <= k，因此此路径有效。 -
此路径上的最小边成本为
min(3, 4) = 3。
-
-
-
没有其他有效路径。因此，所有有效路径分数中的最大值为 3。
示例 2:
输入: edges = [[0,1,7],[1,4,5],[0,2,6],[2,3,6],[3,4,2],[2,4,6]], online = [true,true,true,false,true], k = 12
输出: 6
解释:
-
节点 3 离线，因此任何通过 3 的路径都是无效的。
-
考虑从 0 到 4 的其余路线：
-
路径
0 → 1 → 4-
总成本 =
7 + 5 = 12 <= k，因此此路径有效。 -
此路径上的最小边成本为
min(7, 5) = 5。
-
-
路径
0 → 2 → 3 → 4-
节点 3 离线，因此无论成本多少，此路径无效。
-
-
路径
0 → 2 → 4-
总成本 =
6 + 6 = 12 <= k，因此此路径有效。 -
此路径上的最小边成本为
min(6, 6) = 6。
-
-
-
在两条有效路径中，它们的分数分别为 5 和 6。因此，答案是 6。
提示:
n == online.length2 <= n <= 5 * 1040 <= m == edges.length <= min(105, n * (n - 1) / 2)edges[i] = [ui, vi, costi]0 <= ui, vi < nui != vi0 <= costi <= 1090 <= k <= 5 * 1013online[i]是true或false，且online[0]和online[n - 1]均为true。- 给定的图是一个有向无环图。
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of edges and the binary search for the minimum edge cost. Space complexity is influenced by the graph structure and dynamic programming states, both of which scale with the number of nodes and edges in the graph. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate understands the importance of topological sorting in a directed acyclic graph.
- question_mark
Candidate can explain the concept of binary search applied to this problem's constraints.
- question_mark
Candidate demonstrates knowledge of dynamic programming for path validation and optimization.
常见陷阱
外企场景- error
Forgetting to handle offline nodes correctly when checking for valid paths.
- error
Incorrectly applying binary search without verifying that all conditions hold for the chosen minimum edge-cost.
- error
Failing to optimize the approach for large graphs and edge cases like minimal or maximal path costs.
进阶变体
外企场景- arrow_right_alt
Consider paths with additional constraints, such as node weights or multiple recovery cost limits.
- arrow_right_alt
Modify the problem to consider undirected graphs or graphs with cycles.
- arrow_right_alt
Increase the complexity by adding time constraints or more nodes and edges.