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

原题链接：

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算法
1
2
3
4
5
6
7
8
9
10
11
12
13

参考代码：

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;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

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;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

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;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61