题目描述
给出方程式 A / B = k, 其中 A 和 B 均为用字符串表示的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。
示例 :
给定： 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 ]
输入为：vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)， 其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回vector类型。
基于上述例子，输入如下：
equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。
思路
- 首先，遍历equations，找到尚未出现过的新字母，然后将字母压入para这个vector中，这样通过para.size()就能够知道有多少个不同字母了。
- 然后，初始化一个长度为para.size()的并查集对象，这个并查集对象的容器pre，装有一对数据pair，分别表示父节点的index、与父节点之间的倍数关系(初始时，父节点为自己，倍数为1.0)。再次遍历equations，将每组数据的两个字母在para里面的索引找出来，同时对应有一个values的值作为倍数，这样就能使用并查集的join方法，将两个字母的倍数关系进行关联。
- 最后，完成了所有equations里面的字母间的关联，就可以遍历queries了，如果出现了para里面没有的字母，或者没有在同一个集合里面的两个字母，那么返回-1.0；如果出现了同一集合里面的两个字母，就可以查找到这两个字母的共同的根节点，以及他俩和这个根节点之间的倍数关系，然后就能算出这两个字母之间的倍数关系。
难点
- 和一般的并查集不同，这道题涉及到路径权重，即集合间的节点之间存在倍数关系，所以可以使用pair，来实现数值对的存放。
在将两个节点进行关联的时候，首先要分别找到他们各自的根节点，以及他们各自与根节点的倍数关系，然后在关联这两个节点的根节点得时侯，需要计算才能得到正确的倍数关系。
比如，下面这种情况时，我们关联C、F节点，已知C、F节点之间的倍数关系为m，那么就能够算出根节点A、E之间的倍数关系，然后将A、E进行关联。
代码
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
| class Union{
vector<pair<int, double>> pre;
public:
Union(int n){
pre.resize(n);
for(int i=0; i<n; i++)
pre[i] = make_pair(i, 1.0);
}
int search(int root){
int son, temp;
son = root;
while(root != pre[root].first)
root = pre[root].first;
return root;
}
void join(int x, int y, double multiple){
int root1 = search(x);
int root2 = search(y);
if(root1 != root2){
double f1 = 1.0, f2 = 1.0;
while(x != root1){
f1 *= pre[x].second;
x = pre[x].first;
}
while(y != root2){
f2 *= pre[y].second;
y = pre[y].first;
}
pre[root2].first = root1;
pre[root2].second = (f1 / f2)*multiple;
}
}
double multi(int x, int y){
if(x == -1 || y == -1)
return -1.0;
int root1 = search(x);
int root2 = search(y);
if(root1 == root2){
double f1 = 1.0, f2 = 1.0;
while(x != root1){
f1 *= pre[x].second;
x = pre[x].first;
}
while(y != root2){
f2 *= pre[y].second;
y = pre[y].first;
}
return f2/f1;
}else return -1.0;
}
};
class Solution {
int length;
vector<string> para;
vector<double> answer;
public:
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries){
answer.resize(queries.size());
if(equations.size() == 0){
for(int i=0; i<queries.size(); i++)
answer[i] = -1.0;
return answer;
}
for(int i=0; i<equations.size(); i++)
for(int j=0; j<2; j++)
if(find(para.begin(), para.end(), equations[i][j]) == para.end())
para.push_back(equations[i][j]);
length = para.size();
Union set = Union(length);
for(int i=0; i<equations.size(); i++)
set.join(index(equations[i][0]), index(equations[i][1]), values[i]);
for(int i=0; i<queries.size(); i++)
answer[i] = set.multi(index(queries[i][0]), index(queries[i][1]));
return answer;
}
int index(string c){
for(int i=0; i<para.size(); i++)
if(para[i] == c)
return i;
return -1;
}
};
|
