题目如下:
Equations are given in the format
A / B = k
, whereA
andB
are variables represented as strings, andk
is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return-1.0
.Example:
Givena / 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>> equations, vector<double>& values, vector<pair<string, string>> queries
, whereequations.size() == values.size()
, and the values are positive. This represents the equations. Returnvector<double>
.According to 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.
解题思路:我的方法是先计算equations中所有的表达式,算出所有能间接得到的值存入字典中。最后判断queries中的值是否存在于字典中即可。例如[‘a’,’b’]和[‘a’,’c’]两个组合,两者相除即可得到[‘c’,’b’]的组合。
代码如下:
class Solution(object):
def calcEquation(self, equations, values, queries):
"""
:type equations: List[List[str]]
:type values: List[float]
:type queries: List[List[str]]
:rtype: List[float]
"""
dic_char = {}
dic = {}
queue = []
for inx,(x,y) in enumerate(equations):
queue.append((x,y))
dic[(x,y)] = values[inx] while len(queue) > 0:
x,y = queue.pop(0)
for inx, (m,n) in enumerate(equations):
dic_char[m] = 1
dic_char[n] = 1
dic[(m, n)] = values[inx]
if (x == m and y == n) or (x == n and y == m):
continue
elif x == m:
if (y,n) not in dic and (n,y) not in dic:
dic[(n,y)] = dic[(x,y)] / values[inx]
queue.append((n,y))
elif x == n:
if (m,y) not in dic or (y,m) not in dic:
dic[(m,y)] = dic[(x,y)] * values[inx]
queue.append((m,y))
elif y == m :
if (x,n) not in dic and (n,x) not in dic:
dic[(x,n)] = dic[(x,y)] * values[inx]
queue.append((x,n))
elif y == n:
if (x,m) not in dic and (m,x) not in dic:
dic[(x,m)] = dic[(x,y)] / values[inx]
queue.append((x,m))
#print dic
#print dic_char res = []
for (x,y) in queries:
if x not in dic_char or y not in dic_char:
res.append(-1.0)
elif x == y:
res.append(1)
elif (x,y) in dic:
res.append(dic[(x,y)])
elif (y,x) in dic:
res.append(float(1.0)/float(dic[(y,x)]))
else:
res.append(-1.0)
return res