# LeetCode 399. Evaluate Divisio

@(LeetCode)

问题描述

以 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 ]`

并且有如下定义：

• equations 表示等式，其为二维数组，数组元素为字符串数组。如 [['a', 'b'], ['a', 'c']。
• values 为等式对应的结果，元素为浮点数，如 [1.0, 2.0]。
• queries 为待查询式子，也为二维数组，与 equations 格式一致。如 [['a', 'c'], ['b', 'd']]。

那么对于上述例子，可以表述如下。

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. 

求出 queries 中式子的值，以数组返回结果。

注意：输入永远是有效的。可以假设查询条件不会有冲突，也不会有除以 0 的情况。

想看英文原文的戳这里。

解题思路

递归解法

思路

从上面的栗子，我们可以得出几个简单的结论：

• 不在给定等式中的字符串的查询，返回 -1。比如 ["x", "x"]。

• 查询式子可以是一系列的操作后的结果，比如相乘/相除。

  1. 相乘。已知 a/b=3, b/c=4，求 a/c。

  (a/b) * (b/c) = a/c
  

  2. 相除。已知 a/b=3, c/b=4，求 a/c。

  (a/b) / (c/b) = a/c
  

  3. 乘除混合。已知 a/b=3, b/c=4, d/c=5，求 a/d。

  (a/b) * (b/c) / (d/c) = a/d
  

• 查询式子可能是倒数。

  比如已知 a/b=3, b/c=4，求 c/a。

对于上述问题，我们一个个来分析。

1. 不在给定等式中的字符串的查询，返回 -1。

   这个简单，只需要记下在等式中出现的字符串即可。

2. 一系列乘除混合运算的结果。

   既然可能出现相乘或相除，如果都考虑进来情况会比较复杂。那么我们可以转换为一种运算，即乘法。对于需要相除的，只需要乘以其倒数即可。

   比如：a/b=3, c/b=4，求 a/c。

   a/c = (a/b) / (c/b) = (a/b) * (b/c)
   

   这样就可以将其全部转换为乘法。

   但是如何求得 b/c 的值呢？也好办，只需要在记录时，同时记下其倒数的值。即同时记录： c/b = 4、b/c = 1/4。

3. 查询式子可能为倒数。

   在经过第二步的处理后，这个问题自然也解决了。因为可以转换为倒数相乘，而倒数的值是已知的。

   比如： a/b=3, b/c=4，求 c/a。

   转换为倒数相乘：c/a = b/a * c/b，而 b/a 与 c/b 的值已知。

另外，一个字符串可能会对应多个等式，也就是说字符串作为被除数，会有多个除数与之对应，如 a/c, a/b, a/d 等等。

我们需要同时记录下等式对应的值，所以记录的结构为 {'a': [{'ch': b}, 'value':3]}，字符串与一个数组对应。ch 表示被除数，value 表示等式的值。

在全部转换为乘法后，对于需要计算的查询式子，问题变为：如果可以找到一条链路，以被除数开始，除数结束，则式子是有结果的。假设存在 a->b->c 这条链路，那么可求出 a/c 的值。

在知道计算思路和存储结构后，最关键的一步是如何找到与查询式子相符的链路。

这里我没有想到好的方法，用的是穷举法。整体思路如下：

1. 逐个遍历以被除数开始的每一条可能的链路，如果中途遇到除数，则说明找到了查询式子。

2. 而由于我们存储了双向对应关系，在遍历时，需要记录已经处理的字符串，避免死循环。

栗子

比如：a/b=2, b/c=3，求 a/c。

根据上述记录规则，结果如下：

{
  'a' => [ { ch: 'b', value: 2 } ],
  'b' => [ { ch: 'a', value: 0.5 }, { ch: 'c', value: 3 } ],
  'c' => [ { ch: 'b', value: 0.3333333333333333 } ] 
 }

遍历过程为：

1. 以 a 开始遍历，遍历 a 对应的除数，这里只有 b。
2. 以 b 开始遍历，遍历 b 对应的除数。这里有 a 和 c。由于 a 是以访问过的，需要跳过。否则，会重新进入到 1 的步骤，引发死循环。因此，只需访问 c。
3. c 刚好是除数，则这是一条可行的链路。

如何计算等式最终的值？在遍历过程中，不断相乘即可，当访问的字符正好是除数时，此时的值即为结果。

代码

js 代码如下：

// 全局变量，存储最终等式值
var queryResult = -1
var calcEquation = function(equations, values, queries) {

    let results = new Array()
    let map = new Map()
    let i = 0
    while (i < equations.length) {
        const equation = equations[i]
        const value = values[i]

        const ch1 = equation[0]
        const ch2 = equation[1]
            
        // 记录双向对应关系
        recordValue(map, ch1, ch2, value)
        recordValue(map, ch2, ch1, 1/value)

        i += 1
    }

    i = 0
    while (i < queries.length) {
        const query = queries[i]

        queryResult = -1

        // 存储已经访问的字符
        let set = new Set()
        
        // 递归计算
        recursive(query[0], query[1], 1, map, set)

        results.push(queryResult)

        i += 1
    }

    return results
};

// 记录对应关系
var recordValue = function(map, ch1, ch2, value) {
    let list
    if (map.has(ch1)) {
        list = map.get(ch1)
    } else {
        list = new Array()
        map.set(ch1, list)
    }

    const obj = {
        ch: ch2,
        value: value
    }

    list.push(obj)
}

// 递归穷举遍历
var recursive = function(ch1, ch2, result, map, set) {

    // 如果字符都存在
    if (map.has(ch1) && map.has(ch2)) {
        if (ch1 === ch2) {
            queryResult = result
            return
        }

        const list = map.get(ch1)
        let i = 0

        // 记录已访问的 key，避免死循环，因为 map 中记录的是双向对应关系, a->[b], b->[a]
        set.add(ch1)

        while (i < list.length) {
            const obj = list[i]

            if (!set.has(obj.ch)) {
                const value = obj.value
                
                // 结果不断相乘
                recursive(obj.ch, ch2, result * value, map, set)
            }
            
            i += 1
        }
    }
}

非递归解法

这是在讨论区看到的一种解法，作为一种扩展思路。

它预先计算出所有可能组合的结果，最终要查询式子的结果只需查表即可。

1. 首先其记录等式的对应关系，包括双向对应以及和自身的对应关系。

   对于 a/b=2, b/c=3, c/d=4，其记录结果为：

   Map {
     'a' => Map { 'a' => 1, 'b' => 2 },
     'b' => Map { 'b' => 1, 'a' => 0.5, 'c' => 3 },
     'c' => Map { 'c' => 1, 'b' => 0.3333333333333333, 'd' => 4 },
     'd' => Map { 'd' => 1, 'c' => 0.25 } 
    }
   

2. 遍历所有 subMap 的 key 值所有可能的组合，计算出结果，并保存在原 map 中。

   比如对于 1 中的结果，其步骤为：

   • 取出 a 对应的 subMap 的键值数组，为 [a, b]，两两组合成新的式子。即 a/b、 b/a、a/a、b/a，计算结果后保存。
   • 取出 b 对应的 subMap 的键值数组，为 [b, a, c]，两两组合成新的式子。比如：a/c = a/b * b/c，a/b 和 b/c 已知。
   • 同理，分别取出 c 对应的键值数组，进行计算。
   • ...

   假设 key 为外层 map 的键值，subKey1 和 subKey2 分别为其对应 subMap 中的两个要组合的键值。

   那么结果计算公式如下：map[subKey1][subKey2] = map[subKey1][key] * map[key][subKey2]。

   其中 map[subKey1][key] 和 map[key][subKey2] 是已知的。

点此查看具体代码。