Re: [閒聊] 每日leetcode

https://leetcode.com/problems/find-closest-node-to-given-two-nodes 2359. Find Closest Node to Given Two Nodes 給你一個陣列表示有向圖的邊，每個點最多只會有一個向外的邊，給你兩個整數node1和 node2，找出一個節點node1和node2都可以到，且兩個點到的距離取最大最小的結果，如 果無解返回-1。 思路： 1.用BFS求出每個點的最短距離，然後取最大最小即可。 Java Code: --------------------------------------- class Solution { public int closestMeetingNode(int[] edges, int node1, int node2) { int[] dis1 = getDis(edges, node1); int[] dis2 = getDis(edges, node2); int res = -1; int min = Integer.MAX_VALUE; for (int i = 0; i < edges.length; i++) { if (dis1[i] == Integer.MAX_VALUE || dis2[i] == Integer.MAX_VALUE) { continue; } int max = Math.max(dis1[i], dis2[i]); if (max < min) { min = max; res = i; } } return res; } private int[] getDis(int[] edges, int id) { int[] dis = new int[edges.length]; Arrays.fill(dis, Integer.MAX_VALUE); dis[id] = 0; Queue<Integer> queue = new ArrayDeque<>(); queue.offer(id); while (!queue.isEmpty()) { int cur = queue.poll(); int next = edges[cur]; if (next == -1 || dis[next] != Integer.MAX_VALUE) { continue; } dis[next] = dis[cur] + 1; queue.offer(next); } return dis; } } --------------------------------------- -- https://i.imgur.com/ZUx84aU.jpeg --
※ 批踢踢實業坊(ptt.cc), 來自: 49.159.104.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1748629773.A.1E3.html