细分图中的可到达节点(Leetcode 882)

发表于 | 分类于 ， ， | | 本文总阅读数 次
| 字数统计: 1.7k | 阅读时长 ≈ 8
Leetcode 882

1

题目分析

   本题难度适中，有两种思路，思路一：想法不是很难，但是实现比较困难。思路二：想法比较困难，但是实现相对简单。

BFS/DFS

BFS和DFS是本题的思路一，比较容易想到。从起点0开始，搜索每一条路径。

本题不推荐使用本算法，因为不像其他题目，每个点访问过就可以使用visited数组标记，因为通过其他路径访问到K点时，移动步数可能变少，所以后访问的可能走得更远。

这个解法的两个关键点是：

  1. visited数组记录某个节点是否被访问过，mem数组记录某个节点被访问时的剩余步数
  2. used[i][j]数组表示从i到j节点方向，可以走过多少个子节点，used[j][i]表示从j到i节点方向，可以走过多少个子节点。

因此算法的时间复杂度为O(2^n)，空间复杂度为O(2^n)。因为可以剪枝，所以可以勉强通过本题，如果设计一些很巧妙的数字，则无法通过。

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
class Solution {
    public int reachableNodes(int[][] edges, int maxMoves, int n) {
        HashMap<Integer, Integer>[] g = new HashMap[n];
        for (int i = 0; i < n; i++) {
            g[i] = new HashMap<>();
        }
        for (int[] edge : edges) {
            g[edge[0]].put(edge[1], edge[2]);
            g[edge[1]].put(edge[0], edge[2]);
        }
        Queue<Info> queue = new LinkedList<>();
        queue.add(new Info(maxMoves, 0));
        int[] mem = new int[n];
        int[][] used = new int[n][n];
        mem[0] = maxMoves;
        boolean[] isVisited = new boolean[n];
        isVisited[0] = true;
        int res = 1;
        while (!queue.isEmpty()) {
            Info cur = queue.poll();
            int curRemain = cur.remain;
            int curNode = cur.node;
            if (curRemain == 0) {
                continue;
            }
            for (var next : g[curNode].entrySet()) {
                int nextNode = next.getKey();
                int nextCost = next.getValue();
                if (curRemain - nextCost > mem[nextNode]) {
                    if (!isVisited[nextNode]) {
                        res++;
                        isVisited[nextNode] = true;
                    }
                    int nextRemain =  curRemain - nextCost - 1;
                    mem[nextNode] = nextRemain;
                    queue.add(new Info(nextRemain, nextNode));
                }
                used[curNode][nextNode] = Math.max(used[curNode][nextNode], curRemain);
            }
        }
        for (int[] edge : edges) {
            res += Math.min(used[edge[0]][edge[1]] + used[edge[1]][edge[0]], edge[2]);
        }
        return res;
    }

    static class Info {
        private int remain;

        private int node;

        Info(int remain, int node) {
            this.remain = remain;
            this.node = node;
        }
    }
}

贪心

本题说是贪心算法，不如说是dijkstra算法，第一种方法的本质就是先找到哪些点可以被访问，然后找到达该点的剩余步数。

那么最短路径算法，不就是寻找从某一点开始，到达其他点所花费的最短路径吗？

因此直接使用dijkstra即可，既然使用到了最短路，那么给小伙伴们介绍两种最短路的写法

先介绍最朴素的，基于节点的最短路算法。

步骤如下：

  1. 找到起始点s，和其余未被访问的点，记为unVisited。并设置unVisted的点到已访问点visited的距离数组dist，除和s直接相邻的点外，初始都赋值为无穷大。
  2. 寻找unVisted中，到达已访问点距离最小的点next，表示可以从该点扩展，并更新unVisted可以通过next间接访问visited点的距离。
  3. 将next标记为visited，直到unVisited为空(每个点都访问结束)或者无法找到距离最小的点next(该点无法到达)。

算法中访问需要访问所有点，扩展每个点需要找到dist数组中的最小距离，因此算法的时间复杂度为O(n^2)，空间复杂度为O(n)。

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
class Solution {
    public int reachableNodes(int[][] edges, int maxMoves, int n) {
        ArrayList<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, o -> new ArrayList<>());
        for (int[] edge : edges) {
            g[edge[0]].add(new int[]{edge[1], edge[2] + 1});
            g[edge[1]].add(new int[]{edge[0], edge[2] + 1});
        }
        int[] dist = getDistByNode(0, n, g);
        int res = 0;
        for (int x : dist) {
            if (x <= maxMoves) {
                res++;
            }
        }
        for (int[] edge : edges) {
            int over0 = Math.max(maxMoves - dist[edge[0]], 0);
            int over1 = Math.max(maxMoves - dist[edge[1]], 0);
            res += Math.min(over0 + over1, edge[2]);
        }
        return res;
    }

    private int[] getDistByNode(int start, int n, ArrayList<int[]>[] g) {
        int[] dist = new int[n];
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[start] = 0;
        HashSet<Integer> unVisited = new HashSet<>();
        for (int i = 0; i < n; i++) {
            unVisited.add(i);
        }
        unVisited.remove(start);
        for (int[] neigh : g[start]) {
            dist[neigh[0]] = neigh[1];
        }
        while (!unVisited.isEmpty()) {
            int mini = 0x3f3f3f3f;
            int miniIdx = -1;
            for (int node : unVisited) {
                if (dist[node] < mini) {
                    mini = dist[node];
                    miniIdx = node;
                }
            }
            if (miniIdx == -1) {
                return dist;
            }
            for (int[] neigh : g[miniIdx]) {
                int nextNode = neigh[0];
                int nextCost = neigh[1];
                dist[nextNode] = Math.min(dist[nextNode], dist[miniIdx] + nextCost);
            }
            unVisited.remove(miniIdx);
        }
        return dist;
    }
}

下面介绍基于边的最短路算法

步骤如下：

  1. 找到起始点s，创建一个小顶堆，小顶堆中存放一个长度为2的数组，表示下一个节点和到达该节点的花费。将s和花费0放入小顶堆，初始化距离数组dist为无穷大。
  2. 从小顶堆中寻找一条最短的花费进行扩展，找到最近的节点next，更新dist数组，并将与next相邻的边放入小顶堆中。
  3. 当小顶堆为空，表示所有可扩展的点都访问完毕。

算法的时间复杂度为O(mlog(m))，空间复杂度为O(m)。其中n是边的数量。

有的小伙伴会问，m个边，每次取出元素是log(m)，且还要更新n个临边，为什么不是$O(mn log(m))$，因为每次取到达某个节点最短的路径，所以每个点只会被访问一次，每个边只会添加一次，所以是$O(mlog(m) + m)$

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
class Solution {
    public int reachableNodes(int[][] edges, int maxMoves, int n) {
        ArrayList<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] edge : edges) {
            g[edge[0]].add(new int[]{edge[1], edge[2] + 1});
            g[edge[1]].add(new int[]{edge[0], edge[2] + 1});
        }
        int[] dist = getDistByEdge(0, n, g);
        int res = 0;
        for (int cost : dist) {
            if (maxMoves >= cost) {
                res++;
            }
        }
        for (int[] edge : edges) {
            int remain1 = Math.max(maxMoves - dist[edge[0]], 0);
            int remain2 = Math.max(maxMoves - dist[edge[1]], 0);
            res += Math.min(remain1 + remain2, edge[2]);
        }
        return res;
    }

    private int[] getDistByEdge(int start, int n, ArrayList<int[]>[] g) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        pq.add(new int[]{start, 0});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int node = cur[0];
            int cost = cur[1];
            if (cost > dist[node]) {
                continue;
            }
            for (int[] next : g[node]) {
                int nextNode = next[0];
                int nextCost = next[1];
                int newCost = cost + nextCost;
                if (newCost < dist[nextNode]) {
                    dist[nextNode] = newCost;
                    pq.add(new int[]{nextNode, newCost});
                }
            }
        }
        return dist;
    }
}

基于节点的最短路适合于密集场景，基于边的最短路径适合于稀疏场景。因为密集情况下m ≈ n x n，所以基于节点的算法是$O(n^2)$，基于边的算法是$O(n^2log(n))$，当稀疏情况下，m ≈ n，所以基于边的算法是$O(nlog(n))$。

刷题总结

  最短路径是非常经典的算法之一，大家一定要掌握两种写法。并且知道在稀疏和密集场景分别使用哪一种。

-------------本文结束感谢您的阅读-------------
0%