leetcode:399. Evaluate Division

分手后的思念是犯贱 2022-09-26 02:13 166阅读 0赞

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