Satisfiability of Equality Equations - LeetCode
发布时间:2020-12-14 04:24:55 所属栏目:大数据 来源:网络整理
导读:目录 题目链接 注意点 解法 小结 题目链接 Satisfiability of Equality Equations - LeetCode 注意点 必须要初始化pre 解法 解法一:典型的并查集算法应用。先遍历所有等式,将等号两边的字母加入同一分类,每类中的字母都是相等的。然后遍历不等式,如果不
目录
题目链接Satisfiability of Equality Equations - LeetCode 注意点
解法解法一:典型的并查集算法应用。先遍历所有等式,将等号两边的字母加入同一分类,每类中的字母都是相等的。然后遍历不等式,如果不等号两边的字母属于同一类则返回false。时间复杂度O(nm) class Solution { public: map<char,char> pre; char Find(char x) { char r = x; while(pre[r] != r) { r = pre[r]; } return r; } void Join(char x,char y) { char fx = Find(x); char fy = Find(y); if(fx != fy) pre[fx] = fy; } void Init() { char letter[26] ={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; for (auto l:letter) { pre[l] = l; } } bool equationsPossible(vector<string>& equations) { Init(); for(auto e:equations) { if(e[1] == '=') Join(e[0],e[3]); } for(auto e:equations) { if(e[1] == '!' && Find(e[0]) == Find(e[3])) { return false; } } return true; } }; 小结
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |