Evaluate Division
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 ].
The values are positive. This represents the equations..
According to the example above:
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.
Tips:
- 解法1：
最直白的解法。先过滤掉没有见过的字符，形成字典，然后开始算结果。如果发现问题中设计的两个字串有一个没有出现在字典里，就返回-1，其他情况则进入DFS。
DFS中建立一个新的stack，针对每个queary依次搜索每个equation，如果equation中有queary种两个字串的任意一个，就接着往下搜，temp = helper * value 或 helper / value直到搜出结果。
值得注意的是，这里有 if(temp > 0) return; else stack pop()的语句，是因为题中表示所有等式的值都是positive的，所以如果出现负数，则一定是在这次DFS中直到叶子都没找到结果，返回了-1。所以此时要pop之后接着搜答案。
- 解法2：
先把所有equation都存进map里，这样在queary大的时候比解法一快。
- 解法3：并查集
应该就是在找老大哥合并的过程，只是在compress find的时候和union的时候带着value呗~
Code:
解法1：
public class Solution {
public double[] calcEquation(String[][] equations, double[] values, String[][] query) {
double[] result = new double[query.length];
// filter unexpected words
// 过滤掉没有遇见过的字符
Set<String> words = new HashSet<>();
for (String[] strs : equations) {
words.add(strs[0]);
words.add(strs[1]);
}
for (int i = 0; i < query.length; ++i) {
String[] keys = query[i];
if (!words.contains(keys[0]) || !words.contains(keys[1])) result[i] = -1.0d;
else {
Stack<Integer> stack = new Stack<>();
result[i] = helper(equations, values, keys, stack);
}
}
return result;
}
public double helper(String[][] equations, double[] values, String[] keys, Stack<Integer> stack) {
// 直接查找，key的顺序有正反
// look up equations directly
for (int i = 0; i < equations.length; ++i) {
if (equations[i][0].equals(keys[0]) && equations[i][1].equals(keys[1])) return values[i];
if (equations[i][0].equals(keys[1]) && equations[i][1].equals(keys[0])) return 1 / values[i];
}
// lookup equations by other equations
// 间接查找，key的顺序也有正反
for (int i = 0; i < equations.length; ++i) {
if (!stack.contains(i) && keys[0].equals(equations[i][0])) {
stack.push(i);
double temp = values[i] * helper(equations, values, new String[]{equations[i][1], keys[1]}, stack);
if (temp > 0) return temp;
else stack.pop();
}
if (!stack.contains(i) && keys[0].equals(equations[i][1])) {
stack.push(i);
double temp = helper(equations, values, new String[]{equations[i][0], keys[1]}, stack) / values[i];
if (temp > 0) return temp;
else stack.pop();
}
}
// 查不到，返回-1
return -1.0d;
}
}
解法2：
public double[] calcEquation(String[][] equations, double[] values, String[][] query) {
// use table save string to integer
Map<String, Integer> table = new HashMap<>();
int len = 0;
for (String[] strings : equations)
for (String string : strings)
if (!table.containsKey(string)) table.put(string, len++);
// init map by direct equation
double[][] map = new double[len][len];
for (int i = 0; i < len; ++i)
for (int j = 0; j < len; ++j)
map[i][j] = (i == j ? 1.0d : -1.0d);
for (int i = 0; i < equations.length; ++i) {
String[] keys = equations[i];
int row = table.get(keys[0]);
int col = table.get(keys[1]);
map[row][col] = values[i];
map[col][row] = 1 / values[i];
}
// floyd-warshall like algorithm
for (int i = 0; i < len; ++i) {
for (int j = 0; j < len; ++j) {
for (int k = 0; k < len; ++k) {
if (map[j][i] >= 0d && map[i][k] >= 0d) {
map[j][k] = map[j][i] * map[i][k];
}
}
}
}
// query now
double[] result = new double[query.length];
for (int i = 0; i < query.length; ++i) {
String[] keys = query[i];
Integer row = table.get(keys[0]);
Integer col = table.get(keys[1]);
if (row == null || col == null) result[i] = -1.0d;
else result[i] = map[row][col];
}
return result;
}
解法3：
public double[] calcEquation(String[][] equations, double[] values, String[][] query) {
// map string to integer
Map<String, Integer> mIdTable = new HashMap<>();
int len = 0;
for (String[] words : equations)
for (String word : words)
if (!mIdTable.containsKey(word)) mIdTable.put(word, len++);
// init parent index and value
Node[] nodes = new Node[len];
for (int i = 0; i < len; ++i) nodes[i] = new Node(i);
// union, you can take an example as follows
// (a/b=3)->(c/d=6)->(b/d=12)
for (int i = 0; i < equations.length; ++i) {
String[] keys = equations[i];
int k1 = mIdTable.get(keys[0]);
int k2 = mIdTable.get(keys[1]);
int groupHead1 = find(nodes, k1);
int groupHead2 = find(nodes, k2);
nodes[groupHead2].parent = groupHead1;
nodes[groupHead2].value = nodes[k1].value * values[i] / nodes[k2].value;
}
// query now
double[] result = new double[query.length];
for (int i = 0; i < query.length; ++i) {
Integer k1 = mIdTable.get(query[i][0]);
Integer k2 = mIdTable.get(query[i][1]);
if (k1 == null || k2 == null) result[i] = -1d;
else {
int groupHead1 = find(nodes, k1);
int groupHead2 = find(nodes, k2);
if (groupHead1 != groupHead2) result[i] = -1d;
else result[i] = nodes[k2].value / nodes[k1].value;
}
}
return result;
}
public int find(Node[] nodes, int k) {
int p = k;
while (nodes[p].parent != p) {
p = nodes[p].parent;
// compress
nodes[k].value *= nodes[p].value;
}
// compress
nodes[k].parent = p;
return p;
}
private static class Node {
int parent;
double value;
public Node(int index) {
this.parent = index;
this.value = 1d;
}
}