LEETCODE 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance 解题思路分析

题目大意:

阈值距离内邻居最少的城市

有 n 个城市,按从 0 到 n-1 编号。给你一个边数组 edges,其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边,距离阈值是一个整数 distanceThreshold。

返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市,则返回编号最大的城市。

注意,连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。

示例 1:

输入:n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
输出:3
解释:城市分布图如上。
 每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是:
 城市 0 -> [城市 1, 城市 2] 
 城市 1 -> [城市 0, 城市 2, 城市 3] 
 城市 2 -> [城市 0, 城市 1, 城市 3] 
 城市 3 -> [城市 1, 城市 2] 
 城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市,但是我们必须返回城市 3,因为它的编号最大。

示例 2:

输入:n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
输出:0
解释:城市分布图如上。 
 每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是:
 城市 0 -> [城市 1] 
 城市 1 -> [城市 0, 城市 4] 
 城市 2 -> [城市 3, 城市 4] 
 城市 3 -> [城市 2, 城市 4]
 城市 4 -> [城市 1, 城市 2, 城市 3] 
 城市 0 在阈值距离 4 以内只有 1 个邻居城市。

提示:

  • 2 <= n <= 100
  • 1 <= edges.length <= n * (n – 1) / 2
  • edges[i].length == 3
  • 0 <= fromi < toi < n
  • 1 <= weighti, distanceThreshold <= 10^4
  • 所有 (fromi, toi) 都是不同的。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1334

解题思路分析:

这是一道有关图的题目,每一个城市相当于一个节点,两个城市间的连线代表两个城市间的距离,另外题目定义了一个邻居城市的概念,即与当前城市距离小于等于distanceThreshold的所有城市。题目要求求出邻居城市数目最少的城市。

对于图进行路径搜索时,dfs是一个不错的选择,本题也不例外。首先明确一点,为了求邻居个数最少得城市,我们需要求出所有城市的邻居城市个数才能比较,所以我们应该以每一个城市作为起点进行dfs操作,以取得其邻居个数。然后,对于每条dfs路线,其终点应该在于终点城市与起点城市间的距离小于等于 distanceThreshold 。超过该阈值的节点都不能包含在当前dfs路线内。最后还需要考虑一个非常重要的条件,即如何处理已经遍历过的节点。

对于简单的dfs题来说,每条dfs路线一般会一条路走到底,因此当其他路线遇到已经访问过的节点时,该节点以下的路径我们已经遍历过,因此无须再继续走下去。然而对于本题,路径的终点是有条件的,即上文提到的 distanceThreshold 。这样一来,当遇到已访问过的节点时,我们可能需要继续走下去,举个例子,比如下面这张图:

leetcode 1334 例子

如果 distanceThreshold是4,我们从节点1出发开始dfs所有路线,如果先走到节点2,再走到节点4,此时节点4距离起点1的距离刚好等于阈值4,这时当前dfs路径结束,路径上的点1,2,4均被标记为已访问状态。接下来继续走另外一条线路,从节点1出发,路过节点3,再到达节点4,此时,节点4已经被访问过,如果此时终止该路径,我们将失去对节点5的访问,但是从图中我们很容易看出,节点5与节点1间的距离为3,它也是节点1的邻居,对于这种情况我们应该如何处理?

我采用的方式是,使用int型数组取代bool型访问数组,当访问过某一个节点后,我们不能统一将其标记为已访问状态,而是在访问数组中将该节点的状态记录成为dfs路径走到该点时,阈值与已走距离的差值,该差值其实代表了当前dfs路线还能走多远。当其他路线再次经过该点时,比较当前差值与访问数组中的差值,如果当前差值大于等于访问数组,说明我们可以继续走下去(比原先路线会走的更远),反之则可以终止当前dfs路线。这样一来就解决了遇到已访问节点时的难题。

不过随之而来就会产生另外一个问题,因为某些节点会被不同的路线重复经过,这样在统计路线上节点数量时会出现重复统计的情况,因此我们还需要维护另外一个数组,记录哪些节点已经被统计过,未被统计过的节点需要计数。

实现代码:

public int findTheCity(int n, int[][] edges, int distanceThreshold) {
    // 构建出图结构
    int[][] map = new int[n][n];
    for(int[] edge : edges){
        map[edge[0]][edge[1]]=edge[2];
        map[edge[1]][edge[0]]=edge[2];
    }
    // 最少邻居数
    int min=n;
    // 邻居数最少的节点
    int res=0;
    // 循环每一个节点,以该节点为起点进行dfs
    for(int i=0;i<n;i++){
        // 为了避免重复统计相同邻居,存储已经被记录为邻居的节点
        boolean[] v = new boolean[n];
        // 当前节点不能是自己的邻居,默认为已被记录
        v[i]=true;
        // dfs求出当前节点的邻居个数
        int count=dfs(map,i,distanceThreshold,v,new int[n]);
        // 如果邻居数小于全局最小值
        if(count<=min){
            // 更新全局最小邻居数
            min=count;
            // 当前节点为返回值候选人
            res=i;
        }
    }
    return res;
}
// map:图结构
// city:当前城市
// dis:当前所剩距离
// v:已经被记录为邻居的节点
// maxDis:走到某个节点时,剩余距离的最大值
// 返回值为当前城市的邻居数。
int dfs(int[][] map, int city, int dis, boolean[] v, int[] maxDis){
    int res=0; // 返回值
    // 循环当前城市的所有相邻城市
    for(int i=0;i<map[0].length;i++){
        // 与相邻城市的距离,如果为0,说明与该城市不相连
        int distance = map[city][i];
        // 到达相邻城市后,与阈值相比的剩余距离。
        int diffDis=dis-distance;
        // 与该城市相连并且剩余距离大于等于访问数组中的值
        if(distance>0&&diffDis>=maxDis[i]){
            // 更新访问数组中的剩余距离
            maxDis[i]=diffDis;
            // 如果该城市未被记录为邻居
            if(!v[i]){
                // 设置为已经被记录为邻居
                v[i]=true;
                // 邻居数加一
                res++;
            }
            // 递归dfs与该城市相连的其他城市
            res+=dfs(map,i,diffDis,v,maxDis);
        }
    }
    return res;
}

本题解法执行时间为223ms。

Runtime: 223 ms, faster than 29.84% of Java online submissions for Find the City With the Smallest Number of Neighbors at a Threshold Distance.

Memory Usage: 41 MB, less than 100.00% of Java online submissions for Find the City With the Smallest Number of Neighbors at a Threshold Distance.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。