leetcode:399. Evaluate Division-蒲公英云

leetcode:399. 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 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<String, Integer> map = new HashMap<String, Integer>();
        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<String, Integer> 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));
    }
}