LeetCode-图的建立和迪杰斯特拉算法

• 882. 细分图中的可到达节点
• • 题目描述
  • 解题分析
  • 代码
  • dijkstra
• 743. 网络延迟时间
• • 题目描述
  • 解题分析
  • 代码
• 813. 最大平均值和的分组
• • 题目描述
  • 解题分析
  • 代码
• 1752. 检查数组是否经排序和轮转得到
• • 题目描述
  • 题目分析
  • 代码

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

题目描述

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

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

解题分析

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

代码

public int reachableNodes(int[][] edges, int maxMoves, int n) {// 保存这个节点的可达性，建立图List[] graph = new ArrayList[n];Arrays.setAll(graph, e -> new ArrayList());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;}

dijkstra

    // dijkstra 求取 start 到各个节点的最短路径public int[] dijkstra(List[] graph,int start){// 初始化距离数组全部为最大值，到大本身的距离是0int[] dist = new int[graph.length];Arrays.fill(dist,Integer.MAX_VALUE);dist[start] = 0;// 小顶堆存储到达每一个节点的最短距离PriorityQueue 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;}

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[] graph = new ArrayList[n];Arrays.setAll(graph, e -> new ArrayList());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[] graph,int start){// 初始化距离数组全部为最大值，到大本身的距离是0int[] dist = new int[graph.length];Arrays.fill(dist,INF);dist[start] = 0;// 小顶堆存储到达每一个节点的最短距离PriorityQueue 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;}
}

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

    public int networkDelayTime(int[][] times, int n, int k) {// AOVint[][] 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 = 0dist[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;}

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

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