题目大意：
阈值距离内邻居最少的城市
有 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 。这样一来，当遇到已访问过的节点时，我们可能需要继续走下去，举个例子，比如下面这张图：
如果 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.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance-解题思路分析/