399. 除法求值

https://leetcode.cn/problems/evaluate-division/description/?envType=study-plan-v2&envId=top-interview-150

思路：读完题后我们可以发现这题的考察已经很明确了就是考我们矩阵，我们将矩阵构建出来后，这题就变成可达性分析题了。
所以解题步骤就是：1.构建矩阵 2.递归判断是否可达

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        // 处理所有出现的运算数
        int cnt = 0;
        HashMap<String, Integer> ch = new HashMap<>();
        for(int i = 0; i < equations.size(); i++) {
            String num1 = equations.get(i).get(0);
            String num2 = equations.get(i).get(1);
            if(!ch.containsKey(num1)) {
                ch.put(num1, cnt++);
            }
            if(!ch.containsKey(num2)) {
                ch.put(num2, cnt++);
            }
        }
        // 填充矩阵
        double[][] matrix = new double[cnt][cnt];
        for(int i = 0; i < equations.size(); i++) {
            String num1 = equations.get(i).get(0);
            String num2 = equations.get(i).get(1);
            matrix[ch.get(num1)][ch.get(num2)] = values[i];
            matrix[ch.get(num2)][ch.get(num1)] = 1.0 / values[i];
        }
        double[] res = new double[queries.size()];
        for(int i = 0; i < queries.size(); i++) {
            String num1 = queries.get(i).get(0);
            String num2 = queries.get(i).get(1);
            if(!ch.containsKey(num1) || !ch.containsKey(num2)) { // 如果出现没有出现的运算数，则直接返回-1
                res[i] = -1.0;
            } else { // 递归寻找可达路径
                // 标记某点是否到达过
                boolean[] signed = new boolean[cnt];
                signed[ch.get(num1)] = true;
                double sum = 1;
                res[i] = dfs(matrix, ch.get(num1), ch.get(num2), signed);
            }
        }
        return res;
    }

    public double dfs(double[][] matrix, int i, int j, boolean[] signed) {
        if(matrix[i][j] != 0) { // 如果可达，则直接返回结果
            return matrix[i][j];
        }
        double sum = 1;
        for(int k = 0; k < matrix.length; k++) {
                if(matrix[i][k] != 0 && !signed[k]) { // 如果可达且未到达过
                signed[k] = true;
                double dd = dfs(matrix, k, j, signed); // 递归寻找可达路径
                if(dd != -1) { // 如果可达就乘上权重
                    sum *= matrix[i][k] * dd;
                    return sum;
                }
            }
        }
        // 遍历所有情况没有找到可达路径就返回-1
        return -1;
    }

    public static void main(String[] args) {
        List<List<String>> equations = new ArrayList<>();
        equations.add(new ArrayList<>(List.of("x1","x2")));
        equations.add(new ArrayList<>(List.of("x2","x3")));
        equations.add(new ArrayList<>(List.of("x3","x4")));
        equations.add(new ArrayList<>(List.of("x4","x5")));
        double[] values = {3.0,4.0,5.0,6.0};
        List<List<String>> queries = new ArrayList<>();
        queries.add(new ArrayList<>(List.of("x1","x5")));
        queries.add(new ArrayList<>(List.of("x5","x2")));
        queries.add(new ArrayList<>(List.of("x2","x4")));
        queries.add(new ArrayList<>(List.of("x2","x2")));
        queries.add(new ArrayList<>(List.of("x2","x9")));
        queries.add(new ArrayList<>(List.of("x9","x9")));
        System.out.println(Arrays.toString(new Solution().calcEquation(equations, values, queries)));
    }
}