給定一個有向圖，每個節點最多有一條出邊，用
edges[i]表示（-1 表示無出邊）。給定兩個節點node1和node2，找一個節點使得max(dist(node1, node), dist(node2, node))最小。若有多個答案，回傳編號最小的。
Example:
Input: edges = [2,2,3,-1], node1 = 0, node2 = 1 Output: 2
Intuition
TIP
分別從 node1 和 node2 出發計算到所有可達節點的距離，找兩者都能到達且最大距離最小的節點。
- 每個節點最多一條出邊，所以從任一節點出發的路徑是唯一的
- 分別計算從 node1 和 node2 到所有節點的距離
- 找出兩者都可達的節點中，
max(d1, d2)最小的
Approaches
⭐ 1. Two Distance Passes — O(n) / O(n)
- Idea: 從 node1 和 node2 分別遍歷計算距離，然後遍歷所有節點找最佳答案
- Time:
O(n) - Space:
O(n)
class Solution {
fun closestMeetingNode(edges: IntArray, node1: Int, node2: Int): Int {
val n = edges.size
val dist1 = getDist(edges, node1, n)
val dist2 = getDist(edges, node2, n)
var minDist = Int.MAX_VALUE
var result = -1
for (i in 0 until n) {
if (dist1[i] != -1 && dist2[i] != -1) {
val maxD = maxOf(dist1[i], dist2[i])
if (maxD < minDist) {
minDist = maxD
result = i
}
}
}
return result
}
private fun getDist(edges: IntArray, start: Int, n: Int): IntArray {
val dist = IntArray(n) { -1 }
var cur = start
var d = 0
while (cur != -1 && dist[cur] == -1) {
dist[cur] = d
d++
cur = edges[cur]
}
return dist
}
}2. Same Logic, BFS Form — O(n) / O(n)
- Idea: 用 BFS 風格遍歷計算距離
- Time:
O(n) - Space:
O(n)
class Solution {
fun closestMeetingNode(edges: IntArray, node1: Int, node2: Int): Int {
val n = edges.size
fun bfs(start: Int): IntArray {
val dist = IntArray(n) { -1 }
val queue = ArrayDeque<Int>()
queue.add(start)
dist[start] = 0
while (queue.isNotEmpty()) {
val cur = queue.removeFirst()
val next = edges[cur]
if (next != -1 && dist[next] == -1) {
dist[next] = dist[cur] + 1
queue.add(next)
}
}
return dist
}
val dist1 = bfs(node1)
val dist2 = bfs(node2)
var minDist = Int.MAX_VALUE
var result = -1
for (i in 0 until n) {
if (dist1[i] != -1 && dist2[i] != -1) {
val maxD = maxOf(dist1[i], dist2[i])
if (maxD < minDist) {
minDist = maxD
result = i
}
}
}
return result
}
}🔑 Takeaways
- Pattern: 雙源最短路 — 分別計算兩個起點到所有節點的距離
- Key trick: 每個節點最多一條出邊使得遍歷為 O(n)；用
dist[cur] == -1判斷是否已訪問可偵測環