2151-基于陈述统计最多好人数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

游戏中存在两种角色：

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

给你一个下标从 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

方法一：使用状态压缩枚举所有可能的情况

思路与算法

由于本题中 n \leq 15，因此我们可以使用 O(2^n) 的时间枚举每一种情况：即每个人是好人或坏人有 2 种情况，一共有 n 个人。

我们可以使用状态压缩的方法进行枚举。具体地，我们遍历 [0, 2^n) 中的每一个数 mask，mask 的第 i 位为 1 就表示第 i 个人是好人，如果为 0 就表示第 i 个人是坏人。这样我们就可以不重复不遗漏地枚举所有的情况。

在枚举 mask 后，我们可以根据给定的数组 statements 来判断合法性：具体地：

  • 如果 statements}[i][j] = 0，那么 i 认为 j 是坏人，这说明要么 j 是坏人，要么 i 是坏人。因此如果 i 和 j 都是好人，即 mask 的第 i 位和第 j 位都是 1，那么就是不合法的；

  • 如果 statements}[i][j] = 1，那么 i 认为 j 是好人，这说明要么 j 是好人，要么 i 是坏人。因此如果 i 是好人并且 j 是坏人，即 mask 的第 i 位是 1 并且第 j 位是 0，那么就是不合法的；

  • 如果 statements}[i][j] = 2，那么可以忽略。

因此我们可以在 O(n^2) 的时间内判断 mask 的合法性：如果其合法，我们再统计出其包含的 1 的个数，并更新答案。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int maximumGood(vector<vector<int>>& statements) {
        int n = statements.size();
        int ans = 0;
        for (int mask = 1; mask < (1 << n); ++mask) {
            bool check = [&]() {
                for (int i = 0; i < n; ++i) {
                    for (int j = 0; j < n; ++j) {
                        if (i == j) {
                            continue;
                        }
                        if (statements[i][j] == 0) {
                            if ((mask & (1 << i)) && (mask & (1 << j))) {
                                return false;
                            }
                        }
                        else if (statements[i][j] == 1) {
                            if ((mask & (1 << i)) && !(mask & (1 << j))) {
                                return false;
                            }
                        }
                    }
                }
                return true;
            }();
            if (check) {
                ans = max(ans, __builtin_popcount(mask));
            }
        }
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maximumGood(self, statements: List[List[int]]) -> int:
        n = len(statements)
        ans = 0
        for mask in range(1, 1 << n):
            def check() -> bool:
                for i in range(n):
                    for j in range(n):
                        if i == j:
                            continue
                        if statements[i][j] == 0:
                            if mask & (1 << i) and mask & (1 << j):
                                return False
                        elif statements[i][j] == 1:
                            if mask & (1 << i) and not mask & (1 << j):
                                return False
                return True
            
            if check():
                ans = max(ans, bin(mask).count("1"))
        return ans
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
func maximumGood(statements [][]int) int {
	n := len(statements)
	ans := 0
	for mask := 1; mask < (1 << n); mask++ {
		check := func() bool {
			for i := 0; i < n; i++ {
				for j := 0; j < n; j++ {
					if i == j {
						continue
					}
					if statements[i][j] == 0 {
						if ((mask & (1 << i)) > 0) && ((mask & (1 << j)) > 0) {
							return false
						}
					} else if statements[i][j] == 1 {
						if ((mask & (1 << i)) > 0) && ((mask & (1 << j)) == 0) {
							return false
						}
					}
				}
			}
			return true
		}

		if check() {
			ans = max(ans, bits.OnesCount(uint(mask)))
		}
	}
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

复杂度分析

  • 时间复杂度：O(2^n \cdot n^2)。

  • 空间复杂度：O(1)。

 Comments
On this page
2151-基于陈述统计最多好人数