题目描述：

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.

题目大意：

以算式A / B = k的形式给出若干等式，其中A和B是以字符串表示的变量，k是实数（浮点数）。给定一些查询，返回结果。如果答案不存在，返回 -1.0

输入为：vector<pair<string, string>> euqations, vector<double>& values, vector<pair<string, string>> query。其中 equations.size() == values.size()，values总是正数。

输入永远是有效的。你可以假设查询结果不会出现除零错，并且等式之间不存在冲突。

解题思路：

Floyd算法求解传递闭包

输入等式可以看做一个有向图

例如等式a / b = 2.0，可以转化为两条边：<a, b>，<b, a>，其长度分别为2.0，0.5

遍历equations与values，利用字典g保存有向图中各边的长度，g的keys即为顶点集

最后调用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

 

本文链接：http://bookshadow.com/weblog/2016/09/11/leetcode-evaluate-division/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码