Evaluate Division

You are given an array of variable pairs equations and an array of real numbers values , where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i] . Each Ai or Bi is a string that represents a single variable.

You are also given some queries , where queries[j] = [Cj, Dj] represents the $j^{th}$ query where you must find the answer for Cj / Dj = ? .

Return the answers to all queries. If a single answer cannot be determined, return $-1.0$.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

解题思路

　　可以发现各个变量之间存在传递性，比如有$a = 2b,~ b = 3c$，那么一定会有$a = 6c$。因此想到用floyd求传递闭包。假设$f(a,b) = c$表示$a = c \cdot b$，那么如果存在一个$k$，有$f(a,k) = c_1,~ f(k,b) = c_2$，那么应该有$a = c_1 \cdot c_2 \cdot b$，即$f(a,b) = f(a,k) \times f(k,b)$。

　　AC代码如下：

 1 class Solution {
 2 public:
 3     vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
 4         unordered_map<string, int> mp;
 5         int n = 0;
 6         for (int i = 0; i < equations.size(); i++) {
 7             for (int j = 0; j < 2; j++) {
 8                 if (!mp.count(equations[i][j])) mp[equations[i][j]] = ++n;
 9             }
10         }
11 
12         vector<vector<double>> f(n + 1, vector<double>(n + 1, -1));
13         for (int i = 1; i <= n; i++) {
14             f[i][i] = 1;    // 一开始有x = 1 * x，因此f[x][x] = 1
15         }
16 
17         for (int i = 0; i < equations.size(); i++) {
18             int a = mp[equations[i][0]], b = mp[equations[i][1]];
19             f[a][b] = values[i];        // a = val * b
20             f[b][a] = 1 / values[i];    // b = 1/val * a
21         }
22 
23         // floyd求传递闭包
24         for (int k = 1; k <= n; k++) {
25             for (int i = 1; i <= n; i++) {
26                 for (int j = 1; j <= n; j++) {
27                     if (f[i][k] != -1 && f[k][j] != -1) f[i][j] = f[i][k] * f[k][j];    // 只有f[i][k]和f[k][j]存在才可以转移
28                 }
29             }
30         }
31 
32         vector<double> ans;
33         for (auto &p : queries) {
34             ans.push_back(f[mp[p[0]]][mp[p[1]]]);   // 如果p[0]或p[1]不存在，那么mp[p[0]]或mp[p[1]]得到的值是0，而f[0][x]或f[x][0]都为-1，(0 <= x <= n)
35         }
36         return ans;
37     }
38 };

　　然后看了官方题解，发现还可以建图然后跑bfs。思路大概是把各个变量看作是结点，然后如果这两个变量之间存在关系，那么就连一条有向边，边的权值就是两个变量的比值。比如如果有$a = c \cdot b$，那么就在$a$到$b$连一条权值为$c$的边，在$b$到$a$连一条权值为$\frac{1}{c}$的边。

　　AC代码如下：

 1 class Solution {
 2 public:
 3     vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
 4         unordered_map<string, int> mp;
 5         int n = 0;
 6         for (int i = 0; i < equations.size(); i++) {
 7             for (int j = 0; j < 2; j++) {
 8                 if (!mp.count(equations[i][j])) mp[equations[i][j]] = n++;
 9             }
10         }
11 
12         // 建图
13         vector<pair<int, double>> g[n];
14         for (int i = 0; i < equations.size(); i++) {
15             int a = mp[equations[i][0]], b = mp[equations[i][1]];
16             g[a].push_back({b, values[i]});
17             g[b].push_back({a, 1 / values[i]});
18         }
19 
20         vector<double> ans;
21         for (auto &p : queries) {
22             if (!mp.count(p[0]) || !mp.count(p[1])) {   // 只要存在一个变量不在已知的关系中出现过，就返回-1
23                 ans.push_back(-1);
24                 continue;
25             }
26 
27             queue<int> q({mp[p[0]]});   // 询问的是p[0]/p[1]，因此将p[0]加入队列
28             vector<double> dist(n, -1); // dist[x]表示p[0]/x的值
29             dist[mp[p[0]]] = 1; // p[0]/p[0] = 1
30             while (!q.empty()) {
31                 int t = q.front();
32                 q.pop();
33 
34                 for (auto &it : g[t]) {
35                     if (dist[it.first] == -1) {
36                         // dist[t]表示值p[0]/t，t到it.first存在一条权值为it.second的边，即有it.second = t/it.first
37                         // 因此有dist[it.first] = p[0]/it.first = (p[0]/t) * (t/it.first) = dist[t] * it.second
38                         dist[it.first] = dist[t] * it.second;
39                         if (it.first == mp[p[1]]) break;
40                         q.push(it.first);
41                     }
42                 }
43             }
44             ans.push_back(dist[mp[p[1]]]);
45         }
46 
47         return ans;
48     }
49 };

　　甚至还可以用并查集，我都不知道怎么想到的。

　　应该是各个变量之间存在关系，因此可以放到一个集合，然后维护各个变量到根节点的距离，来表示集合中各个变量之间的关系。设$x$所在集合的代表元素（根节点）为$fa[x]$，定义$x$到根节点的距离$dist[x] = x / fa[x]$。

　　因此如果有询问求$a$和$b$的比值（关系），假设$a$和$b$在同一个集合中，根据定义有$dist[a] = a / fa[a],~ dist[b] = b / fa[b]$，其中$fa[a] = fa[b]$（因为$a$和$b$在同一个集合中），因此就有$a / b = dist[a] / dist[b]$。

　　已知条件$a / b = val$，现在要进行合并操作，首先应该让$fa[a]$（$a$所在集合的代表元素）指向$fa[b]$（$b$所在集合的代表元素），然后$dist[fa[a]]$的值应该是多少呢？首先根据定义应该有$dist[fa[a]] = fa[a] / fa[b]$，然后又有$dist[a] = a / fa[a]$（在调用find函数的时候已经路径压缩，$a$直接指向$fa[a]$，$b$同理），$dist[b] = b / fa[b]$，$a / b = dist[a] / dist[b]$，因此有

\begin{align*}
dist[fa[a]] &= \frac{fa[a]}{fa[b]} \\
&= \frac{fa[a]}{a} \times \frac{a}{b} \times \frac{b}{fa[b]} \\
&= \frac{1}{dist[a]} \times val \times dist[b]
\end{align*}

　　AC代码如下：

 1 class Solution {
 2 public:
 3     vector<int> fa;
 4     vector<double> dist;
 5 
 6     int find(int x) {
 7         if (fa[x] == x) return fa[x];
 8         int p = find(fa[x]);
 9         dist[x] *= dist[fa[x]];
10         return fa[x] = p;
11     }
12 
13     vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
14         unordered_map<string, int> mp;
15         int n = 0;
16         for (int i = 0; i < equations.size(); i++) {
17             for (int j = 0; j < 2; j++) {
18                 if (!mp.count(equations[i][j])) mp[equations[i][j]] = n++;
19             }
20         }
21 
22         for (int i = 0; i < n; i++) {
23             fa.push_back(i);
24             dist.push_back(1);
25         }
26         for (int i = 0; i < equations.size(); i++) {
27             int a = mp[equations[i][0]], b = mp[equations[i][1]];
28             int pa = find(a), pb = find(b);
29             fa[pa] = pb;
30             dist[pa] = values[i] * dist[b] / dist[a];
31         }
32         
33         vector<double> ans;
34         for (auto &p : queries) {
35             if (!mp.count(p[0]) || !mp.count(p[1])) {
36                 ans.push_back(-1);
37             }
38             else {
39                 int a = mp[p[0]], b = mp[p[1]];
40                 if (find(a) == find(b)) ans.push_back(dist[a] / dist[b]);
41                 else ans.push_back(-1);
42             }
43         }
44 
45         return ans;
46     }
47 };

参考资料　　

　　除法求值：https://leetcode.cn/problems/evaluate-division/solution/chu-fa-qiu-zhi-by-leetcode-solution-8nxb/