一直超時，應該怎么優化？
class Solution:
L = {}
def equationsPossible(self, equations: List[str]) -> bool:
for i in range(27):
self.L[chr(ord('a')+i)] = chr(ord('a')+i)
T = []
for i in equations:
if '==' in i:
l = i.split('==')
self.found(l[0],l[-1])
else:
T.append(i.split('!='))
for i in T:
if self.aaa(self.L[i[0]]) == self.aaa(self.L[i[-1]]):
return False
return True
def found(self,pre,last):
if self.L[last] == last:
self.L[last] = self.L[pre]
else:
last = self.aaa(last)
self.L[last] = self.L[pre]
def aaa(self,last):
while self.L[last] != last:
last = self.L[last]
return last
uj5u.com熱心網友回復：
首先==關系是可以傳遞的，即a==b, b==c暗含a==c。可以先建立一個表ta = []。然后將輸入中的==兩邊的字母都加入ta。然后將!=兩邊的字母拿出來檢驗：檢驗這兩個字母是否都在ta中，如果是那么就回傳false；如果不是，那么繼續檢驗下一個!=兩邊的字母。代碼：def solution(input_alg):
ta = []
for x in input_alg:
if len(x) != 4:
return False
if x[1:3] == '==':
x_split = x.split('==')
if x_split[0] not in ta:
ta.append(x_split[0])
if x_split[1] not in ta:
ta.append(x_split[1])
for x in input_alg:
if x[1:3] == '!=':
x_split = x.split('!=')
if x_split[0] in ta and x_split[1] in ta:
return False
return True
uj5u.com熱心網友回復：
搞錯了。傳遞不一定值在一個序列中。uj5u.com熱心網友回復：
def solution(input_alg):
ta = {}
for x in input_alg:
if len(x) != 4:
return False
if x[1:3] == '==':
x_split = x.split('==')
u = x_split[0]; v = x_split[1]
if u in ta and v in ta:
u_lab = ta[u]
v_lab = ta[v]
if u_lab == v_lab: continue
for v1 in ta:
if ta[v1] == v_lab:
ta[v1] = u_lab
elif u in ta and v not in ta:
ta[v] = ta[u]
elif v in ta and u not in ta:
ta[u] = ta[v]
else:
ta[u] = u; ta[v] = u
for x in input_alg:
if x[1:3] == '!=':
x_split = x.split('!=')
u = x_split[0]; v = x_split[1]
if u in ta and v in ta and ta[u] == ta[v]:
return False
return True
定義字典ta中，將'=='兩邊的字母打相同的標簽，而且可以傳遞，傳遞規則就是如果'a==b'，那么標簽字典ta中和b的標簽相同的字母都必須打賞a的標簽。然后利用含'!='的等式來檢驗，如果存在某個'!='兩邊的字母標簽相同，那么等式方程不成立。
uj5u.com熱心網友回復：
def f(eqs):
s = set()
sp = [(eq[0], eq[1:-1], eq[-1]) for eq in eqs]
[s.update((x, y)) for x, e, y in sp if e=='==']
return all([not(x in s and y in s or x==y) for x,e,y in sp if e=='!='])
f(['a!=a'])
f(['a!=b'])
f(['a==b', 'b==c', 'c!=a'])
f(['a!=b', 'b!=c', 'c!=a'])
f(['a==b', 'b==c', 'c==a'])
f(['a==b', 'b!=a'])
f(['a==b', 'b!=c'])
f(['a==b', 'b==c', 'c!=d', 'd!=a'])
f(['a!=b', 'b!=c', 'c!=d', 'd==a'])
結果: FTFTTFTTT
uj5u.com熱心網友回復：
試一試 f(['a==b', 'b==c', 'c!=e', 'd==e'])。你的函式結果為F，事實上為T。轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/245864.html