推 Rushia: 大師 09/26 20:01
推 nh60211as: python 不能 char 相減嗎？ 'z' - 'a' 這樣 09/26 20:06
→ pandix: 不行== 很討厭 09/26 20:12
→ nh60211as: 糞語言 09/26 20:13
990. Satisfiability of Equality Equations
給你很多"xi==yi" / "xi!=yi"，問你有沒有合法的解，有就回傳 True，反之 False
變數名稱都是小寫英文字母。
Example 1:
Input: equations = ["a==b","b!=a"]
Output: false
Example 2:
Input: equations = ["b==a","a==b"]
Output: true
思路:
1.disjoint set經典題，把相等的變數都加到同一個 set 裡就好。
遇到 "!=" 就判斷兩個是不是在同一個 set 裡，是的話就矛盾了
2.避免出現 ["a!=b", "a==b"] 這種先不等式再等式的情況，要先把等式做完
所以先 sort 一次 equations 把等式拿到前面先做
Python code:
class Solution:
def equationsPossible(self, equations: List[str]) -> bool:
root = list(range(26))
equations.sort(key = lambda x: x[1] == '!')
def find(x):
if root[x] != x:
root[x] = find(root[x])
return root[x]
for equation in equations:
a, b = ord(equation[0])-97, ord(equation[3])-97,
if equation[1] == '=':
root[find(a)] = find(b)
elif find(a) == find(b):
return False
return True
contest 剛出完一題馬上又幫大家複習一次 disjoint set==
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.233.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1664193344.A.19C.html