本文共 5353 字，大约阅读时间需要 17 分钟。

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

示例 1：

输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]

输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]

输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]

1.第一步就是用一个哈希表来存储存在的每个字符串，把每个字符串当作一个点，利用哈希表可以把这个点映射成一个整数(下标index)。第二步就是通过条件把每个点能直接连接的点以及权值作为一条边存储。最后一步就是进行广度优先遍历得到以每个点为起点到其他点能够得到的值。

        图+有向权值边+DFS。从这道题可以总结一下怎么建图，建边，并赋上权重。

class Solution {    public double[] calcEquation(List
   
    
     > equations, double[] values, List
     
      
       > queries) {        int nvars = 0;//统计点的数量        Map
       
         variables = new HashMap<>();//用一个哈希表存储每个节点，并把每个节点映射成整数        int n = equations.size();        for (int i = 0;i < n;i++) {//把equations中出现过的字符串都加入哈希表中            if (!variables.containsKey(equations.get(i).get(0))) {                variables.put(equations.get(i).get(0),nvars);                nvars++;            }            if (!variables.containsKey(equations.get(i).get(1))) {                variables.put(equations.get(i).get(1),nvars);                nvars++;            }        }        //对于每个点，存储其直接连接到的所有点以及对应的权值        List
        
         [] edges = new List[nvars]; for (int i = 0;i < nvars;i++) { edges[i] = new ArrayList
         
          (); } for (int i = 0;i < n;i++) {//把条件里的每一组连接起来 int va = variables.get(equations.get(i).get(0)); int vb = variables.get(equations.get(i).get(1)); edges[va].add(new Pair(vb,values[i])); edges[vb].add(new Pair(va,1/values[i])); } int queriesCount = queries.size(); double[] ret = new double[queriesCount]; for (int i = 0;i < queriesCount;i++) { List
          
            query = queries.get(i); double result = -1.0; //只有当两个字符串都是哈希表中存在的条件时，才需要继续往下计算，否则就是-1.0 if (variables.containsKey(query.get(0)) && variables.containsKey(query.get(1))) { int ia = variables.get(query.get(0));//得到第一个点的下标 int ib = variables.get(query.get(1));//得到第二个点的下标 if (ia == ib) { result = 1.0; } else { Queue
           
             points = new LinkedList<>();//用一个队列来存储遍历到的节点(广度优先遍历) points.offer(ia); double[] ratios = new double[nvars];//存储从起点遍历到剩下每个点的比率 Arrays.fill(ratios,-1.0); ratios[ia] = 1.0;//起点比率初始化为1.0 while (!points.isEmpty() && ratios[ib] < 0) { //rations小于0表示当前ib点未被访问过 int x = points.poll();//取出当前起点 for (Pair pair : edges[x]) {//遍历这个起点能达到的每条边 int y = pair.index; double val = pair.value; if (ratios[y] < 0) { ratios[y] = ratios[x] * val;//计算到达这个点的比率 points.offer(y);//把新的点加入队列 } } } result = ratios[ib]; } } ret[i] = result; } return ret; }}class Pair{ int index;//表示当前节点连接的点的下标 double value;//表示权值 Pair(int index,double value) { this.index = index; this.value = value; }}
           
          
         
        
       
      
     
    
   

2.Floyd算法。对于查询数量很多的情形，如果为每次查询都独立搜索一次，则效率会变低。为此，我们不妨对图先做一定的预处理，随后就可以在较短的时间内回答每个查询。在本题中，我们可以使用Floyd算法，预先计算出任意两点之间的距离。

参考：

class Solution {    public double[] calcEquation(List
   
    
     > equations, double[] values, List
     
      
       > queries) {        int nvars = 0;//点的数量        Map
       
         variables = new HashMap<>();//哈希表存储每个点，并且映射到每个点的下标        int n = equations.size();        for (int i = 0;i < n;i++) {//在哈希表中存储每个存在的字符串            if (!variables.containsKey(equations.get(i).get(0))) {                variables.put(equations.get(i).get(0),nvars);                nvars++;            }            if (!variables.containsKey(equations.get(i).get(1))) {                variables.put(equations.get(i).get(1),nvars);                nvars++;            }        }        //Floyd算法        double[][] graph = new double[nvars][nvars];        for (int i = 0;i < nvars;i++) {            Arrays.fill(graph[i],-1.0);        }         for (int i = 0;i < n;i++) {//初始化动态数组，对能直接连接的点进行赋值            int va = variables.get(equations.get(i).get(0));            int vb = variables.get(equations.get(i).get(1));            graph[va][vb] = values[i];            graph[vb][va] = 1.0 / values[i];        }        for (int k = 0;k < nvars;k++) {//表示中介点的意思            for (int i = 0;i < nvars;i++) {                for (int j = 0;j < nvars;j++) {                    if (graph[i][k] > 0 && graph[k][j] > 0) {//只有当乘积大于0，即表明从i点可以到j点时，才进行更新                        graph[i][j] = graph[i][k] * graph[k][j];                    }                }            }        }        int queriesCount = queries.size();        double[] ret = new double[queriesCount];        for (int i = 0;i < queriesCount;i++) {            List
        
          query = queries.get(i); double result = -1.0; if (variables.containsKey(query.get(0)) && variables.containsKey(query.get(1))) {//只有当两个字符串都存在才有可能找到结果 int ia = variables.get(query.get(0)); int ib = variables.get(query.get(1)); if (graph[ia][ib] > 0) { result = graph[ia][ib]; } } ret[i] = result; } return ret; }}
        
       
      
     
    
   

题源：

转载地址：https://blog.csdn.net/xxyneymar/article/details/122184788 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！