399. Evaluate Division
by Botao Xiao
Question
Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
Example:
Given a / b = 2.0, b / c = 3.0.
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
return [6.0, 0.5, -1.0, 1.0, -1.0 ].
Thinking:
- Method:通过并查集，可以检查连通性，也可以计算rate。
class Solution {
public static class Node{
String cur;
String parent;
double r;
public Node(String cur, String par, double r){
this.cur = cur;
this.parent = par;
this.r = r;
}
}
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
int len = values.length;
Map<String, Node> map = new HashMap<>();
for(int i = 0; i < len; i++){
String par = equations[i][0];
String child = equations[i][1];
double r = values[i];
union(par, child, r, map);
}
double[] result = new double[queries.length];
int index = 0;
for(String[] pair : queries){
result[index++] = calculate(pair[0], pair[1], map);
}
return result;
}
private static double calculate(String par, String child, Map<String, Node> map){
if(!map.containsKey(par) || !map.containsKey(child)) return -1D;
double r1 = 1D;
Node parNode = map.get(par);
while(!parNode.parent.equals(parNode.cur)){
r1 *= parNode.r;
parNode = map.get(parNode.parent);
}
double r2 = 1D;
Node childNode = map.get(child);
while(!childNode.parent.equals(childNode.cur)){
r2 *= childNode.r;
childNode = map.get(childNode.parent);
}
if(!childNode.cur.equals(parNode.cur)) return -1D;
return r2 / r1;
}
private static void union(String par, String child, double r, Map<String, Node> map){
if(!map.containsKey(par)){
if(!map.containsKey(child)){
map.put(par, new Node(par, par, 1D));
map.put(child, new Node(child, par, r));
}else{
map.put(par, new Node(par, child, 1/r));
}
}else{
if(!map.containsKey(child)){
map.put(child, new Node(child, par, r));
}else{ // both exist
Node parNode = map.get(par);
double r1 = 1D;
while(!parNode.parent.equals(parNode.cur)){
r1 *= parNode.r;
parNode = map.get(parNode.parent);
}
double r2 = 1D;
Node childNode = map.get(child);
while(!childNode.parent.equals(childNode.cur)){
r2 *= childNode.r;
childNode = map.get(childNode.parent);
}
childNode.parent = parNode.cur;
childNode.r = r * r1 / r2;
}
}
}
}
Second Time
- Method 1: Union Find Set
class Solution { private static class Node{ // node = ratio * parent or node / parent = ratio String parent; double ratio; public Node(String parent, double ratio){ this.parent = parent; this.ratio = ratio; } } private static class UF{ Map<String, Node> uf = new HashMap<>(); public Node find(String s){ if(!uf.containsKey(s)) return null; Node n = uf.get(s); if(!n.parent.equals(s)){ Node p = find(n.parent); n.parent = p.parent; // b = 2 * a && c = 2 * b => c = 2 * 3 * a = 6 * a n.ratio *= p.ratio; } return n; } public void union(String i, String j, double ratio){ boolean hasI = uf.containsKey(i); boolean hasJ = uf.containsKey(j); // i / j = ratio => i = j * ratio if(!hasI && !hasJ){ uf.put(i, new Node(j, ratio)); uf.put(j, new Node(j, 1D)); }else if(!hasI){ uf.put(i, new Node(j, ratio)); }else if(!hasJ){ uf.put(j, new Node(i, 1 / ratio)); }else{ Node p = find(i); Node q = find(j); p.parent = q.parent; p.ratio = ratio * q.ratio / p.ratio; } } } public double[] calcEquation(String[][] equations, double[] values, String[][] queries) { UF uf = new UF(); for(int i = 0; i < equations.length; i++){ uf.union(equations[i][0], equations[i][1], values[i]); } double[] res = new double[queries.length]; for(int i = 0; i < res.length; i++){ String[] query = queries[i]; Node first = uf.find(query[0]); Node second = uf.find(query[1]); if(first == null || second == null || !first.parent.equals(second.parent)){ res[i] = -1D; continue; }else{ // we want a / b = first.ratio * r / second.ratio * r res[i] = first.ratio / second.ratio; } } return res; } }- Method 2: dfs: record all pairs and use dfs to get the result.
class Solution { Map<String, Map<String, Double>> graph; public double[] calcEquation(String[][] equations, double[] values, String[][] queries) { graph = new HashMap<>(); for(int i = 0; i < equations.length; i++){ // a / b = ratio => a = b * ratio String first = equations[i][0], second = equations[i][1]; Map<String, Double> temp = graph.containsKey(first) ? graph.get(first): new HashMap<>(); temp.put(second, values[i]); graph.put(first, temp); temp = graph.containsKey(second) ? graph.get(second): new HashMap<>(); temp.put(first, 1/ values[i]); graph.put(second, temp); } double[] res = new double[queries.length]; for(int i = 0; i < res.length; i++){ String first = queries[i][0]; String second = queries[i][1]; if(!graph.containsKey(first) || !graph.containsKey(second)){ res[i] = -1D; continue; }else{ res[i] = divide(first, second, new HashSet<>()); } } return res; } private double divide(String first, String second, Set<String> visited){ if(first.equals(second)) return 1D; else{ for(String next : graph.get(first).keySet()){ if(visited.contains(next)) continue; visited.add(next); double d = divide(next, second, visited); if(d > 0) return d * graph.get(first).get(next); } return -1D; } } }
- Method 2: dfs: record all pairs and use dfs to get the result.
Reference
Subscribe via RSS