<div>
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [A<sub>i</sub>, B<sub>i</sub>] and values[i] represent the equation A<sub>i</sub> / B<sub>i</sub> = values[i]. Each A<sub>i</sub> or B<sub>i</sub> is a string that represents a single variable.
You are also given some queries, where queries[j] = [C<sub>j</sub>, D<sub>j</sub>] represents the j<sup>th</sup> query where you must find the answer for C<sub>j</sub> / D<sub>j</sub> = ?.
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:
<pre>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 ] </pre>
Example 2:
<pre>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] </pre>
Example 3:
<pre>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] </pre>
Constraints:
1 <= equations.length <= 20equations[i].length == 21 <= A<sub>i</sub>.length, B<sub>i</sub>.length <= 5values.length == equations.length0.0 < values[i] <= 20.01 <= queries.length <= 20queries[i].length == 21 <= C<sub>j</sub>.length, D<sub>j</sub>.length <= 5A<sub>i</sub>, B<sub>i</sub>, C<sub>j</sub>, D<sub>j</sub>consist of lower case English letters and digits.
</div>
题目大意：
根据已知除法结果求其他除法表达式
解题思路：
这是G家的面试题。图问题，因为每个除法式相乘可以得到query所要的，所以属于图问题。可以用BFS来遍历图，如已知a/b = 2, b/c = 3, 需要知道a/c, 就是2 x 3，所以只要从a开始， c为BFS的target，迭代时不断相乘
解题步骤：
N/A
注意事项：
- 核心思想： BFS来遍历图，迭代时不断相乘。无向图，因为a/c也可以c/a.
- BFS的注意事项后两个：BFS无解时候不存在的时候返回-1
- 两种edge cases： 若query中任意元素不在图中，返回-1(题目要求), 若元素相等，返回1
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
graph = collections.defaultdict(list)
for i, li in enumerate(equations):
graph[li[0]].append((li[1], values[i]))
graph[li[1]].append((li[0], 1 / values[i])) # remember it is an undirected graph
res = []
for query in queries:
if query[0] not in graph or query[1] not in graph:
res.append(-1.0)
elif query[0] in graph and query[0] == query[1]:
res.append(1.0)
else:
val = self.bfs(graph, query)
res.append(val)
return res
def bfs(self, graph, query):
queue = collections.deque([(query[0], 1)])
visited = set([queue[0]])
while queue:
node, parent_val = queue.popleft()
if node == query[1]:
return parent_val
for neighbor, val in graph[node]:
if neighbor in visited:
continue
queue.append((neighbor, parent_val * val))
visited.add(neighbor)
return -1 # remember
算法分析：
时间复杂度为O(（V + E) * m)，空间复杂度O(E), m为query数
