ChunNote
0%

leetCode-399:Evaluate Division

发表于 分类于

问题描述

给定一个列表和一个数组，列表中都是只包含两个元素的列表，表示两个元素相除的方程式，其结果是数组中对应的下标元素的值。再给出另一个列表用于查询方程式相除的结果，如果某个方程式没查询到结果，则返回 -1.0。题目链接：**点我**

样例输入输出

输入：equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0], queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]]

输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]

输入：equations = [[“a”,”b”],[“b”,”c”],[“bc”,”cd”]], values = [1.5,2.5,5.0], queries = [[“a”,”c”],[“c”,”b”],[“bc”,”cd”],[“cd”,”bc”]]

输出：[3.75000,0.40000,5.00000,0.20000]

问题解法

使用带权并查集进行求解，在每次查找根节点的过程中，进行路径压缩的同时更新边的权值（此处值两数相除的结果），在合并根节点的同时，也进行边权值的更新，此处的更新考虑 四边形 的情况，其更新表达式为 value[firstParent] = currentEdgeValue * value[second] / value[first]。代码如下

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
class Solution
{
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries)
    {
        Set<String> nodeSet = new HashSet<>();
        Map<String, String> parentMap = new HashMap<>();
        Map<String, Double> valueMap = new HashMap<>();
        build(nodeSet, parentMap, valueMap, equations, values);
        return query(nodeSet, parentMap, valueMap, queries);
    }

    private double[] query(Set<String> nodeSet, Map<String, String> parentMap, Map<String, Double> valueMap, List<List<String>> queries)
    {
        double[] result = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++)
        {
            String first = queries.get(i).get(0);
            String second = queries.get(i).get(1);
            if (!nodeSet.contains(first) || !nodeSet.contains(second))
            {
                result[i] = -1.0;
                continue;
            }

            String firstParent = getParent(first, parentMap, valueMap);
            String secondParent = getParent(second, parentMap, valueMap);
            if (!firstParent.equals(secondParent))
            {
                result[i] = -1.0;
            }
            else
            {
                result[i] = valueMap.get(first) / valueMap.get(second);
            }
        }

        return result;
    }

    private void build(Set<String> nodeSet, Map<String, String> parentMap, Map<String, Double> valueMap, List<List<String>> equations, double[] values)
    {
        for (int i = 0; i < equations.size(); i++)
        {
            List<String> equation = equations.get(i);
            String first = equation.get(0);
            String second = equation.get(1);
            nodeSet.add(first);
            nodeSet.add(second);
            String firstParent = getParent(first, parentMap, valueMap);
            String secondParent = getParent(second, parentMap, valueMap);
            if (!firstParent.equals(secondParent))
            {
                parentMap.put(firstParent, secondParent);
                valueMap.put(firstParent, values[i] * valueMap.get(second) / valueMap.get(first));
            }
        }
    }

    private String getParent(String str, Map<String, String> parentMap, Map<String, Double> valueMap)
    {
        if (parentMap.get(str) == null)
        {
            valueMap.put(str, 1.0);
            return str;
        }

        String root = getParent(parentMap.get(str), parentMap, valueMap);
        valueMap.put(str, valueMap.get(str) * valueMap.get(parentMap.get(str)));
        parentMap.put(str, root);

        return root;
    }
}