2021-01-06 | 399. 除法求值

「爱情、让人受尽委屈。」 2023-01-04 14:50 96阅读 0赞

### 1. 题目描述 ###

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

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

返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -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"]]
    输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
    解释：
    条件：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 ]

示例 2：

输入：equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
    输出：[3.75000,0.40000,5.00000,0.20000]

示例 3：

输入：equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
    输出：[0.50000,2.00000,-1.00000,-1.00000]

提示：

*  1 <= equations.length <= 20
 *  equations\[i\].length == 2
 *  1 <= Ai.length, Bi.length <= 5
 *  values.length == equations.length
 *  0.0 < values\[i\] <= 20.0
 *  1 <= queries.length <= 20
 *  queries\[i\].length == 2
 *  1 <= Cj.length, Dj.length <= 5
 *  Ai, Bi, Cj, Dj 由小写英文字母与数字组成

### 2. 解题思路 ###

对于 queries 中能得到结果的等式，它的除号两边的变量都能直接找到关联或能通过一些中间变量来找到关联，这样我们可以使用一种数据结构来保存这种关联，那就是图！

对 示例1，看下面的图，我们使用边权来表示这两个数的商，如 a / b = 2.0 ，b / a = 1 / 2.0  
![在这里插入图片描述][20210110222129494.png]

这样，我们要求图上任意两点的商，我们只需要乘上这两点之间的路径权值即可，如 a / c = a->b->c = 2.0 \* 3.0

图常用的存储结构有两种，邻接矩阵和邻接表，这里我选择使用邻接表。

这里使用了一个 map + array 来完成邻接表的创建。即使用 map 作为顶点表存储所有顶点，对一个顶点，使用一个数组 array 来存储与其相连的所有边。

因此对于 示例1，存储的邻接表就是这样的：

Map(3) { 
      'a' => [ [ 'b', 2 ] ],
      'b' => [ [ 'a', 0.5 ], [ 'c', 3 ] ],
      'c' => [ [ 'b', 0.3333333333333333 ] ]
    }

创建完邻接表后，遍历 queries 数组，若这两个变量均为邻接表中的顶点，我们就对其使用深度优先遍历计算它们的路径积，否则填入 -1.0：

### 3. 代码实现 ###

/** * @param {string[][]} equations * @param {number[]} values * @param {string[][]} queries * @return {number[]} */
    
    var calcEquation = function(equations, values, queries) { 
        let map = new Map(), res = [];
        let visit = new Map();  // visit 数组标记在搜索过程中是否访问过
    
        const dfs = (src, dst) => { 
            if (src === dst) { 
                return 1.0;
            }
    
            let adjs = map.get(src);
    
            for (let i = 0; i < adjs.length; ++i) { 
                let next = adjs[i];
                if (!visit.get(next[0])) { 
                    visit.set(next[0], true);
    
                    let ret = dfs(next[0], dst);
    
                    visit.set(next[0], false);
                    if (ret !== -1.0) { 
                        return next[1] * ret;
                    }
                }
            }
    
            return -1.0;
        };
    
        // 创建邻接表
        for (let i = 0; i < equations.length; ++i) { 
            let e = equations[i], v = values[i];
    
            if (!map.has(e[0])) { 
                map.set(e[0], []);
                visit.set(e[0], false);
            }
            if (!map.has(e[1])) { 
                map.set(e[1], []);
                visit.set(e[1], false);
            }
    
            let adj1 = map.get(e[0]);
            let adj2 = map.get(e[1]);
            adj1.push([e[1], v]);
            adj2.push([e[0], 1 / v]);
        }
    
        for (let q of queries) { 
            let n0 = q[0], n1 = q[1];
            if (map.has(n0) && map.has(n1)) { 
                visit.set(n0, true);
                res.push(dfs(n0, n1));
                visit.set(n0, false);
            } else { 
                res.push(-1.0);
            }
        }
    
        return res;    
    };

### 4. 提交结果 ###

![在这里插入图片描述][2021011022214677.png]

[20210110222129494.png]: /images/20221119/8c8f0d079f604dc39855fcbfa32e1148.png?
[2021011022214677.png]: /images/20221119/3301c11fab3b4d2bb51219145f97be05.png?