[LeetCode][399. Evaluate Division] 4 Approaches: BFS, DFS, Floyd, Union Find

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 4.6k 阅读时长 ≈ 4 分钟

By Long Luo

This article is the solution 4 Approaches: BFS, DFS, Floyd, Union Find of Problem 399. Evaluate Division.

Here shows 4 Approaches to slove this problem: BFS, DFS, Floyd, Union Find.

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// DFS time: O(n^2 * m) space: O(n)
public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    Map<String, Map<String, Double>> graph = buildGraph(equations, values);

    int len = queries.size();
    double[] results = new double[len];

    for (int i = 0; i < len; i++) {
        String u = queries.get(i).get(0);
        String v = queries.get(i).get(1);

        if (!graph.containsKey(u) || !graph.containsKey(v)) {
            results[i] = -1.0;
            continue;
        }

        if (u.equals(v)) {
            results[i] = 1.0;
            continue;
        }

        results[i] = bfs(graph, u, v);
    }

    return results;
}


private static double bfs(Map<String, Map<String, Double>> graph, String u, String v) {
    if (graph.get(u).containsKey(v)) {
        return graph.get(u).get(v);
    }

    Set<String> visited = new HashSet<>();

    Queue<String[]> queue = new LinkedList<>();
    queue.offer(new String[]{u, String.valueOf(1.0)});

    visited.add(u);

    while (!queue.isEmpty()) {
        String[] cur = queue.poll();

        String curKey = cur[0];
        double curRatio = Double.parseDouble(cur[1]);

        if (curKey.equals(v)) {
            return curRatio;
        }

        Map<String, Double> curMap = graph.get(curKey);

        for (Map.Entry<String, Double> entry : curMap.entrySet()) {
            String nextKey = entry.getKey();
            double nextRatio = entry.getValue();

            if (visited.contains(nextKey)) {
                continue;
            }

            if (!graph.containsKey(nextKey)) {
                continue;
            }

            double product = curRatio * nextRatio;

            if (!graph.get(curKey).containsKey(nextKey)) {
                graph.get(curKey).put(nextKey, product);
            }

            visited.add(nextKey);
            queue.offer(new String[]{nextKey, String.valueOf(product)});
        }
    }

    return -1.0;
}

private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
    Map<String, Map<String, Double>> graph = new HashMap<>();

    int len = equations.size();

    for (int i = 0; i < len; i++) {
        String u = equations.get(i).get(0);
        String v = equations.get(i).get(1);

        double w = values[i];

        graph.putIfAbsent(u, new HashMap<>());
        graph.get(u).put(v, w);

        graph.putIfAbsent(v, new HashMap<>());
        graph.get(v).put(u, 1.0 / w);
    }

    return graph;
}

Analysis

  • Time Complexity: \(O(n^2logn)\)
  • Space Complexity: \(O(n^2)\)

DFS

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// DFS time: O(n^2 * m) space: O(n)
public static double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
    Map<String, Map<String, Double>> graph = buildGraph(equations, values);

    int len = queries.size();
    double[] results = new double[len];

    for (int i = 0; i < len; i++) {
        String u = queries.get(i).get(0);
        String v = queries.get(i).get(1);

        if (!graph.containsKey(u) || !graph.containsKey(v)) {
            results[i] = -1.0;
            continue;
        }

        if (u.equals(v)) {
            results[i] = 1.0;
            continue;
        }

        results[i] = dfs(graph, new HashSet<>(), u, v);
    }

    return results;
}


private double dfs(Map<String, Map<String, Double>> graph, Set<String> visited, String u, String v) {
    if (graph.get(u).containsKey(v)) {
        return graph.get(u).get(v);
    }

    visited.add(u);

    Map<String, Double> map = graph.get(u);

    for (Map.Entry<String, Double> entry : map.entrySet()) {
        String nextKey = entry.getKey();
        double nextRatio = entry.getValue();

        if (visited.contains(nextKey)) {
            continue;
        }

        double result = dfs(graph, visited, nextKey, v);
        if (result != -1.0) {
            return result * nextRatio;
        }
    }

    return -1.0;
}

private Map<String, Map<String, Double>> buildGraph(List<List<String>> equations, double[] values) {
    Map<String, Map<String, Double>> graph = new HashMap<>();

    int len = equations.size();

    for (int i = 0; i < len; i++) {
        String u = equations.get(i).get(0);
        String v = equations.get(i).get(1);

        double w = values[i];

        graph.putIfAbsent(u, new HashMap<>());
        graph.get(u).put(v, w);

        graph.putIfAbsent(v, new HashMap<>());
        graph.get(v).put(u, 1.0 / w);
    }

    return graph;
}

Analysis

  • Time Complexity: \(O(k \log n)\)
  • Space Complexity: \(O(n)\)

Floyd

1

Analysis

  • Time Complexity: \(O(n \log (r-l)\)
  • Space Complexity: \(O(1)\)

Union Find

1
2


Analysis

  • Time Complexity: \(O(n \log (r-l))\)
  • Space Complexity: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗