leetcode399

 1 class Solution:
 2     def calcEquation(self, equations: 'List[List[str]]', values: 'List[float]', queries: 'List[List[str]]') -> 'List[float]':
 3         sets = set()
 4         for eq in equations:
 5             sets.add(eq[0])
 6             sets.add(eq[1])
 7         l = sorted(list(sets))
 8         n = len(l)
 9         l1 = [[x] for x in l]
10         l2 = [[1.0]] * n
11 
12         nx = len(equations)
13         for i in range(nx):
14             p1 = equations[i][0]
15             p2 = equations[i][1]
16             pp = values[i]
17             if pp <= 1.0:
18                 p1,p2 = p2,p1
19                 pp = 1/pp
20                 print(p1,p2,pp)
21 
22             i1 = 0
23             i2 = 0
24             i22 = 0
25             ct = 0
26             for j in range(len(l1)):    
27                 if p1 in l1[j]:
28                     i1 = j
29                     i11 = l1[j].index(p1)
30                     ct += 1
31                 if p2 in l1[j]:
32                     i2 = j
33                     i22 = l1[j].index(p2)
34                     ct += 1
35                 if ct==2:
36                     break
37             l2[i1] =  [y * pp * l2[i2][i22] / l2[i1][i11] for y in l2[i1]]
38             l2[i1] = l2[i1] + l2[i2]
39             l2.pop(i2)
40             l1[i1] = l1[i1] + l1[i2]
41             l1.pop(i2)
42 
43         result = list()
44         for i in range(len(queries)):
45             q1 = queries[i][0]
46             q2 = queries[i][1]
47             if q1 not in l or q2 not in l:
48                 result.append(-1.0)
49             else:
50                 qi1 = 0
51                 qi2 = 0
52                 ct2 = 0
53                 for j in range(len(l1)):
54                     if q1 in l1[j]:
55                         qi1 = j
56                         ct2 += 1
57                     if q2 in l1[j]:
58                         qi2 = j
59                         ct2 += 1
60                     if ct2 == 2:
61                         break
62                 if qi1 != qi2:
63                     result.append(-1.0)
64                 else:
65                     k1 = l1[qi1].index(q1)
66                     k2 = l1[qi1].index(q2)
67                     v1 = l2[qi2][k1]
68                     v2 = l2[qi2][k2]
69                     result.append(v1/v2)
70 
71         return result

纯集合运算，并查集的思想。

将有运算关系的项目放在同一个集合中，并统一这个集合中的各项的倍数关系。

例如：a / b = 2.0, b / c = 3.0

则a,b,c三个项相互之间具有运算关系，通过程序形成两个集合

集合l1记录项的位置[a,b,c]，集合l2记录项的比例[6.0,3.0,1.0]，表示a:b:c=6.0:3.0:1.0。

有了这样的数据结构，就可以进行运算。比如计算a/c，就取a的比例值6.0处以c的比例值1.0，结果等于6.0。