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)) { // 如果出现没有出现的运算数，则直接返回-1res[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;}}}// 遍历所有情况没有找到可达路径就返回-1return -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)));}
}