399. 除法求值

题目描述

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

**注意：**输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

**注意：**未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。

示例 1：

输入：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]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]
注意：x 是未定义的 => -1.0
1
2
3
4
5
6
7

示例 2：

输入：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]
1
2

示例 3：

输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]
1
2

提示：

• 1 <= equations.length <= 20
• equations[i].length == 2
• 1 <= Ai.length, Bi.length <= 5
• values.length == equations.length
• 0.0 < values[i] <= 20.0
• 1 <= queries.length <= 20
• queries[i].length == 2
• 1 <= Cj.length, Dj.length <= 5
• Ai, Bi, Cj, Dj 由小写英文字母与数字组成

解答

class UnionFind{
private:
    vector<int> parent;  // 存父节点，值就是分母（parent[a] ，a的父母）
    vector<double> weight; // 指向根节点的权值
public:
    UnionFind(int n)
    {
        for(int i  = 0; i < n; ++i)
        {
            parent.push_back(i); 
            weight.push_back(1.0); 
        }
    }
    // 路径压缩，返回根节点id，变查边改,把间接连接改成直接连接： a->b, b->c 改变为 a->c并求权值
    int find(int x)
    {
        if(x != parent[x])
        {
            int orign = parent[x];
            parent[x] = find(parent[x]);
            weight[x] *= weight[orign];
        }
        return parent[x];
    }
    // 返回除法结果
    double isConnected(int x, int y)
    {
        int rootX = find(x);
        int rootY = find(y);
        // 若两个值有共同的根（分母）表示可化成相同字母计算；否则不在同一个并查集中-1
        if(rootX == rootY)
        {
            return weight[x] / weight[y];
        }
        else 
        {
            return -1.00000;
        }
    }
    // 构造并查集
    void myunion(int x, int y, double value)
    {
        int rootX = find(x);
        int rootY = find(y);
        // 若两个值有共同的根（分母），构造成功
        if(rootX == rootY)
        {
            return ;
        }
        parent[rootX] = rootY;
        weight[rootX] = weight[y] * value / weight[x]; // a/c = 2, b/c = 3 => a/b = 
    }
};
class Solution {
public:
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        // 只关心连通性，不关心距离，或者问题具有传递性，可以使用并查集
        // 并查集：用于判断一对元素是否相连，它们关系是动态添加的
        // 这一类问题叫做动态连通性问题
        // 主要支持合并 与 查询是否在同一个集合的操作
        // 底层结构为【数组】 或 【哈希表】，表示节点指向的父节点，初始化时指向自己
        // 合并：把一个集合的根节点指向另一个集合的根节点，只要根节点同，就表示在同一个集合中
        // 并查集优化：路径压缩（降低树高）与按秩合并（使得高度更低的树的根节点指向高度更高的根节点）
        // a->b(b为根) 表示 a/b
        
        // 将给出的equation的两个变量所在的集合合并
        // 同一个集合中的两个变量就可以通过某种方式计算出它们的比值
        // 关键就是把不同变量的比值转换成相同的变量的比值
        // 如 a/b = 2.0, 则 parent[a] = b, 则 ,同时weight[a] = 2.0
        int equationsSize = equations.size();
        UnionFind UnionFind(2 * equationsSize);

        // 1.预处理，将变量的值与id映射
        map<string, int> hashMap;
        int id = 0;
        for(int i = 0; i < equationsSize; ++i)
        {
            // 存分子、分母、值为id
            vector<string> equation = equations[i];
            string var1 = equation[0];
            string var2 = equation[1];
            if(!hashMap.count(var1))
            {
                hashMap[var1] = id;
                ++id;
            }
            if(!hashMap.count(var2))
            {
                hashMap[var2] = id;
                ++id;
            }
            // 把分子和分母用有向边相连
            UnionFind.myunion(hashMap[var1], hashMap[var2], values[i]);
        }

        // 2.查询
        int queriesSize = queries.size();
        vector<double> res(queriesSize, -1.00000);
        for(int i = 0; i < queriesSize; ++i)
        {
            string var1 = queries[i][0]; // 分子
            string var2 = queries[i][1]; // 分母
            int id1, id2;

            // 若至少有一个不在equations, 则为 -1， 否则为除法
            if(hashMap.count(var1) && hashMap.count(var2))
            {
                id1 = hashMap[var1];
                id2 = hashMap[var2];
                res[i] = UnionFind.isConnected(id1, id2);
            }
        }
        return res;
    }
};
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115