Re: [閒聊] 每日LeetCode已回收
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
推
09/26 20:01,
3年前
, 1F
09/26 20:01, 1F
推
09/26 20:06,
3年前
, 2F
09/26 20:06, 2F
→
09/26 20:12,
3年前
, 3F
09/26 20:12, 3F
→
09/26 20:13,
3年前
, 4F
09/26 20:13, 4F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 11 之 719 篇)：