基于陈述统计最多好人数
难度:
标签:
题目描述
游戏中存在两种角色：
- 好人：该角色只说真话。
- 坏人：该角色可能说真话，也可能说假话。
给你一个下标从 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或2statements[i][i] == 2
代码结果
运行时间: 155 ms, 内存: 16.1 MB
/*
* 思路：
* 1. 使用Java Stream生成所有可能的情况。
* 2. 对于每种情况，验证是否所有好人的陈述都是真实的。
* 3. 找出好人的最大数量。
*/
import java.util.stream.IntStream;
public class Solution {
public int maximumGood(int[][] statements) {
int n = statements.length;
return IntStream.range(0, 1 << n)
.filter(mask -> isValid(mask, statements))
.map(mask -> Integer.bitCount(mask))
.max()
.orElse(0);
}
private boolean isValid(int mask, int[][] statements) {
int n = statements.length;
return IntStream.range(0, n)
.filter(i -> (mask & (1 << i)) != 0) // i is considered a good person
.allMatch(i -> IntStream.range(0, n)
.filter(j -> statements[i][j] != 2)
.allMatch(j -> ((mask & (1 << j)) != 0) == (statements[i][j] == 1))
);
}
}解释
方法:
此题解采用了暴力搜索的方法，尝试每种可能的好人组合，并验证每一种组合是否符合所有玩家的陈述。首先，代码中构建了两个字典 `good` 和 `bad` 来存储每个玩家认为的好人和坏人名单。随后，从可能的最大好人数开始向下逐一尝试所有组合（使用组合来列举所有可能的好人集合），检查这些组合是否符合所有玩家的陈述。如果某个组合符合，即返回该组合的大小作为最大可能的好人数。
时间复杂度:
O(n^2 * 2^n)
空间复杂度:
O(n^2)
代码细节讲解
🦆
在您的解法中，您是如何处理玩家对自己的陈述（即statements[i][i] = 2）？
▷🦆
您的代码中使用了组合来尝试不同的好人集合，为什么选择从最大可能的好人数开始尝试而不是从最小数开始？
▷🦆
在您的代码中，对于每个可能的好人组合，您如何确保这个组合满足所有玩家的陈述？能否详细说明这一验证过程？
▷🦆
在您的题解中，您构建了两个字典good和bad来存储玩家对其他玩家的好人和坏人的看法，这种数据结构选择对算法的效率有何影响？
▷