leetcode:399. Evaluate Division
7007 ワード
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 input is: vector
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 input is: vector
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class Solution {
static boolean[][] vis = null;
static double[][] graph;
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
double[] ans = new double[queries.length];
HashMap map = new HashMap();
int index = 0;
index = this.map(map, index, equations);
// index = this.map(map, index, queries);
graph = new double[index][index];
vis = new boolean[index][index];
for (int i = 0; i < graph.length; ++i) {
Arrays.fill(graph[i], -1);
}
index = 0;
for (String[] s : equations) {
int a = map.get(s[0]);
int b = map.get(s[1]);
graph[a][b] = values[index];
graph[b][a] = 1.0 / values[index];
++index;
}
for(int i = 0; i < graph.length; ++i){
graph[i][i] = 1.0;
vis[i][i] = true;
dfs(i, i, graph[i][i]);
}
for(int i = 0 ; i < graph.length; ++i){
System.out.println(Arrays.toString(graph[i]));
}
index = 0;
for(String[] s : queries){
Integer a = map.get(s[0]);
Integer b = map.get(s[1]);
if(a == null || b == null){
ans[index++] = -1;
continue;
}
ans[index ++] = graph[a][b];
}
return ans;
}
public static void dfs(int a, int b, double value) {
for(int i = 0; i < graph.length; ++i){
if(graph[b][i] > 0 && !vis[a][i]){
vis[a][i] = true;
graph[a][i] = value * graph[b][i];
dfs(a, i, graph[a][i]);
}
}
}
private int map(Map map, int index, String[][] equations) {
for (String[] ss : equations) {
String a = ss[0];
String b = ss[1];
if (map.get(a) == null) {
map.put(a, index++);
}
if (map.get(b) == null) {
map.put(b, index++);
}
}
return index;
}
public static void main(String[] args) {
String[][] equations= new String[][]{
{
"a", "b"}, {
"b", "c"}};
double values[] = new double[]{
2, 3};
String[][] queries = { {
"a", "c"}, {
"b", "a"}, {
"a", "e"}, {
"a", "a"}, {
"x", "x"} };
Solution s = new Solution();
double[] ans = s.calcEquation(equations, values, queries);
System.out.println(Arrays.toString(ans));
}
}