Re: [閒聊] 每日LeetCode已回收
2359. Find Closest Node to Given Two Nodes
給你一個用邊表示的有向圖，節點被編號為0 ~ n-1，再給你兩個點 node1 和 node2，
要你求出節點的編號，他需要滿足：
1.node1和node2和那個點連通
2.node1和node2距離那個點要是所有節點裡最小，若距離相等則取索引較小的節點。
如果不存在滿足條件的節點返回-1。
思路：
1.用兩次BFS找出從node1和node2到所有點的最短距離，還有因為可能存在循環所以要去
重走過的點就不走了。
2.判斷如果node1和node2都和當前點連通且距離更小的話，更新最小值和索引值。
Java Code：
----------------------------------------
class Solution {
public int closestMeetingNode(int[] edges, int node1, int node2) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < edges.length; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < edges.length; i++) {
if (edges[i] == -1) continue;
graph.get(i).add(edges[i]);
}
int[] result1 = BFS(graph, node1);
int[] result2 = BFS(graph, node2);
int index = -1;
int min = Integer.MAX_VALUE;
for (int i = 0; i < edges.length; i++) {
if (result1[i] == -1 || result2[i] == -1) continue;
int maxDistance = Math.max(result1[i], result2[i]);
if (maxDistance < min) {
index = i;
min = maxDistance;
}
}
return index;
}
private int[] BFS(List<List<Integer>> graph, int node) {
int n = graph.size();
int[] result = new int[n];
Arrays.fill(result, -1);
result[node] = 0;
Queue<Integer> queue = new LinkedList<>();
queue.offer(node);
int distance = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int edge = queue.poll();
for (int next : graph.get(edge)) {
if (result[next] == -1) {
queue.offer(next);
}
}
result[edge] = distance;
}
distance++;
}
return result;
}
}
----------------------------------------
--
https://i.imgur.com/3e5CZfj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1674650402.A.F52.html
※ 編輯: Rushia (122.100.75.86 臺灣), 01/25/2023 20:41:23
→
01/26 01:46,
2年前
, 1F
01/26 01:46, 1F
討論串 (同標題文章)
完整討論串 (本文為第 208 之 719 篇)：