1334. 阈值距离内邻居最少的城市
原题链接：
https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/solutions
完成情况：
解题思路：
给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边
距离阈值是一个整数 distanceThreshold。
返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。
返回要求：
距离路径最大，且相连城市最少，然后同情况下编号最大的城市。
他的邻居指的不是相邻，而是只要在<=最大 为 distanceThreshold 的城市
解法：
对每一个节点，去计算满足在<=最大 为 distanceThreshold结点内的邻居数量，然后挨个节点去判断谁的邻居最少，并且节点编号能够更大。
题目就转化成了对所有节点，计算到其他结点的最短路径 Dijkstra算法 && Floyd算法
参考代码：
Dijkstra
package LeetCode中等题02;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class __1334阈值距离内邻居最少的城市__Dijkstra{
/**
*
* @param n
* @param edges
* @param distanceThreshold
* @return
*/
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
/** 给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边
距离阈值是一个整数 distanceThreshold。
返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。
返回要求：
距离路径最大，且相连城市最少，然后同情况下编号最大的城市。
他的邻居指的不是相邻，而是只要在<=最大 为 distanceThreshold 的城市
解法：
对每一个节点，去计算满足在<=最大 为 distanceThreshold结点内的邻居数量，然后挨个节点去判断谁的邻居最少，并且节点编号能够更大。
题目就转化成了对所有节点，计算到其他结点的最短路径 Dijkstra算法 && Floyd算法
*/
List<int []> adjacentArray [] = new List[n];
for (int i = 0;i<n;i++){
adjacentArray[i] = new ArrayList<int[]>();
}
for (int edge [] : edges){
int cityA = edge[0],cityB = edge[1],weigth = edge[2];
adjacentArray[cityA].add(new int[]{cityB,weigth});
adjacentArray[cityB].add(new int[]{cityA,weigth});
}
int leastCity = Integer.MIN_VALUE,leastNeightbors = Integer.MAX_VALUE;
for (int i=n-1;i>=0;i--){
int neighbors = Dijkstra(adjacentArray,i,distanceThreshold);
if (leastNeightbors > neighbors){
leastCity = i;
leastNeightbors = neighbors;
}
}
return leastCity;
}
/**
*
* @param adjacentArray
* @param sourceFrom
* @param distanceThreshold
* @return
*/
private int Dijkstra(List<int[]>[] adjacentArray, int sourceFrom, int distanceThreshold) {
int n = adjacentArray.length;
int distancces [] = new int[n];
Arrays.fill(distancces,Integer.MAX_VALUE / 2);
distancces[sourceFrom] = 0;
boolean [] visited = new boolean[n];
for (int i = 0;i<n;i++){
int curr = -1;
for (int j=0;j<n;j++){
if (!visited[j] && (curr < 0 || distancces[curr] > distancces[j])){
curr = j;
}
}
visited[curr] = true;
for (int [] adjacent: adjacentArray[curr]){
int next = adjacent[0],weight = adjacent[1];
distancces[next] = Math.min(distancces[next],distancces[curr] + weight);
}
}
int neighbors = 0;
for (int i = 0;i<n;i++){
if (i == sourceFrom){
continue;
}
if (distancces[i] <= distanceThreshold){
neighbors++;
}
}
return neighbors;
}
}
Dijkstra_小顶堆
package LeetCode中等题02;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class __1334阈值距离内邻居最少的城市__Dijkstra_小顶堆 {
/**
* @param n
* @param edges
* @param distanceThreshold
* @return
*/
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
List<int []> adjacentArray [] = new List[n];
for (int i = 0;i<n;i++){
adjacentArray[i] = new ArrayList<int[]>();
}
for (int edge [] : edges){
int cityA = edge[0],cityB = edge[1],weigth = edge[2];
adjacentArray[cityA].add(new int[]{cityB,weigth});
adjacentArray[cityB].add(new int[]{cityA,weigth});
}
int leastCity = Integer.MIN_VALUE,leastNeightbors = Integer.MAX_VALUE;
for (int i=n-1;i>=0;i--){
int neighbors = Dijkstra(adjacentArray,i,distanceThreshold);
if (leastNeightbors > neighbors){
leastCity = i;
leastNeightbors = neighbors;
}
}
return leastCity;
}
/**
*
* @param adjacentArray
* @param sourceFrom
* @param distanceThreshold
* @return
*/
private int Dijkstra(List<int[]>[] adjacentArray, int sourceFrom, int distanceThreshold) {
int n = adjacentArray.length;
int distancces [] = new int[n];
Arrays.fill(distancces,Integer.MAX_VALUE );
distancces[sourceFrom] = 0;
//小顶堆，是基于队列
//Deque实现stack，PriorityQueue实现queue
PriorityQueue<int []> pQueue = new PriorityQueue<int []>((a,b) -> a[1] - b[1]); //直接插入比较规则
pQueue.offer(new int[]{sourceFrom,0});
while (!pQueue.isEmpty()){
int pair[] = pQueue.poll();
int curr = pair[0],distancce = pair[1];
for (int [] adjancet : adjacentArray[curr]){
int next = adjancet[0],weight = adjancet[1];
if (distancces[next] > distancce + weight){
distancces[next] = distancce + weight;
pQueue.offer(new int[]{next,distancces[next]});
}
}
}
int neightbors = 0;
for (int i = 0;i<n;i++){
if (i == sourceFrom){
continue;
}
if (distancces[i] <= distanceThreshold){
neightbors++;
}
}
return neightbors;
}
}
Floyd_martix方法
package LeetCode中等题02;
import java.util.Arrays;
public class __1334阈值距离内邻居最少的城市__Floyd_martix方法 {
/**
*
* @param n
* @param edges
* @param distanceThreshold
* @return
*/
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
int [][] matrix = new int[n][n];
for (int i = 0;i<n;i++){
Arrays.fill(matrix[i],Integer.MAX_VALUE / 2);
}
for (int edge [] : edges){
int cityA = edge[0],cityB = edge[1],weigth = edge[2];
matrix[cityA][cityB] = matrix[cityB][cityA] = weigth;
}
for (int k = 0;k<n;k++){
for (int i = 0;i<n;i++){
for (int j = 0;j<n;j++){
matrix[i][j] = Math.min(matrix[i][j],matrix[i][k] + matrix[k][j]);
}
}
}
int leastCity = -1,leastNeightbors = Integer.MAX_VALUE;
for (int i = n-1;i>=0;i--){
int neightbors = countNeughtbors_Floyd(matrix,i,distanceThreshold);
if (leastNeightbors > neightbors){
leastCity = i;
leastNeightbors = neightbors;
}
}
return leastCity;
}
/**
*
* @param matrix
* @param i
* @param distanceThreshold
* @return
*/
private int countNeughtbors_Floyd(int[][] matrix, int sourceFrom, int distanceThreshold) {
int neightbors = 0;
int n = matrix.length;
for (int i = 0;i<n;i++){
if (i == sourceFrom){
continue;
}
if (matrix[sourceFrom][i] <= distanceThreshold){
neightbors++;
}
}
return neightbors;
}
}
