leetcode
leetcode 2051 ~ 2100
找到离给定两个节点最近的节点

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

难度:

标签:

题目描述

给你一个 n 个节点的 有向图 ,节点编号为 0 到 n - 1 ,每个节点 至多 有一条出边。

有向图用大小为 n 下标从 0 开始的数组 edges 表示,表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边,那么 edges[i] == -1 。

同时给你两个节点 node1 和 node2 。

请你返回一个从 node1 和 node2 都能到达节点的编号,使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案,请返回 最小 的节点编号。如果答案不存在,返回 -1 。

注意 edges 可能包含环。

 

示例 1:

输入:edges = [2,2,3,-1], node1 = 0, node2 = 1
输出:2
解释:从节点 0 到节点 2 的距离为 1 ,从节点 1 到节点 2 的距离为 1 。
两个距离的较大值为 1 。我们无法得到一个比 1 更小的较大值,所以我们返回节点 2 。

示例 2:

输入:edges = [1,2,-1], node1 = 0, node2 = 2
输出:2
解释:节点 0 到节点 2 的距离为 2 ,节点 2 到它自己的距离为 0 。
两个距离的较大值为 2 。我们无法得到一个比 2 更小的较大值,所以我们返回节点 2 。

 

提示:

  • n == edges.length
  • 2 <= n <= 105
  • -1 <= edges[i] < n
  • edges[i] != i
  • 0 <= node1, node2 < n

代码结果

运行时间: 64 ms, 内存: 27.8 MB


/*
题目思路:
1. 使用广度优先搜索计算从node1和node2到其他节点的最短距离。
2. 使用Java Stream来处理节点的距离和找到最小的最大距离节点。
3. 如果没有满足条件的节点,返回-1。
*/

import java.util.*;
import java.util.stream.IntStream;

public class Solution {
    public int findClosestMeetingNode(int[] edges, int node1, int node2) {
        int n = edges.length;
        int[] dist1 = bfs(edges, node1);
        int[] dist2 = bfs(edges, node2);
        
        return IntStream.range(0, n)
                .filter(i -> dist1[i] < Integer.MAX_VALUE && dist2[i] < Integer.MAX_VALUE)
                .mapToObj(i -> new int[]{i, Math.max(dist1[i], dist2[i])})
                .min(Comparator.<int[]>comparingInt(a -> a[1]).thenComparingInt(a -> a[0]))
                .map(a -> a[0])
                .orElse(-1);
    }
    
    private int[] bfs(int[] edges, int start) {
        int n = edges.length;
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        dist[start] = 0;
        
        while (!queue.isEmpty()) {
            int node = queue.poll();
            int neighbor = edges[node];
            if (neighbor != -1 && dist[neighbor] == Integer.MAX_VALUE) {
                dist[neighbor] = dist[node] + 1;
                queue.offer(neighbor);
            }
        }
        
        return dist;
    }
}

解释

方法:

该题解采用的是同时从两个节点开始追踪路径的策略。首先,创建两个布尔数组flag_1和flag_2来标记从node1和node2出发访问过的节点。接着,从两个节点同时开始沿着有向图的边走,直到两者相遇或到达终点。过程中检查对方是否已经访问过当前节点,若是,则返回当前节点,因为这意味着找到了一个共同可达节点。如果在某一步中,一个节点无法再前进(即该节点没有出边或到达了先前访问过的节点),则停止并返回-1,表示不存在这样的节点。这种方法利用了双指针的思想,同时追踪两个节点的路径,直到它们相遇。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在题解中使用的同时追踪两个节点路径的策略,该策略是否考虑了图中可能存在的环形结构对算法的影响?
题解中的策略确实考虑到了环形结构的存在。由于使用了两个布尔数组flag_1和flag_2来标记每个节点是否被访问过,这样一来,即使图中存在环,一旦某个节点再次被访问时,算法将不会进入该节点,从而避免了无限循环。这种方法可以有效地处理环形结构,确保算法总能在有限步骤内返回结果或者判断不存在共同节点。
🦆
为什么题解在两个节点都不能前进时直接返回-1?是否有可能存在其他未被考虑到的节点作为合适的最近共同节点?
题解中直接返回-1的情况是基于算法的逻辑,当两个节点都无法前进时(即没有未访问的出边),说明已经探索了所有可能的路径。由于从两个节点出发的路径都已经追踪完毕且没有交点,因此可以确定不存在其他未被考虑到的节点作为合适的最近共同节点。这种情况下,返回-1表示在现有图结构中,没有共同的可达节点。
🦆
题解中提到,如果节点已经被对方访问过则可判断为共同可达节点,这种方法在有向图中是否总是有效?
这种方法在有向图中基本上是有效的,尤其是在本题的上下文中,因为问题的设置是找到两个节点的最近共同节点。如果一个节点已经被对方访问过,那么这意味着从两个起始节点都可以到达这个节点。然而,需要注意的是,这种方法假设了节点的可达性是对称的,即如果从A可达B,则从B也可以回到A。在某些特定的有向图结构中(如不对称的),这个假设可能不成立。但对于本题的目的而言,这种方法是适用的。
🦆
题解假设了每个节点至多有一条出边,这个假设是否限制了算法的通用性?如果图中允许节点有多条出边,该如何调整算法?
题解中的假设确实限制了算法的通用性,因为它只适用于每个节点至多有一条出边的场景。如果在一个更一般的图中,节点可能有多条出边,算法需要调整以处理这种复杂性。一种可能的调整是使用广度优先搜索(BFS)。对每个节点,我们可以维护一个队列来探索所有可能的出边,同时还需要标记访问过的节点以避免重复访问。这种方法能够在更一般的图结构中找到最近的共同可达节点。

相关问题