建设工程学部研究生培养网站,湖南常德邮编,优化关键词的方法包括,成都学校网站建设公司【问题描述】[中等]
给定一个由表示变量之间关系的字符串方程组成的数组#xff0c;每个字符串方程 equations[i] 的长度为 4#xff0c;并采用两种不同的形式之一#xff1a;ab 或 a!b。在这里#xff0c;a 和 b 是小写字母#xff08;不一定不…【问题描述】[中等]
给定一个由表示变量之间关系的字符串方程组成的数组每个字符串方程 equations[i] 的长度为 4并采用两种不同的形式之一ab 或 a!b。在这里a 和 b 是小写字母不一定不同表示单字母变量名。只有当可以将整数分配给变量名以便满足所有给定的方程时才返回 true否则返回 false。
【解答思路】 并查集
时间复杂度O(N^2) 空间复杂度O(1)
public class Solution {public boolean equationsPossible(String[] equations) {UnionFind unionFind new UnionFind(26);for (String equation : equations) {char[] charArray equation.toCharArray();if (charArray[1] ) {int index1 charArray[0] - a;int index2 charArray[3] - a;unionFind.union(index1, index2);}}for (String equation : equations) {char[] charArray equation.toCharArray();if (charArray[1] !) {int index1 charArray[0] - a;int index2 charArray[3] - a;if (unionFind.isConnected(index1, index2)) {// 如果合并失败表示等式有矛盾根据题意返回 falsereturn false;}}}// 如果检查了所有不等式都没有发现矛盾返回 truereturn true;}private class UnionFind {private int[] parent;public UnionFind(int n) {parent new int[n];for (int i 0; i n; i) {parent[i] i;}}public int find(int x) {while (x ! parent[x]) {parent[x] parent[parent[x]];x parent[x];}return x;}/*** param x* param y* return 如果合并成功返回 true*/public void union(int x, int y) {int rootX find(x);int rootY find(y);parent[rootX] rootY;}public boolean isConnected(int x, int y) {return find(x) find(y);}}public static void main(String[] args) {// String[] equations new String[]{ba, ab};// String[] equations new String[]{ab,bc,ac};// String[] equations new String[]{ab,b!c,ca};String[] equations new String[]{cc, bd, x!z};Solution solution new Solution();boolean res solution.equationsPossible(equations);System.out.println(res);}
}
【总结】
1.并查集知识小结
面试较少出现 酌情掌握
2.并查集时间复杂度分析 时间复杂度知乎链接https://www.zhihu.com/question/35090745
3.并查集练习题 转载链接https://leetcode-cn.com/problems/satisfiability-of-equality-equations/solution/shi-yong-bing-cha-ji-chu-li-bu-xiang-jiao-ji-he-we/
