题目：LeetCode
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 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] 是 '='
解题思路
创建一个26*26的数组，用来存取字母间的关系：
- 1.如果数组relation[i][j] = 1,那么说明i表示的字母和j表示的字母对应的数值相同
- 2.如果数组relation[i][j] = 0,那么说明i表示的字母和j表示的字母对应的数值不知道是否相同
- 3.如果数组relation[i][j] = -1,那么说明i表示的字母和j表示的字母对应的数值不相同 自己和自己肯定相同，然后把题目给的存一下，注意如果出现了矛盾就返回false，然后用三个for来判断是否出现a==b,b==c,但是a!=c这样的情况，出现了就直接返回false。 最后返回true
代码实现
public boolean equationsPossible(String[] equations) {
int[][] relation = new int[26][26];
for(int i = 0; i < 26; i++) relation[i][i] = 1;
for(int i = 0; i < equations.length; i++){
char flag = equations[i].charAt(1);
int x = equations[i].charAt(0) - 'a';
int y = equations[i].charAt(3) - 'a';
if(flag == '!' && relation[x][y] != 1){
relation[x][y] = -1;
relation[y][x] = -1;
}
else if(flag == '=' && relation[x][y] != -1) {
relation[x][y] = 1;
relation[y][x] = 1;
}
else return false;
}
for(int i = 0; i < 26; i++){
for(int j = 0; j < 26; j++){
for(int k = 0; k < 26; k++){
if(relation[i][j] == 1 && relation[j][k] == 1){
if(relation[i][k] == -1) return false;
else {
relation[i][k] = 1;
relation[k][i] = 1;
}
}
}
}
}
return true;
}
复制代码
复杂度分析
- 时间复杂度：<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><annotation encoding="application/x-tex">O(N^2)</annotation></semantics></math>O(N2)
- 空间复杂度：<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><annotation encoding="application/x-tex">O(N^2)</annotation></semantics></math>O(N2)
网友评论