Leetcode 399.除法求值

题目描述：

给你一个变量对数组 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：

1
2
3
4
5
6

输入：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：

1
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：

1
2

输入：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 由小写英文字母与数字组成

链接：

https://leetcode-cn.com/problems/evaluate-division

题目分析

  一开始被示例吓了一跳，以为 bd 表示的是 b 乘 d，那这道题要分析的情况就特别复杂，还好仔细阅读题目之后发现，Ai 或 Bi 表示的就是单个变量。（PS：在题解中也发现了同样的兄弟，他甚至还以为有 5b / 3d 这样的出现，那就更复杂了。）
  首先我们可以简化一下，将每个变量使用一个数字编号表示，这样做的好处是可以将它们在数组中处理，并且同时也可以统计所出现的变量个数。这个过程可以使用一个哈希表完成，统计不同的变量并给他们从 0 开始的编号，最后 count 的值就是变量的个数。

1
2
3
4
5
6
7
8
9
10

unordered_map<string, int> vars;
int count = 0;
for(const auto &it : equations){
    if(vars.find(it[0]) == vars.end()){
        vars[it[0]] = count++;
    }
    if(vars.find(it[1]) == vars.end()){
        vars[it[1]] = count++;
    }
}

  然后我们来分析一下变量之间的转化过程，比如我们有 a / b = x 和 b / c = y，那么我们就有 a / c = (a / b) * (b / c) = x * y。那么它们是有传递关系的，很容易可以想到使用图来表示，每个变量是一个结点，而它们之间的边权值就可以用除法值表示，那么我们可以得到一个有向图。对于没有直接连接的结点呢？其实就是路径中的各个权值乘起来。那么其实是一个最短路径问题，只是这个路径中的权值不是加起来的而是乘起来的，并且任意路径都是最短路径。我们最后需要对所有的问题作出回答，也即可能是任意两个变量之间的最短路径，对于这种多源最短路径问题可以使用 Floyd 算法。
  定义一个二维数组，result[i][j] 表示 i 到 j 的路径，我们先将初始值赋为 -1.0 也即题目中定义的不可达。先将直连的边加入数组，这里注意加入是双向的。然后使用三层循环遍历即可得到结果，而判断的条件从“最短”改为了“是否可达”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// Floyd
vector<vector<double>> result(count, vector<double>(count, -1.0));
for(int i = 0; i < equations.size(); i++){
    result[vars[equations[i][0]]][vars[equations[i][1]]] = values[i];
    result[vars[equations[i][1]]][vars[equations[i][0]]] = 1.0 / values[i];
}
for(int k = 0; k < count; k++){
    for(int i = 0; i < count; i++){
        for(int j = 0; j < count; j++){
            if(result[i][k] > 0 && result[k][j] > 0){
                result[i][j] = result[i][k] * result[k][j];
            }
        }
    }
}

  最后我们再对每一个问题进行查询并输出结果即可，注意题目中提到问题中的变量也有可能是从未出现过的，那么我们需要先判断是否出现再处理。

1
2
3
4
5
6
7
8
9
10
11

// answer
vector<double> answer;
for(const auto &it : queries){
    if(vars.find(it[0]) == vars.end() || vars.find(it[1]) == vars.end()){
        answer.emplace_back(-1.0);
    }
    else{
        answer.emplace_back(result[vars[it[0]]][vars[it[1]]]);
    }
}
return answer;

  时间复杂度：$O(E+N^3+Q)$，其中 $E、N、Q$ 分别表示初始边、变量、问题的数量。建立哈希表的时间是 $O(E)$，初始化图是 $O(E)$，而 Floyd 算法是 $O(N^3)$，最后每个问题查询时间是 $O(1)$，共有 $Q$ 个问题。这里是把变量的长度视为常数。
  空间复杂度：$O(N^2)$，其中 $N$ 表示出现的变量数。哈希表的大小是 $O(N)$，而进行 Floyd 算法得到的结果数组需要 $O(N^2)$ 的空间进行存放，作为结果返回的问题答案不计入空间复杂度。

  这道题还有并查集的做法。还没学会，待填的坑++。