力扣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 ]
输入：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]
输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
输出：[0.50000,2.00000,-1.00000,-1.00000]
提示：
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;
}
};
解法二，使用广度优先搜索
//使用广度优先搜索
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;
}
};
解法三，使用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;
}
};