X

leetcode 886. Possible Bipartition 解题思路分析

题目大意:

可能的二分法

给定一组 N 人(编号为 1, 2, ..., N), 我们想把每个人分进任意大小的两组。

每个人都可能不喜欢其他人,那么他们不应该属于同一组。

形式上,如果 dislikes[i] = [a, b],表示不允许将编号为 ab 的人归入同一组。

当可以用这种方法将每个人分进两组时,返回 true;否则返回 false

示例 1:

输入:N = 4, dislikes = [[1,2],[1,3],[2,4]]
输出:true
解释:group1 [1,4], group2 [2,3]

示例 2:

输入:N = 3, dislikes = [[1,2],[1,3],[2,3]]
输出:false

示例 3:

输入:N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出:false

提示:

  1. 1 <= N <= 2000
  2. 0 <= dislikes.length <= 10000
  3. 1 <= dislikes[i][j] <= N
  4. dislikes[i][0] < dislikes[i][1]
  5. 对于 dislikes[i] == dislikes[j] 不存在 i != j

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=886

解题思路:

这道题是要用到dfs深度搜索的方法来解题。由于题目要求是将所有人分到两个组中,所以,我们可以先定义两个组为组一和组二,然后以任意一个人作为起始节点开始遍历。遍历的方法是查看当前人不喜欢的对象是谁,并将当前人和他不喜欢的对象们分在两个组中,然后再以其不喜欢的对象为节点继续查看其的不喜欢对象,直到遍历完所有的人。

在遍历过程中,如果遇到节点X已经被分过组,那么就要看当前要将X分入的组和之前的分组是否一致,如果出现矛盾,则可以结束遍历,直接返回false。如果一致,说明当前尚未出现矛盾点,另外注意,当前节点X之前已经被遍历过,因此不需要继续向下遍历。

以上就是写代码前应该考虑到的简单思路,但是有个问题,我们如何dps题目中给出的二维数组dislikes[][]呢?单纯看dislikes,它给出的仅仅是每两个人之间的局部关系,要做dps之前,我们需要将整体的关系网络描述出来才可以,因此,我们需要建立一个List<List<Integer>> dislikesMap对象,来保存每个人的不喜欢列表。List是有序数组,因此我们可以使用List的index来代表每个人,题目给出的人是从1开始起名的,所以,考虑到越界问题,dislikesMap的大小应该是人数加一(其中List[0]不保存数据,只是为了占位)。

举个例子,比如有1,2,3三个人,他们分别不喜欢除了自己以外的人,也就是说,1不喜欢2和3,2不喜欢1和3,3不喜欢1和2(无语的人际关系网。。。。)。那么, dislikesMap中保存的数据应为:

dislikesMap.get(0) = null;
dislikesMap.get(1) = {2, 3};
dislikesMap.get(2) = {1, 3};
dislikesMap.get(3) = {1, 2};

接下来按照最早的思路dfs这个dislikesMap即可,看下完整代码:

List<List<Integer>> dislikesMap; // 保存每个人的不喜欢列表
int[] groupArray; // 保存分组信息,下表代表人名,值代表组名。
                  // 默认0为尚未分组,1为组1,2为组2

public boolean possibleBipartition(int N, int[][] dislikes) {
    dislikesMap = new ArrayList<>();
    dislikesMap.add(null); // 为了保持index和人名一致,将第一个元素置空
    for (int n = 1; n <= N; n++) {
        // 为每个人名先创建一个空数组
        dislikesMap.add(new ArrayList<>());
    }

    for (int[] dis : dislikes) {
        // 由于不喜欢关系是相互的,所以,将双方分别加入到对方的不喜欢列表中
        dislikesMap.get(dis[0]).add(dis[1]);
        dislikesMap.get(dis[1]).add(dis[0]);
    }
    // 与dislikesMap同样,为了保持index和人名一致,从index为1开始保存数据。
    groupArray = new int[N + 1];
    for (int n = 1; n <= N; n++) {
        // 如果尚未将当前人分组,则dps当前人的关系树,分组失败返回false。
        if (groupArray[n] == 0 && !dfs(n, 1)) {
            return false;
        }
    }
    // 全部无矛盾分组成功,返回true
    return true;
}
// current为当前人,newGroupId为当前人被分到的组(1或者2)
private boolean dfs(int current, int newGroupId) {
    // 将当前人current的组信息设置为newGroupId
    groupArray[current] = newGroupId;
    // 从dislikesMap中遍历当前人不喜欢的人列表
    for (int next : dislikesMap.get(current)) {
        // 该不被当前人喜欢的人尚未被分组
        if (groupArray[next] == 0) {
            // 尝试将这个不被喜欢的人next分到与当前人不同的组,
            // 继续以next作为起点继续dfs,如果分组失败,返回false
            if (!dfs(next, newGroupId == 1 ? 2 : 1)) {
                return false;
            }
        } else if (groupArray[next] == newGroupId) {
            // 如果该不被当前人喜欢的人已被分组,并且与当前人在同一组,
            // 说明发生矛盾,即分组失败,返回false
            return false;
        }
    }
    // 全部分组成功
    return true;
}

本题解法用时16ms

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-886-possible-bipartition-解题思路分析/
Categories: leetcode
admin: