力扣399题：除法求值

力扣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 的情况，且不存在任何矛盾的结果。

输入输出样例

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

1
2
3
4
5
6
7

输入：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
3
4

提示：

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:

    //parent 存放父节点，weight 存放结点的值
    vector<int>parent;
    vector<double>weight;

public:

    //构造函数
    UnionFind(int n)
    {
        //限定容器的长度
        parent=vector<int>(n);
        weight=vector<double>(n);

//因为每一个根节点都指向其自己，所以父结点的权重为1.0
        for(int i=0;i<n;i++)
        {
            parent[i]=i;

            weight[i]=1.0;
        }
    }

//实现并查集的合并方法
    void myUnion(int x,int y,double value)
    {
        //首先查找两个结点对应根节点的id
        
        int rootX=find(x);
        int rootY=find(y);

        //如果二者根结点是一致的，那么就代表不用合并
        if(rootX==rootY)
        {
            return;
        }
        //否则将其中的根结节指向另一个根节点
        parent[rootX]=rootY;
        //利用两条路径上的有向边的权值的乘积相等的原则
        weight[rootX]=weight[y]*value/weight[x];
    }


//路径压缩
//实现并查集的find 方法，传入输入结点的id,返回根节点对应的id
    int find(int x)
    {
        //递归寻找到根节点，更新该点到根的权重为该点父节点到跟的权重

        if(x!=parent[x])
        {
            //保存上一个接待结点的权值
            int origin=parent[x];
            parent[x]=find(parent[x]);
            //更新到根节点的权值
            weight[x]*=weight[origin];
        }
        return parent[x];
    }

//实现除法结果。如果两个值不存在则返回-1
    double isConnected(int x,int y)
    {
        //判断二则的根节点是否相同，若有相同的根可执行除法操作，若无，则二者不在一个并查集，返回-1
        int rootX=find(x);
        int rootY=find(y);

        if(rootX==rootY)
        {
            return weight[x]/weight[y];
        }
        else{
            return -1.0000;
        }
    }

};






class Solution2 {
public:

//使用并查集
//构建有向图 b/c=3.0  parent[b]=c  weight[b]=3.0
//统一变量与路径压缩
//两条路径上的有向边的权值的乘积是一定相等的

    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int equationsSize=equations.size();
        
        //实例化并查集
        //2*equationSize 最极端的情况，都不相同
        UnionFind unionFind(2*equationsSize);
        unordered_map<string,int>maps(2*equationsSize);
        //使用id标记变量
        int id=0;

        for(int i=0;i<equationsSize;i++)
        {
            //将equations中的变量存储进来
            vector<string>equation=equations[i];
            string var1=equation[0];
            string var2=equation[1];

            //将变量放入hash表中
            if(!maps.count(var1))
            {
                maps[var1]=id;
                id++;
            }
            if(!maps.count(var2))
            {
                maps[var2]=id;
                id++;
            }

            //在并查集中执行一次合并的操作
            //将分子分母用有向边连接起来
            unionFind.myUnion(maps[var1],maps[var2],values[i]);
        }

                //进行查询操作票
        int queriesSize=queries.size();
        vector<double>res(queriesSize,-1.0000);
        for(int i=0;i<queriesSize;i++)
        {
            string var1=queries[i][0];
            string var2=queries[i][1];

            if(maps.count(var1)&&maps.count(var2))
            {
                int id1=maps[var1];
                int id2=maps[var2];
                res[i]=unionFind.isConnected(id1,id2);
            }
            else{
                res[i]=-1.0000;
            }
        }
        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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

解法二，使用广度优先搜索

//使用广度优先搜索
class Solution {
public:
//将整个问题建模成图，给定图中的一些点，以及某些边的权值（两个变量的比值）
//对任意两点（两个变量）求出其路径长（两个变量的壁纸）
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        //使用id标记结点
        int id=0;
        unordered_map<string,int>maps;

        int equationLength=equations.size();

        //将表达式添加到hash表中
        for(int i=0;i<equationLength;i++)
        {
            if(!maps.count(equations[i][0]))
            {
                maps[equations[i][0]]=id++;
            }

            if(!maps.count(equations[i][1]))
            {
                maps[equations[i][1]]=id++;
            }            
        }

        //边中存储每个点其直接连接的点和对应的权值
        vector<vector<pair<int,double>>>edges(id);

        for(int i=0;i<equationLength;i++)
        {
            int temp1=maps[equations[i][0]];
            int temp2=maps[equations[i][1]];

            edges[temp1].push_back({temp2,values[i]});
            edges[temp2].push_back({temp1,1.0/values[i]});
        }


        vector<double>res;
        for(const auto &q:queries)
        {
            double result=-1.0;

            //如果hash表中存在对应的结点
            if(maps.count(q[0])&&maps.count(q[1]))
            {
                int id1=maps[q[0]];
                int id2=maps[q[1]];

                //如果二者id相同，二者肯定相同
                if(id1==id2)
                {
                    result=1.0;
                }
                else
                {
                    //建立队列进行辅助
                    queue<int>points;

                    points.push(id1);

                    vector<double>ratios(id,-1.0);
                    ratios[id1]=1.0;

                    while(!points.empty()&&ratios[id2]<0)
                    {
                        int x=points.front();
                        points.pop();

                        for( auto [y,val]:edges[x])
                        {
                            if(ratios[y]<0)
                            {
                                ratios[y]=ratios[x]*val;
                                points.push(y);
                            }
                        }
                    }
                    result=ratios[id2];
                }
            }
            res.push_back(result);
        }
        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

解法三，使用Floyd算法

//使用Floyd算法
class Solution3 {
public:
//将整个问题建模成图，给定图中的一些点，以及某些边的权值（两个变量的比值）
//使用Floyd算法，预先计算出任意两点之间的距离
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        int id=0;
        unordered_map<string,int>maps;

        int equationLength=equations.size();
                //将表达式添加到hash表中
        for(int i=0;i<equationLength;i++)
        {
            if(!maps.count(equations[i][0]))
            {
                maps[equations[i][0]]=id++;
            }

            if(!maps.count(equations[i][1]))
            {
                maps[equations[i][1]]=id++;
            }            
        }

    //绘制图
        vector<vector<double>>graph(id,vector<double>(id,-1.0));
        for(int i=0;i<equationLength;i++)
        {
            int id1=maps[equations[i][0]];
            int id2=maps[equations[i][1]];
            graph[id1][id2]=values[i];
            graph[id2][id1]=1.0/values[i];
        }

    //对图进行预处理，将各个顶点连接在一块
        for(int k=0;k<id;k++)
        {
            for(int i=0;i<id;i++)
            {
                for(int j=0;j<id;j++)
                {
                    if(graph[i][k]>0&&graph[k][j]>0)
                    {
                        graph[i][j]=graph[i][k]*graph[k][j];
                    }
                }
            }
        }

        //计算结果
        vector<double>res;
        for(auto q:queries)
        {
            double result=-1.0;
            if(maps.count(q[0])&&maps.count(q[1]))
            {
                int id1=maps[q[0]];
                int id2=maps[q[1]];

                if(graph[id1][id2]>0)
                {
                    result=graph[id1][id2];
                }
            }
            res.push_back(result);
        }
        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