深圳seo优化服务,太原seo网络优化招聘网,网站不备案可以访问吗,动漫新闻资讯站1. 题目
给定一个由表示变量之间关系的字符串方程组成的数组#xff0c;每个字符串方程 equations[i] 的长度为 4#xff0c;并采用两种不同的形式之一#xff1a;ab 或 a!b。 在这里#xff0c;a 和 b 是小写字母#xff08;不一定不同#xf…1. 题目
给定一个由表示变量之间关系的字符串方程组成的数组每个字符串方程 equations[i] 的长度为 4并采用两种不同的形式之一ab 或 a!b。 在这里a 和 b 是小写字母不一定不同表示单字母变量名。
只有当可以将整数分配给变量名以便满足所有给定的方程时才返回 true否则返回 false。
示例 1
输入[ab,b!a]
输出false
解释如果我们指定a 1 且 b 1那么可以满足第一个方程
但无法满足第二个方程。没有办法分配变量同时满足这两个方程。示例 2
输出[ba,ab]
输入true
解释我们可以指定 a 1 且 b 1 以满足满足这两个方程。示例 3
输入[ab,bc,ac]
输出true示例 4
输入[ab,b!c,ca]
输出false示例 5
输入[cc,bd,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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考数据结构–并查集Disjoint-Set 类似题目 LeetCode 959. 由斜杠划分区域并查集 LeetCode 1202. 交换字符串中的元素并查集 LeetCode 1319. 连通网络的操作次数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(vectorstring 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
