基于陈述统计最多好人数

标签: 位运算 数组 回溯 枚举

难度: Hard

游戏中存在两种角色：

  • 好人：该角色只说真话。
  • 坏人：该角色可能说真话，也可能说假话。

给你一个下标从 0 开始的二维整数数组 statements ，大小为 n x n ，表示 n 个玩家对彼此角色的陈述。具体来说，statements[i][j] 可以是下述值之一：

  • 0 表示 i 的陈述认为 j 是 坏人 。
  • 1 表示 i 的陈述认为 j 是 好人 。
  • 2 表示 i 没有对 j 作出陈述。

另外，玩家不会对自己进行陈述。形式上，对所有 0 <= i < n ，都有 statements[i][i] = 2 。

根据这 n 个玩家的陈述，返回可以认为是 好人 的 最大 数目。

示例 1：

输入：statements = [[2,1,2],[1,2,2],[2,0,2]]
输出：2
解释：每个人都做一条陈述。
- 0 认为 1 是好人。
- 1 认为 0 是好人。
- 2 认为 1 是坏人。
以 2 为突破点。
- 假设 2 是一个好人：
    - 基于 2 的陈述，1 是坏人。
    - 那么可以确认 1 是坏人，2 是好人。
    - 基于 1 的陈述，由于 1 是坏人，那么他在陈述时可能：
        - 说真话。在这种情况下会出现矛盾，所以假设无效。
        - 说假话。在这种情况下，0 也是坏人并且在陈述时说假话。
    - 在认为 2 是好人的情况下，这组玩家中只有一个好人。
- 假设 2 是一个坏人：
    - 基于 2 的陈述，由于 2 是坏人，那么他在陈述时可能：
        - 说真话。在这种情况下，0 和 1 都是坏人。
            - 在认为 2 是坏人但说真话的情况下，这组玩家中没有一个好人。
        - 说假话。在这种情况下，1 是好人。
            - 由于 1 是好人，0 也是好人。
            - 在认为 2 是坏人且说假话的情况下，这组玩家中有两个好人。
在最佳情况下，至多有两个好人，所以返回 2 。
注意，能得到此结论的方法不止一种。

示例 2：

输入：statements = [[2,0],[0,2]]
输出：1
解释：每个人都做一条陈述。
- 0 认为 1 是坏人。
- 1 认为 0 是坏人。
以 0 为突破点。
- 假设 0 是一个好人：
    - 基于与 0 的陈述，1 是坏人并说假话。
    - 在认为 0 是好人的情况下，这组玩家中只有一个好人。
- 假设 0 是一个坏人：
    - 基于 0 的陈述，由于 0 是坏人，那么他在陈述时可能：
        - 说真话。在这种情况下，0 和 1 都是坏人。
            - 在认为 0 是坏人但说真话的情况下，这组玩家中没有一个好人。
        - 说假话。在这种情况下，1 是好人。
            - 在认为 0 是坏人且说假话的情况下，这组玩家中只有一个好人。
在最佳情况下，至多有一个好人，所以返回 1 。 
注意，能得到此结论的方法不止一种。

提示：

  • n == statements.length == statements[i].length
  • 2 <= n <= 15
  • statements[i][j] 的值为 0、1 或 2
  • statements[i][i] == 2

Submission

运行时间: 155 ms

内存: 16.1 MB

class Solution:
    def maximumGood(self, statements: List[List[int]]) -> int:
        n = len(statements) 
        l = list(range(n))
        k = n
        good = {}
        bad = {}
        for i in range(n):
            for j in range(n):
                if statements[i][j] == 1:
                    if i in good:
                        good[i].append(j)
                    else:
                        good[i] = [j]
                if statements[i][j] == 0:
                    if i in bad:
                        bad[i].append(j)
                    else:
                        bad[i] = [j]
        
        while k >= 0:
            for ll in combinations(l,k):
                res = True
                for x in ll:
                    if x in bad:
                        for y in bad[x]:
                            if y in ll:
                                res = False
                                break
                        if not res:
                            break
                    if x in good:
                        for y in good[x]:
                            if y not in ll:
                                res = False
                                break
                        if not res:
                            break
                if res:
                    return k                
            k -= 1
        return 0

Explain

此题解采用了暴力搜索的方法，尝试每种可能的好人组合，并验证每一种组合是否符合所有玩家的陈述。首先，代码中构建了两个字典 `good` 和 `bad` 来存储每个玩家认为的好人和坏人名单。随后，从可能的最大好人数开始向下逐一尝试所有组合（使用组合来列举所有可能的好人集合），检查这些组合是否符合所有玩家的陈述。如果某个组合符合，即返回该组合的大小作为最大可能的好人数。

时间复杂度: O(n^2 * 2^n)

空间复杂度: O(n^2)

class Solution:
    def maximumGood(self, statements: List[List[int]]) -> int:
        n = len(statements)
        l = list(range(n))
        k = n
        good, bad = {}, {}
        # 构建好人和坏人字典
        for i in range(n):
            for j in range(n):
                if statements[i][j] == 1:
                    good.setdefault(i, []).append(j)
                if statements[i][j] == 0:
                    bad.setdefault(i, []).append(j)
        # 从最大可能的好人数开始尝试
        while k >= 0:
            for ll in combinations(l, k):
                res = True
                # 验证当前组合是否符合所有玩家的陈述
                for x in ll:
                    if x in bad:
                        for y in bad[x]:
                            if y in ll:
                                res = False
                                break
                    if not res:
                        break
                    if x in good:
                        for y in good[x]:
                            if y not in ll:
                                res = False
                                break
                if res:
                    return k
            k -= 1
        return 0

Explore

在题解中没有特别提及对statements[i][i] = 2的处理。通常情况下，如果statements[i][i] = 2，可以理解为玩家对自己的陈述没有明确表态是好人还是坏人。在实际代码实现中，statements[i][i]的值无论是1还是0都不会影响到算法的逻辑，因为我们主要关注的是玩家对其他玩家的陈述。因此，可以简单地忽略玩家对自己的陈述或认为这种陈述不会对判断过程产生影响。

从最大可能的好人数开始尝试的原因是题目的目的是找出最多的好人数。若从最大数量开始尝试，并且能找到一个符合所有陈述的好人组合，那么这就直接是最大的可能好人数，可以立即结束搜索。这种方式比从最小数开始更高效，因为它避免了不必要的迭代和验证较小组合的情况，而这些较小组合的最大可能数量已被较大组合覆盖。

验证过程是通过检查每个玩家的陈述是否与假设的好人组合相符来实现的。首先，对于假设的好人组合中的每个玩家x，检查两个条件：1) 任何被x标记为坏人的玩家y不应出现在好人组合中；2) 任何被x标记为好人的玩家y必须出现在好人组合中。如果某个假设的好人x的陈述不符，即发现标记为坏人的y在好人组合中，或标记为好人的y不在好人组合中，则当前的好人组合不符合所有玩家的陈述，验证失败。只有当所有玩家的陈述都被当前组合满足时，这个组合才被认为是有效的。

使用字典来存储每个玩家的好人和坏人名单可以显著提升算法的效率。这种数据结构使得在验证过程中能够快速地访问和检查每个玩家的陈述，而不需要重复遍历statements数组来寻找相关信息。这样不仅减少了处理时间，也使得代码更加清晰和易于管理。此外，字典的键值对访问通常是常数时间复杂度，这对于频繁的查找操作是非常高效的。