列表

详情

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

游戏中存在两种角色：

给你一个下标从 0 开始的二维整数数组 statements ，大小为 n x n ，表示 n 个玩家对彼此角色的陈述。具体来说，statements[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 。 
注意，能得到此结论的方法不止一种。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int maximumGood(vector<vector<int>>& statements) { } };

python3 解法, 执行用时: 3236 ms, 内存消耗: 16 MB, 提交时间: 2023-09-26 09:47:37 

class Solution:
    def maximumGood(self, statements: List[List[int]]) -> int:
        """
        有 n 个人，每个人可能是好人，也可能是坏人，
        因此这 n 个人的好坏有 2^n 种情况。

        二进制枚举好人（一共 2^n 种情况），
        然后根据好人的陈述来判断合法性：

        因为好人只说真话，那么：
            - 好人对好人的陈述只能是 1 或 2，即不能是 0
            - 好人对坏人的陈述只能是 0 或 2，即不能是 
        """

        def check(good: List[int], bad: List[int]) -> bool:
            # 1. 检查好人对好人的陈述
            # 好人对好人的陈述只能是 1 或 2，即不能是 0
            for i in good:
                for j in good:
                    if i != j and statements[i][j] == 0:
                        return False
            
            # 2. 检查好人对坏人的陈述
            # 好人对坏人的陈述只能是 0 或 2，即不能是 1
            for i in good:
                for j in bad:
                    if statements[i][j] == 1:
                        return False

            return True


        n = len(statements)
        res = 0
        # 二进制枚举好人
        for mask in range(1 << n):
            # good: 好人
            #  bad: 坏人
            good, bad = [], []
            
            for i in range(n):
                if mask & 1:
                    good.append(i)
                else:
                    bad.append(i)
                mask >>= 1

            if check(good, bad):
                res = max(res, len(good))

        return res

java 解法, 执行用时: 23 ms, 内存消耗: 39.5 MB, 提交时间: 2023-09-26 09:45:50 

class Solution {
    public int maximumGood(int[][] statements) {
        var ans = 0;
        var n = statements.length;
        next:
        for (var i = 1; i < 1 << n; i++) {
            var cnt = 0; // i 中好人个数
            for (var j = 0; j < n; j++) {
                if (((i >> j) & 1) == 1) { // 枚举 i 中的好人 j
                    for (var k = 0; k < n; k++) { // 枚举 j 的所有陈述
                        if (statements[j][k] < 2 && statements[j][k] != ((i >> k) & 1)) { // 该陈述与实际情况矛盾
                            continue next;
                        }
                    }
                    cnt++;
                }
            }
            ans = Math.max(ans, cnt);
        }
        return ans;
    }
}

python3 解法, 执行用时: 1724 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-26 09:45:21 

class Solution:
    def maximumGood(self, statements: List[List[int]]) -> int:
        def check(i: int) -> int:
            cnt = 0  # i 中好人个数
            for j, row in enumerate(statements):  # 枚举 i 中的好人 j
                if (i >> j) & 1:
                    if any(st < 2 and st != (i >> k) & 1 for k, st in enumerate(row)):
                        return 0  # 好人 j 的某个陈述 st 与实际情况矛盾
                    cnt += 1
            return cnt

        return max(check(i) for i in range(1, 1 << len(statements)))

cpp 解法, 执行用时: 92 ms, 内存消耗: 8.6 MB, 提交时间: 2023-09-26 09:43:32 

class Solution {
public:
    int maximumGood(vector<vector<int>> &statements) {
        int ans = 0, n = statements.size();
        for (int i = 1; i < 1 << n; ++i) {
            int cnt = 0; // i 中好人个数
            for (int j = 0; j < n; ++j) {
                if ((i >> j) & 1) { // 枚举 i 中的好人 j
                    for (int k = 0; k < n; ++k) { // 枚举 j 的所有陈述
                        if (statements[j][k] < 2 && statements[j][k] != ((i >> k) & 1)) { // 该陈述与实际情况矛盾
                            goto next;
                        }
                    }
                    ++cnt;
                }
            }
            ans = max(ans, cnt);
            next:;
        }
        return ans;
    }
};

golang 解法, 执行用时: 24 ms, 内存消耗: 2.4 MB, 提交时间: 2023-09-26 09:43:11 

/**
 * 二进制枚举，1 ~ 2^n - 1 种情况
 */
func maximumGood(statements [][]int) (ans int) {
next:
	for i := 1; i < 1<<len(statements); i++ {
		cnt := 0 // i 中好人个数
		for j, row := range statements {
			if i>>j&1 == 1 { // 枚举 i 中的好人 j
				for k, st := range row { // 枚举 j 的所有陈述 st
					if st < 2 && st != i>>k&1 { // 该陈述与实际情况矛盾
						continue next
					}
				}
				cnt++
			}
		}
		if cnt > ans {
			ans = cnt
		}
	}
	return
}

上一题

© 2024 leetcode.cn