LeetCode399. 除法求值

给出方程式 A / B = k, 其中 A 和 B 均为代表字符串的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。

示例 :
给定 a / b = 2.0, b / c = 3.0
问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]

输入为: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)， 其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回vector<double>类型。

基于上述例子，输入如下：

equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果

思路:用一个HashMap映射字符串到一个数字序号的索引,将方程式中的点构成一个图,
例如equations(方程式) = [ ["a", "b"], ["b", "c"] ], 可以构成a->b,b->c的图,权重即为a/b和b/c;
之后进行计算,凡是图中可以到达的地方,便重新计算出权值。

class Solution {

    double[][] map ;
    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {

        map = new double[26][26];
        Map<String ,Integer> hashMap = new HashMap<>();
        int count = 0;
        for (int i=0;i<equations.length;i++){
            if (!hashMap.containsKey(equations[i][0])){
                hashMap.put(equations[i][0],count++);
            }
            if (!hashMap.containsKey(equations[i][1])){
                hashMap.put(equations[i][1],count++);
            }
        }

        for (int i=0;i<equations.length;i++){
            int indexA = hashMap.get(equations[i][0]);
            int indexB = hashMap.get(equations[i][1]);
            map[indexA][indexB] = values[i];
            map[indexB][indexA] = 1/values[i];
            map[indexA][indexA] = 1;
            map[indexB][indexB] = 1;
        }


        for (int i=0;i<map.length;i++){
            for (int j=0;j<map[0].length;j++){
                if (map[i][j]>0){
                    for (int k = 0; k<map[0].length;k++){
                        if (map[j][k]>0){
                            map[i][k] = map[i][j] * map[j][k];
                        }
                    }
                }
            }
        }

        double[] result = new double[queries.length];

        for (int i=0;i<queries.length;i++){
            if (!hashMap.containsKey(queries[i][0]) || !hashMap.containsKey(queries[i][1])){
                 result[i] = -1.0;
                 continue;
            }

            int indexA = hashMap.get(queries[i][0]);

            int indexB = hashMap.get(queries[i][1]);

            if (map[indexA][indexB]==0){
                result[i] = -1.0;
            }else{
                result[i]=map[indexA][indexB];
            }


        }

        return result;



    }
}