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
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));
    }
}