1. 題目

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

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

示例 1： 輸入：["a==b","b!=a"] 輸出：false 解釋：如果我們指定，a = 1 且 b = 1，那么可以滿足第一個方程， 但無法滿足第二個方程。沒有辦法分配變量同時滿足這兩個方程。示例 2： 輸出：["b==a","a==b"] 輸入：true 解釋：我們可以指定 a = 1 且 b = 1 以滿足滿足這兩個方程。示例 3： 輸入：["a==b","b==c","a==c"] 輸出：true示例 4： 輸入：["a==b","b!=c","c==a"] 輸出：false示例 5： 輸入：["c==c","b==d","x!=z"] 輸出：true提示： 1 <= equations.length <= 500 equations[i].length == 4 equations[i][0] 和 equations[i][3] 是小寫字母 equations[i][1] 要么是 '='，要么是 '!' equations[i][2] 是 '='

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/satisfiability-of-equality-equations
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

參考：數(shù)據(jù)結(jié)構(gòu)–并查集（Disjoint-Set）
類似題目：
LeetCode 959. 由斜杠劃分區(qū)域（并查集）
LeetCode 1202. 交換字符串中的元素（并查集）
LeetCode 1319. 連通網(wǎng)絡(luò)的操作次數(shù)（BFS/DFS/并查集）
程序員面試金典 - 面試題 17.07. 嬰兒名字（并查集）

class uni {int f[26]; public:uni(){for(int i = 0; i < 26; ++i)f[i] = i;}int find(int a){if(f[a] == a)return f[a];return f[a] = find(f[a]);}void merge(int a, int b){int fa = find(a);int fb = find(b);f[fa] = fb;} }; class Solution { public:bool equationsPossible(vector<string>& equations) {uni u;int a, b, i;for(i = 0; i < equations.size(); ++i){if(equations[i][1]=='='){a = equations[i][0]-'a';b = equations[i][3]-'a';u.merge(a,b);}}for(i = 0; i < equations.size(); ++i){if(equations[i][1]=='!'){a = equations[i][0]-'a';b = equations[i][3]-'a';if(u.find(a) == u.find(b))return false;}}return true;} };

12 ms 11.2 MB

總結(jié)

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

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