package com.heu.wsq.leetcode.bingchaji;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* 399. 除法求值
* @author wsq
* @date 2021/1/6
* 给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件,其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。
* 另有一些以数组 queries 表示的问题,其中 queries[j] = [Cj, Dj] 表示第 j 个问题,请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。
* 返回 所有问题的答案 。如果存在某个无法确定的答案,则用 -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 ]
*
* 链接:https://leetcode-cn.com/problems/evaluate-division
*/
public class CalcEquation {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries){
int equationSize = equations.size();
UnionFind unionFind = new UnionFind(2 * equationSize);
// 第一步,预处理,将字母与id进行映射,使得底层能用数组实现
Map<String, Integer> hashMap = new HashMap<>(2 * equationSize);
int id = 0;
for (int i = 0; i < equationSize; i++){
List<String> equation = equations.get(i);
String var1 = equation.get(0);
String var2 = equation.get(1);
// 保存映射关系
if (!hashMap.containsKey(var1)){
hashMap.put(var1, id);
id++;
}
if (!hashMap.containsKey(var2)){
hashMap.put(var2, id);
id++;
}
unionFind.union(hashMap.get(var1), hashMap.get(var2), values[i]);
}
// 第二部,做查询
int queriesSize = queries.size();
double[] ans = new double[queriesSize];
for (int i = 0; i < queriesSize; i++){
List<String> query = queries.get(i);
String var1 = query.get(0);
String var2 = query.get(1);
// 获取对应的id
Integer id1 = hashMap.get(var1);
Integer id2 = hashMap.get(var2);
if (id1 == null || id2 == null){
ans[i] = -1.0d;
}else{
ans[i] = unionFind.isConnected(id1, id2);
}
}
return ans;
}
private class UnionFind{
/**
* 保存当前结点的父结点
*/
private int[] parent;
/**
* 指向父结点的权值
*/
private double[] weight;
public UnionFind(int n){
this.parent = new int[n];
this.weight = new double[n];
// 初始化数组状态
for (int i = 0; i < n; i++){
this.parent[i] = i;
this.weight[i] = 1.0d;
}
}
public void union(Integer x, Integer 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];
}
private int find(int x){
if (x != parent[x]){
int origin = parent[x];
parent[x] = find(origin);
weight[x] *= weight[origin];
}
return parent[x];
}
public double isConnected(Integer x, Integer y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY){
return weight[x] / weight[y];
}else{
return -1.0d;
}
}
}
}