給定一個(gè)由表示變量之間關(guān)系的字符串方程組成的數(shù)組，每個(gè)字符串方程 equations[i] 的長度為 4，并采用兩種不同的形式之一：“a==b” 或 “a!=b”。在這里，a 和 b 是小寫字母（不一定不同），表示單字母變量名。

只有當(dāng)可以將整數(shù)分配給變量名，以便滿足所有給定的方程時(shí)才返回 true，否則返回 false。

示例 1：

輸入：[“a==b”,“b!=a”]
輸出：false
解釋：如果我們指定，a = 1 且 b = 1，那么可以滿足第一個(gè)方程，但無法滿足第二個(gè)方程。沒有辦法分配變量同時(shí)滿足這兩個(gè)方程。

代碼

class Solution {int[] fa;public void init(){for(int i=0;i<fa.length;i++)fa[i]=i;}public int find(int x){if(x!=fa[x])fa[x]=find(fa[x]);return fa[x];}public void union(int x,int y){x=find(x);y=find(y);if(x==y) return;fa[x]=y;}public boolean equationsPossible(String[] equations) {fa=new int[26];init();for(String s:equations)//將相等的數(shù)字的湊成一個(gè)集合{ if(s.charAt(1)=='!') continue;int fx=find(s.charAt(0)-'a');int fy=find(s.charAt(3)-'a');union(s.charAt(0)-'a',s.charAt(3)-'a');}for(String s:equations)//如果不相等的兩個(gè)數(shù)字出現(xiàn)在同一個(gè)集合中則出現(xiàn)矛盾{if(s.charAt(1)=='=') continue;int fx=find(s.charAt(0)-'a');int fy=find(s.charAt(3)-'a');if(fx==fy) return false;} return true;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode990. 等式方程的可满足性（并查集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。