一、题目
给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。
给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和 bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。
二、示例
2.1> 示例 1：
【输入】n = 4, dislikes = [[1,2],[1,3],[2,4]]
【输出】true
【解释】group1 [1,4], group2 [2,3]
2.2> 示例 2：
【输入】n = 3, dislikes = [[1,2],[1,3],[2,3]]
【输出】false
2.3> 示例 3：
【输入】n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
【输出】false
提示：
-
1<= n <=2000 -
0<= dislikes.length <=104 - dislikes[i].length ==
2 -
1<= dislikes[i][j] <=n - ai
<bi -
dislikes中每一组都 不同
三、解题思路
首先，创建一个二维数组，用来记录1到n个数之间的互斥关系。我们以n = 10，dislikes = [[1,2],[3,4],[5,6],[6,7],[8,9],[7,8]]为例，那么我们就可以得出如下矩阵图，如下图所示：
然后我们从第1行（row1）开始遍历，如果发现有“红色”，即表示发生了排斥，那么我们在对其进行深度遍历，如下图所示，我们遍历第1行的时候，发现2与其排斥，那么我们深度遍历第2行，由于第二行中没有与2排斥的数字了，所以我们得出结论，即：1在a组，2在b组。
我们继续遍历其他行，由于2已经被分配给了b组，所以第2行（row2）不遍历。
我们遍历第3行，由于发现与4发生了排斥，那么深度遍历到第4行，发现没有其他数组与4发生排斥，所以我们得出结论，即：3在a组，4在b组。
由于4已经被分配给了b组，所以第4行（row4）不遍历。我们遍历到第5行，发生如下遍历情况：
row5发现
数字6与它发生排斥，深度遍历到row6
row6发现数字7与它发生排斥，深度遍历到row7
row7发现数字8与它发生排斥，深度遍历到row8
row8发现数字9与它发生排斥，深度遍历到row9
row9发现没有数字与其排斥，所得得出分组结论：即：5在a组，6在b组，7在a组，8在b组，9在a组
最终结论就是，a组里有[1,3,5,7,9] ，b组里有[2,4,6,8] ，具体详情请见下图：
四、代码实现
4.1> 以二维数组方式实现矩阵
class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
int[][] matrix = new int[n + 1][n + 1];
for (int[] item : dislikes)
matrix[item[0]][item[1]] = matrix[item[1]][item[0]] = 1;
int[] record = new int[n + 1]; // 记录分组情况
for (int i = 1; i <= n ; i ++)
if (record[i] == 0 && ! dfs(matrix, record, i, 1, n)) return false;
return true;
}
private boolean dfs(int[][] matrix, int[] record, int index,int group, int n) {
record[index] = group;
for (int i = 1; i <= n ; i++) {
if(i == index || matrix[index][i] == 0) continue;
if (record[i] == group) return false;
if (record[i] == 0 && !dfs(matrix, record, i, group * -1, n)) return false;
}
return true;
}
}
4.2> 以List方式进行改造
class Solution {
public boolean possibleBipartition(int n, int[][] dislikes) {
List<Integer>[] matrix = new ArrayList[n + 1];
for (int i = 1; i < matrix.length; i++) matrix[i] = new ArrayList(n + 1);
for (int[] item : dislikes) {
matrix[item[0]].add(item[1]);
matrix[item[1]].add(item[0]);
}
int[] record = new int[n + 1]; // 记录分组情况
for (int i = 1; i < matrix.length ; i ++)
if (record[i] == 0 && !dfs(matrix, record, i, 1)) return false;
return true;
}
private boolean dfs(List<Integer>[] matrix, int[] record, int index, int group) {
record[index] = group;
for (int i = 0; i < matrix[index].size() ; i++) {
int num = matrix[index].get(i);
if (record[num] == group) return false;
if (record[num] == 0 && !dfs(matrix, record, num, group * -1)) return false;
}
return true;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论