LeetCode周记 EP6

前言

这周好像是划水了，只有一道题。

本周主题：暴力搜索（DFS）、Dijkstra算法

题目：

• 240702每日一题—Maximum Path Quality of a Graph

  暴力搜索（DFS）

  题目：Maximum Path Quality of a Graph

一个无向带权图，给定边和权，每个节点都有value。另给一参数maxTime，求valid path(VP)的最大value和。一个VP是一个0节点的环路，且路径时间消耗总和不超过maxTime，同时每个节点的value只计算一次。图中每个节点最多有$4$条边。

首先基于题目数据范围，可以采取暴力搜索的方式，一条VP的最大边数为$\frac{maxTime}{\min (time_j)}$，且图中每个节点最多有$4$条边，则可以得到搜索树的大小为$\frac{maxTime}{\min (time_j)}+1$层的$4$叉树。

在本题中，穷举的内容是一条环路，因此采用DFS暴力搜索：

class Solution {
    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        int n = values.length;
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            int t = e[2];
            g[x].add(new int[]{y, t});
            g[y].add(new int[]{x, t});
        }

        boolean[] vis = new boolean[n];
        vis[0] = true;
        return dfs(0, 0, values[0], vis, g, values, maxTime);
    }

    private int dfs(int x, int sumTime, int sumValue, boolean[] vis, List<int[]>[] g, int[] values, int maxTime) {
        int res = x == 0 ? sumValue : 0;
        for (int[] e : g[x]) {
            int y = e[0];
            int t = e[1];
            if (sumTime + t > maxTime) {
                continue; // 超时中断
            }
            if (vis[y]) {
                res = Math.max(res, dfs(y, sumTime + t, sumValue, vis, g, values, maxTime));
            } else {
                vis[y] = true;
                // 每个节点的价值至多算入价值总和中一次
                res = Math.max(res, dfs(y, sumTime + t, sumValue + values[y], vis, g, values, maxTime));
                vis[y] = false; // 恢复现场
            }
        }
        return res;
    }
}

递归实现的DFS，对于每个节点的所有邻接点逐线路进行访问，访问标记在递归过程中用于防止搜索已经过路径，在整条路径搜索结束后逐个恢复支持下一次搜索，当遇到已搜索过的节点时依然需要计算一次max值，因为我们要找的是0节点的环路，只有遇到0节点时才会贡献sumValue。

这个时间复杂度计算也可以学习一下，$O(n+m+4^k)$，主要是四叉树的复杂度。空间复杂度为$O(n+m+k)$，即一次只消耗一条路径的空间。

Dijkstra算法优化搜索

用 Dijkstra 算法预处理起点 0 到每个节点的最短路，这也是每个节点到 0 的最短路。本题是稀疏图，可以使用堆优化的 Dijkstra 算法。

在递归到下一个节点之前，判断下一个节点在走最短路的前提下，能否在 maxTime 时间内回到起点 0，若不能则不递归。

class Solution {
    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        int n = values.length;
        List<int[]>[] g = new ArrayList[n];
        Arrays.setAll(g, i -> new ArrayList<>());
        for (int[] e : edges) {
            int x = e[0];
            int y = e[1];
            int t = e[2];
            g[x].add(new int[]{y, t});
            g[y].add(new int[]{x, t});
        }

        // Dijkstra 算法
        int[] dis = new int[n];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.add(new int[]{0, 0});
        while (!pq.isEmpty()) {
            int[] p = pq.poll();
            int dx = p[0];
            int x = p[1];
            if (dx > dis[x]) { // x 之前出堆过
                continue;
            }
            for (int[] e : g[x]) {
                int y = e[0];
                int newDis = dx + e[1];
                if (newDis < dis[y]) {
                    dis[y] = newDis; // 更新 x 的邻居的最短路
                    pq.offer(new int[]{newDis, y});
                }
            }
        }

        boolean[] vis = new boolean[n];
        vis[0] = true;
        return dfs(0, 0, values[0], vis, g, values, maxTime, dis);
    }

    private int dfs(int x, int sumTime, int sumValue, boolean[] vis, List<int[]>[] g, int[] values, int maxTime, int[] dis) {
        int res = x == 0 ? sumValue : 0;
        for (int[] e : g[x]) {
            int y = e[0];
            int t = e[1];
            // 相比方法一，这里多了 dis[y]
            if (sumTime + t + dis[y] > maxTime) {
                continue;
            }
            if (vis[y]) {
                res = Math.max(res, dfs(y, sumTime + t, sumValue, vis, g, values, maxTime, dis));
            } else {
                vis[y] = true;
                // 每个节点的价值至多算入价值总和中一次
                res = Math.max(res, dfs(y, sumTime + t, sumValue + values[y], vis, g, values, maxTime, dis));
                vis[y] = false; // 恢复现场
            }
        }
        return res;
    }
}

参考文献

[1] https://leetcode.cn/problems/maximum-path-quality-of-a-graph/solutions/1088414/bao-sou-jian-zhi-by-endlesscheng-iv6z/

后记

首发于 silencezheng.top，转载请注明出处。

赏

谢谢打赏哟！

支付宝

微信