题目描述：

LeetCode 399. Evaluate Division

p> Equations are given in the format `A / B = k`, where `A` and `B` are variables represented as strings, and `k` is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return `-1.0`.

Example:
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 ].`

The input is: ` vector<pair<string, string>> euqations, vector<double>& values, vector<pair<string, string>> query `. where `equations.size() == values.size()`,the values are positive. this represents the equations.return ` vector<double>. `.
The example above: ` equations = [ ["a", "b"], ["b", "c"] ]. values = [2.0, 3.0]. queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. `

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

Floyd算法求解传递闭包

Python代码：

``````class Solution(object):
def calcEquation(self, equations, values, query):
"""
:type equations: List[List[str]]
:type values: List[float]
:type query: List[List[str]]
:rtype: List[float]
"""
g = collections.defaultdict(lambda: collections.defaultdict(int))
for (s, t), v in zip(equations, values):
g[s][t] = v
g[t][s] = 1.0 / v
for k in g:
g[k][k] = 1.0
for s in g:
for t in g:
if g[s][k] and g[k][t]:
g[s][t] = g[s][k] * g[k][t]
ans = []
for s, t in query:
ans.append(g[s][t] if g[s][t] else -1.0)
return ans
``````

Pingbacks已关闭。