代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
游戏中存在两种角色：
给你一个下标从 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].length2 <= n <= 15statements[i][j] 的值为 0、1 或 2
statements[i][i] == 2方法一：二进制枚举
二进制枚举好人的状态 $mask$，由于“好人只说真话”，我们借此判断 $statements$ 与 $mask$ 是否存在矛盾，不存在则获取 $mask$ 中好人的数量 $cnt$。迭代获取最大的合法 $cnt$。
时间复杂度 $O(2^n*n^2)$，其中 $n$ 表示 $statements$ 的长度。
class Solution:
def maximumGood(self, statements: List[List[int]]) -> int:
def check(mask):
cnt = 0
for i, s in enumerate(statements):
if (mask >> i) & 1:
for j, v in enumerate(s):
if v < 2 and ((mask >> j) & 1) != v:
return 0
cnt += 1
return cnt
return max(check(mask) for mask in range(1, 1 << len(statements)))
class Solution {
public int maximumGood(int[][] statements) {
int ans = 0;
for (int mask = 1; mask < 1 << statements.length; ++mask) {
ans = Math.max(ans, check(mask, statements));
}
return ans;
}
private int check(int mask, int[][] statements) {
int cnt = 0;
int n = statements.length;
for (int i = 0; i < n; ++i) {
if (((mask >> i) & 1) == 1) {
for (int j = 0; j < n; ++j) {
int v = statements[i][j];
if (v < 2 && ((mask >> j) & 1) != v) {
return 0;
}
}
++cnt;
}
}
return cnt;
}
}
class Solution {
public:
int maximumGood(vector<vector<int>>& statements) {
int ans = 0;
for (int mask = 1; mask < 1 << statements.size(); ++mask) ans = max(ans, check(mask, statements));
return ans;
}
int check(int mask, vector<vector<int>>& statements) {
int cnt = 0;
int n = statements.size();
for (int i = 0; i < n; ++i) {
if ((mask >> i) & 1) {
for (int j = 0; j < n; ++j) {
int v = statements[i][j];
if (v < 2 && ((mask >> j) & 1) != v) return 0;
}
++cnt;
}
}
return cnt;
}
};
func maximumGood(statements [][]int) int {
n := len(statements)
check := func(mask int) int {
cnt := 0
for i, s := range statements {
if ((mask >> i) & 1) == 1 {
for j, v := range s {
if v < 2 && ((mask>>j)&1) != v {
return 0
}
}
cnt++
}
}
return cnt
}
ans := 0
for mask := 1; mask < 1<<n; mask++ {
ans = max(ans, check(mask))
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
function maximumGood(statements: number[][]): number {
const n = statements.length;
function check(mask) {
let cnt = 0;
for (let i = 0; i < n; ++i) {
if ((mask >> i) & 1) {
for (let j = 0; j < n; ++j) {
const v = statements[i][j];
if (v < 2 && ((mask >> j) & 1) != v) {
return 0;
}
}
++cnt;
}
}
return cnt;
}
let ans = 0;
for (let mask = 1; mask < 1 << n; ++mask) {
ans = Math.max(ans, check(mask));
}
return ans;
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
