除法求值

发表于
本文字数： 2.4k 阅读时长 ≈ 2 分钟

LeetCode每日一题，399. Evaluate Division

先看题目描述

sEniCt.png

大意就是首先给定一个 equations 和一个 value，其中 equations[i] = [a，b] 和 values[i] 共同表示等式 a / b = values[i]，再给定一个问题数组 queries，queries[j] = [c，d] 表示第 j 个问题，让我们根据已知条件求出 c / d 的值，让我们将所有问题的答案返回，求不出答案的问题就在结果的相应位置填上 -1

算法和思路

这题看了好久不会做，就去看题解了，看了题解才知道这是道图论的题，自己还没怎么接触过图论的题

Floyd算法

我们可以将整个问题建模成一张图：给定图中的一些点（变量），以及某些边的权值（两个变量的比值），试对任意两点（两个变量）求出其路径长（两个变量的比值）

因此，我们首先需要遍历 equations 数组，找出其中所有不同的字符串，并通过哈希表将每个不同的字符串映射成整数

在构建完图之后，我们就可以使用 Floyd 算法，预先计算出任意两点之间的距离，最后根据 queries 去查找距离，返回结果即可

算法源码

Floyd算法

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
class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Integer> nodes = new HashMap<>();
        int n = 0;
        int len = values.length;
        for (List<String> equation : equations) {
            if (!nodes.containsKey(equation.get(0))) {
                nodes.put(equation.get(0), n++);
            }
            if (!nodes.containsKey(equation.get(1))) {
                nodes.put(equation.get(1), n++);
            }
        }
        double[][] graph = new double[n][n];
        for (double[] g : graph) {
            Arrays.fill(g, -1.0);
        }
        for (int i = 0; i < n; i++) {
            graph[i][i] = 1.0;
        }
        for (int i = 0; i < len; i++) {
            int ia = nodes.get(equations.get(i).get(0));
            int ib = nodes.get(equations.get(i).get(1));
            graph[ia][ib] = values[i];
            graph[ib][ia] = 1.0 / values[i];
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (graph[i][j] > 0 && graph[k][i] > 0) {
                        graph[k][j] = graph[k][i] * graph[i][j];
                    }
                }
            }
        }
        int cnt = queries.size();
        double[] res = new double[cnt];
        for (int i = 0; i < cnt; i++) {
            double ret = -1.0;
            if (nodes.containsKey(queries.get(i).get(0)) && nodes.containsKey(queries.get(i).get(1))) {
                ret = graph[nodes.get(queries.get(i).get(0))][nodes.get(queries.get(i).get(1))];
            }
            res[i] = ret;
        }
        return res;
    }
}