- 每日一题：LeetCode：2045.到达目的地的第二短时间
- 时间：2022-01-24
- 力扣难度：Hard
- 个人难度：Hard
- 数据结构：图
- 是否：BFS、最短路径、Dijkstra
2022-01-23：LeetCode：2045.到达目的地的第二短时间
1. 题目描述
题目：原题链接
- 城市用一个双向连通图表示，图中有 n 个节点，从 1 到 n 编号（包含 1 和 n）。
- 图中的边用一个二维整数数组 edges 表示，其中每个 edges[i] = [ui, vi] 表示一条节点 ui 和节点 vi 之间的双向连通边。
- 每组节点对由最多一条边连通，顶点不存在连接到自身的边。穿过任意一条边的时间是 time 分钟。
- 每个节点都有一个交通信号灯，每 change 分钟改变一次，从绿色变成红色，再由红色变成绿色，循环往复。
- 所有信号灯都同时改变。你可以在任何时候进入某个节点，但是只能在节点信号灯是绿色时才能离开。
- 如果信号灯是绿色 ，你不能在节点等待，必须离开。
- 第二小的值 是 严格大于 最小值的所有值中最小的值。例如，[2, 3, 4] 中第二小的值是 3 ，而 [2, 2, 4] 中第二小的值是 4 。
- 给你 n、edges、time 和 change ，返回从节点 1 到节点 n 需要的 第二短时间 。
- 你可以任意次穿过任意顶点，包括 1 和 n 。
- 你可以假设在启程时 ，所有信号灯刚刚变成绿色。
2 <= n <= 10^4n - 1 <= edges.length <= min(2 * 10^4, n * (n - 1) / 2)edges[i].length == 21 <= ui, vi <= n，ui != vi- 不含重复边，每个节点都可以从其他节点直接或者间接到达
1 <= time, change <= 10^3
输入输出规范
- 输入：节点个数、边的连通情况、边的权值时间、红绿灯的周期
- 输出：到达目的地的第二短的时间
输入输出示例
输入：n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
输出：13
解释
- 右图中的蓝色路径是最短时间路径，花费的时间是：
- 从节点 1 开始，总花费时间=0
- 1 -> 4：3 分钟，总花费时间=3
- 4 -> 5：3 分钟，总花费时间=6
- 右图中的红色路径是第二短时间路径，花费的时间是：
- 从节点 1 开始，总花费时间=0
- 1 -> 3：3 分钟，总花费时间=3
- 3 -> 4：3 分钟，总花费时间=6
- 在节点 4 等待 4 分钟，总花费时间=10
- 4 -> 5：3 分钟，总花费时间=13
- 右图中的蓝色路径是最短时间路径，花费的时间是：
2. 方法一：BFS
思路
- 根据题意分析可知，本题是一个双向连通图，且边的权值相等，是一个等权图，或*无权图 *
- 本题要求的是到达目的地的最短路径(最小花费)，虽然除了路径上的权值花费，还有等待红绿灯的额外花费，但是明显可以发现，由于权值相等，路径长的情况下，等待红绿灯的花费也会更多
- 因此对于无权图的最短路径问题，可以通过BFS广度优先搜索的方式来进行搜索，当第一次搜索的目标节点(终点)时，得到的就是最短路径
- 本题要求的是第二短的时间花费，即次短路径，那么，只需要求出最短路径，然后下一次搜索到目标节点时就是次短路径了
解题步骤
- 首先，先要构造一个邻接表储存顶点和边的情况，可以使用Map或者二维数组等
- 其次，为了得到最短路径和次短路径。还需要维护两个集合或数组来存储数据，这里索引表示节点的ID，值表示到达该节点最短时间(也可以存步数，这里因为两者是线性关系都一样)
- 既可以存到达各个节点时的最短步数、最小花费
- 也可以存到达各个节点时的具体路径(存一个List)
- 然后，维护一个队列来实现BFS，队列中存储当前节点的ID和到达该节点的时间花费，从起点开始
- 在BFS的过程中，要根据邻接表找到其下一步可以走向的多个节点，并通过内层循环逐个判断到达这些节点的时间花费，根据花费的时间大小和维护的两个路径数组中的值比较，存储新的更小的值，完成更新
- 此外，本题还需要考虑等待红绿灯的额外花费，可以通过到达当前节点时的总的时间花费和红绿灯变化周期的余数的奇偶性来进行判断：
costTime / change- 余数为偶数：表示到达当前节点时为绿灯，无需等待
- 余数为奇数：表示到达当前节点时为红灯，需要等待
change - costTime % change - 注意：总的花费时间 costTime 是要包括已经等待了的时间
题解
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
44public int secondMinimum(int n, int[][] edges, int time, int change) {
Map<Integer, List<Integer>> graph = new HashMap<>(); // 邻接表
// 构建图：邻接表
for (int[] edge : edges) {
List<Integer> nodes = graph.getOrDefault(edge[0], new ArrayList<>());
List<Integer> nodes_ = graph.getOrDefault(edge[1], new ArrayList<>());
nodes.add(edge[1]);
graph.put(edge[0], nodes);
nodes_.add(edge[0]);
graph.put(edge[1], nodes_);
}
// 最短路与次短路
int[] first = new int[n + 1]; // 到节点i的最短路，步数or时间
int[] second = new int[n + 1]; // 到节点i的次短路，步数or时间
Arrays.fill(first, Integer.MAX_VALUE);
Arrays.fill(second, Integer.MAX_VALUE);
Deque<int[]> deque = new LinkedList<>(); // int[] {nodeId, costTime}
deque.add(new int[]{1, 0}); // 起点出发
while (!deque.isEmpty()) {
int[] cur = deque.poll();
int node = cur[0], costTime = cur[1];
int nextTime = costTime + time;
List<Integer> nextNodeList = graph.get(node);
for (int nextNode : nextNodeList) {
if (nextTime < first[nextNode]) {
first[nextNode] = nextTime;
deque.add(new int[]{nextNode, nextTime});
} else if (nextTime > first[nextNode] && nextTime < second[nextNode]) {
second[nextNode] = nextTime;
deque.add(new int[]{nextNode, nextTime});
}
}
}
// 红绿灯等待时间
int waitTime = 0;
for (int i = 1; i < second[n] / time; i++) {
if ((((waitTime + i * time) / change) & 1) == 1) { // 奇数，红灯
waitTime += change - (i * time + waitTime) % change;
}
}
// System.out.println(Arrays.toString(first));
// System.out.println(Arrays.toString(second));
return second[n] + waitTime;
}复杂度分析：n 是节点个数、m 是边的个数
- 时间复杂度：$O(n+m)$
- 空间复杂度：$O(n+m)$
3. 方法二：BFS & 剪枝
思路：剪枝优化
- 对于方法一的BFS，在搜索的过程中，是会遍历所有的节点和边，不断更新路径数组
- 外层循环用来遍历队列中的节点，且由于节点间是双向连通的，其中的节点可能会重复
- 而内层循环用来遍历当前节点可以连接的各个节点，进行更新操作
- 此时，可以通过两个方面来进行剪枝优化
- 第一：对于内层循环，中间可能会遍历到目标节点，第一次遍历到目标节点时是最短路径，第二次就是次短路径
- 此后的内层遍历，乃至外层队列的遍历都不需要继续进行了，因为后续的已经是第三短的路径以及其他路径了
- 因此可以通过设置标识变量来控制跳出循环，也可以通过判断路径数组的目标元素索引处的值是否被更新来实现
- 第二：另一方面，对于同一个节点，其被访问的次数最多是两次
- 因为对于最短路径，一定是不会走回头路访问已经访问过的元素的，即一个元素最多访问一次
- 同样的，对于次短路径，由于要保证比最短路径长，所以可能会重复访问同一个节点，但是也最多只访问两次
- 因此，通过对元素被访问的次数进行计数，从而减少循环次数
- 对于方法一的BFS，在搜索的过程中，是会遍历所有的节点和边，不断更新路径数组
题解
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
52public int secondMinimum(int n, int[][] edges, int time, int change) {
Map<Integer, List<Integer>> graph = new HashMap<>(); // 邻接表
// 构建图：邻接表
for (int[] edge : edges) {
List<Integer> nodes = graph.getOrDefault(edge[0], new ArrayList<>());
List<Integer> nodes_ = graph.getOrDefault(edge[1], new ArrayList<>());
nodes.add(edge[1]);
graph.put(edge[0], nodes);
nodes_.add(edge[0]);
graph.put(edge[1], nodes_);
}
// 最短路与次短路
int[] first = new int[n + 1]; // 到节点i的最短路，步数or时间
int[] second = new int[n + 1]; // 到节点i的次短路，步数or时间
Arrays.fill(first, Integer.MAX_VALUE);
Arrays.fill(second, Integer.MAX_VALUE);
int[] visited = new int[n + 1]; // 访问次数计数器
visited[1]++;
Deque<int[]> deque = new LinkedList<>(); // int[] {nodeId, costTime}
deque.add(new int[]{1, 0}); // 起点出发
while (!deque.isEmpty()) {
// 剪枝1
if(second[n] != Integer.MAX_VALUE) break;
int[] cur = deque.poll();
int node = cur[0], costTime = cur[1];
int nextTime = costTime + time;
List<Integer> nextNodeList = graph.get(node);
for (int nextNode : nextNodeList) {
// 剪枝2
if(visited[nextNode] >= 2) continue;
if (nextTime < first[nextNode]) {
visited[nextNode]++;
first[nextNode] = nextTime;
deque.add(new int[]{nextNode, nextTime});
} else if (nextTime > first[nextNode] && nextTime < second[nextNode]) {
visited[nextNode]++;
second[nextNode] = nextTime;
deque.add(new int[]{nextNode, nextTime});
}
}
}
// 红绿灯等待时间
int waitTime = 0;
for (int i = 1; i < second[n] / time; i++) {
if ((((waitTime + i * time) / change) & 1) == 1) { // 奇数，红灯
waitTime += change - (i * time + waitTime) % change;
}
}
// System.out.println(Arrays.toString(first));
// System.out.println(Arrays.toString(second));
return second[n] + waitTime;
}
4. 方法三：Dijkstra算法
- 参考
本文作者：
Chthollists
发布时间： 2022-01-23 17:45:24
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:2045.到达目的地的第二短时间
本文链接： https://chthollists.github.io/post/c217db6f.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
发布时间： 2022-01-23 17:45:24
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:2045.到达目的地的第二短时间
本文链接： https://chthollists.github.io/post/c217db6f.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
