LeetCode-图的建立和迪杰斯特拉算法以及数组的分组和排序轮转

882. 细分图中的可到达节点

题目描述

给你一个无向图（原始图），图中有 n 个节点，编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链，每条边之间的新节点数各不相同。

882. 细分图中的可到达节点

解题分析

edge[][] 二维数组存储的是图中的每一条边，每一行也就是一条边具有三列分别是起点，终点，路长。自定义数组存储图的关系信息，通过 dijkstra 算法 求解指定点到每一个节点的最短路径，返回 dist[] 数组保存到达的节点的最短路径。遍历 dist[] 数组，距离小于指定的最大长度就是图中符合要求的可达节点，再遍历每一条边，统计边上可达的路径长度，即是小于等于最大的移动距离

代码

public int reachableNodes(int[][] edges, int maxMoves, int n) {
        // 保存这个节点的可达性，建立图
        List<int[]>[] graph = new ArrayList[n];
        Arrays.setAll(graph, e -> new ArrayList<int[]>());
        for(int[] edge : edges){
            int u = edge[0],v = edge[1],cnt = edge[2];
            // 建立图，节点和连接节点关系
            graph[u].add(new int[]{v,cnt+1});
            graph[v].add(new int[]{u,cnt+1});
        }

        // 从 0 出发的最短路
        int[] dist = dijkstra(graph, 0);

        int res = 0;
        // 可达节点的个数
        for(int x : dist){
            if(x <= maxMoves) res++;
        }
        // 节点之间边上增加的个数
        for(int[] edge : edges){
            int u = edge[0],v = edge[1],cnt = edge[2];
            res +=Math.min(cnt,Math.max(maxMoves-dist[u],0)+Math.max(maxMoves-dist[v],0));
        }
        return res;
    }
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

dijkstra

    // dijkstra 求取 start 到各个节点的最短路径
    public int[] dijkstra(List<int[]>[] graph,int start){
        // 初始化距离数组全部为最大值，到大本身的距离是0
        int[] dist = new int[graph.length];
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[start] = 0;
        // 小顶堆存储到达每一个节点的最短距离
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
        pq.offer(new int[]{start,0});
        while(!pq.isEmpty()){
            // 堆顶的元素和最短距离
            int[] curNode = pq.poll();
            int x = curNode[0],d = curNode[1];
            if(d > dist[x]) continue;
            // 遍历节点元素的可达路径，更新最短距离，并且
            for(int[] e : graph[x]){
                int y = e[0];
                int curDist = d + e[1];
                if(curDist < dist[y]){
                    dist[y] = curDist;
                    pq.offer(new int[]{y,curDist});
                }
            }
        }
        return dist;
    }
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

743. 网络延迟时间

题目描述

有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

743. 网络延迟时间

解题分析

从节点 k 出发，到达其他节点的最短路径的最大值，如果存在不可达的节点，直接返回-1
通过迪杰斯特拉算法求取目标节点k到达每一和个节点的最短路径，遍历这个距离数组，一旦距离是无穷大就说明不可达，直接返回 -1，如果不存在就直接返回数组的最大值即可

代码

注意建立图关系的时候，是有向图，单方向

class Solution {
    private static final int INF = Integer.MAX_VALUE / 2;
    public int networkDelayTime(int[][] times, int n, int k) {
        // 保存这个节点的可达性，建立图
        List<int[]>[] graph = new ArrayList[n];
        Arrays.setAll(graph, e -> new ArrayList<int[]>());
        for(int[] edge : times){
            int u = edge[0]-1,v = edge[1]-1,cnt = edge[2];
            // 建立图，节点和连接节点关系，思想ok，建立图的时候需要注意是有向图只需要单向即可
            graph[u].add(new int[]{v,cnt});
        }
        int[] dist = dijkstra(graph,k-1);
        for(int x : dist){
            if(x == INF){
                return -1;
            }
        }
        return Arrays.stream(dist).max().getAsInt();
    }


	public int[] dijkstra(List<int[]>[] graph,int start){
        // 初始化距离数组全部为最大值，到大本身的距离是0
        int[] dist = new int[graph.length];
        Arrays.fill(dist,INF);
        dist[start] = 0;
        // 小顶堆存储到达每一个节点的最短距离
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->o1[1]-o2[1]);
        pq.offer(new int[]{start,0});
        while(!pq.isEmpty()){
            // 堆顶的元素和最短距离
            int[] curNode = pq.poll();
            int x = curNode[0],d = curNode[1];
            if(d > dist[x]) continue;
            // 遍历节点元素的可达路径，更新最短距离,无向图
            for(int[] e : graph[x]){
                int y = e[0];
                int curDist = d + e[1];
                if(curDist < dist[y]){
                    dist[y] = curDist;
                    pq.offer(new int[]{y,curDist});
                }
            }
        }
        return dist;
    }
}
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

第二种思路就是AOV网络，从k节点开始，创建一个访问标记数组用于记录每个节点是否被访问过，将距离k节点最近的节点加入，就是在未访问的节点中查找最短路径长度，更新抵达节点的距离数组，将INF初始化为Integer.MAX_VALUE的一半是因为要进行距离的相加求取最短距离，防止溢出，不够存储

    public int networkDelayTime(int[][] times, int n, int k) {
        // AOV
        int[][] graph = new int[n][n];
        for(int i = 0; i < n; i++){
            Arrays.fill(graph[i],Integer.MAX_VALUE/2);
        }
        // 节点编号 - 1,存储为graph中
        for(int[] t : times){
            int i = t[0] - 1,j = t[1] - 1;
            graph[i][j] = t[2];
        }

        int[] dist = new int[n];
        Arrays.fill(dist,Integer.MAX_VALUE/2);
        // k -> k = 0
        dist[k-1] = 0;
        boolean[] used = new boolean[n];
        for(int i = 0; i < n; i++){
            // x保存未被访问的最短路径的节点
            int x = -1;
            for(int j = 0; j < n; j++){
                if(!used[j] && (x == -1 || dist[x] > dist[j])){
                    x = j;
                }
            }
            used[x] = true;
            for (int y = 0; y < n; ++y) {
                // 预防越界
                dist[y] = Math.min(dist[y], dist[x] + graph[x][y]);
            }
        }
        int ans = Arrays.stream(dist).max().getAsInt();
        return ans == Integer.MAX_VALUE/2 ? -1 : ans;
    }
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

813. 最大平均值和的分组

题目描述

给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成 最多 k 个相邻的非空子数组 。 分数 由每个子数组内的平均值的总和构成。
注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。
返回我们所能得到的最大 分数 是多少。答案误差在 10^6 内被视为是正确的。

813. 最大平均值和的分组

解题分析

将数组划分为k段，求解每一段的平均值，返回最大的平均值求和

定义前缀和数组，类型注意是double类型的否则会出现精度的丢失

采用动态规划，dp[i][j]代表的是前 i 个元素划分为j的最大平均值和

代码

class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        int n = nums.length;
        double[] sum = new double[n+1];
        // 前缀和使用double类型的，否则会出现精度的丢失
        for(int i = 1; i <= n; i++){
            sum[i] = sum[i-1] + nums[i-1];
        }
        // dp[i][j]代表前i个元素划分为j段的最大平均值和
        double[][] dp = new double[n+1][k+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= Math.min(i,k); j++){
                if(j == 1){
                    dp[i][1] = sum[i] / i;
                }else{
                    for(int m = 2; m <= i; m++){
                        dp[i][j] = Math.max(dp[i][j],dp[m-1][j-1]+((sum[i]-sum[m-1])/(i-m+1)));
                    }
                }
            }
        }
        return dp[n][k];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1752. 检查数组是否经排序和轮转得到

题目描述

给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。
如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false 。
源数组中可能存在 重复项 。
注意：我们称数组 A 在轮转 x 个位置后得到长度相同的数组 B ，当它们满足 A[i] == B[(i+x) % A.length] ，其中 % 为取余运算。

1752. 检查数组是否经排序和轮转得到

题目分析

最开始的数组是一个非递减的数组，轮转之后能否得到题目给定的数组的顺序

给定的数组有序的话，反转0，给定的数组有且仅有2个数，即是1次递减，可以反转得到，并且给定数组的开头一定大于结尾，一旦递减的次数大于1，就不可能反转得到

代码

class Solution {
    public boolean check(int[] nums) {
        // 旋转之后非递减即可，sum 记录递减的元素对个数
        int sum = 0;
        for(int i = 1; i < nums.length; i++){
            // 一个非降序的数组旋转之后最多具有一组数对递减
            if(nums[i] < nums[i-1]){
                if(sum != 0){
                    return false;
                }
                sum++;
            }
        }
        return sum == 0 || nums[0] >= nums[nums.length - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16