2359.找到离给定两个节点最近的节点

首先肯定要计算节点到各个节点之间的最短距离。由于是有向图因此可以通过循环实现找到节点到其他节点的路径及距离。
最后选出里node1和node2最远距离最小的点即可。

Java

class Solution {
    public int closestMeetingNode(int[] edges, int node1, int node2) {
        int[] dist1 = computeDistance(edges, node1);
        int[] dist2 = computeDistance(edges, node2);

        int res = -1;
        int minDistance = Integer.MAX_VALUE;
        
        for (int i = 0; i < edges.length; i++){
            if (dist1[i] != -1 && dist2[i] != -1){
                int maxDist = Math.max(dist1[i], dist2[i]);
                if (maxDist < minDistance){
                    minDistance = maxDist;
                    res = i;
                }
            }
        }

        return res;
    }

    public int[] computeDistance(int[] edges, int startNode){
        int n = edges.length;
        // 初始化
        int[] dist = new int[n];
        Arrays.fill(dist, -1);

        int current = startNode;
        int d = 0;

        while(current != -1 && dist[current] == -1){
            dist[current] = d++;
            current = edges[current];
        }

        return dist;
    }
}

C++

class Solution {
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        vector<int> dist1 = computeDistance(edges, node1);
        vector<int> dist2 = computeDistance(edges, node2);

        int n = edges.size();
        int res = -1;
        int minDistance = INT_MAX;
        
        for (int i = 0; i < n; i++){
            if (dist1[i] != -1 && dist2[i] != -1){
                int maxDist = max(dist1[i], dist2[i]);
                if (maxDist < minDistance){
                    minDistance = maxDist;
                    res = i;
                }
            }
        }

        return res;
    }

    vector<int> computeDistance(const vector<int>& edges, int startNode){
        int n = edges.size();
        // 初始化
        vector<int> dist(n, -1);
        int d = 0;
        int current = startNode;
        while(current != -1 && dist[current] == -1){
            dist[current] = d++;
            current = edges[current];
        }

        return dist;
    }
};