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

题目链接

来自第277场周赛第4题。
https://leetcode-cn.com/problems/maximum-good-people-based-on-statements/

题目内容

游戏中存在两种角色：

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

给你一个下标从 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个玩家的陈述，返回可以认为是 好人 的 最大 数目。

提示：

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

思路

由于题目数据量n小于等于15，每个人都有好人或者坏人两种情况。因此总共有2¹⁵ =32768种可能，而其中每个人究竟是好人还是坏人，我们可以利用二进制位的特性，进行相关的移位操作，来得到每一个人究竟是好人还是坏人。
比如，此时有8个人，那十进制15的二进制数是00001111，我们用0代表坏人，1代表好人，那么，右边4位(0-3号)代表好人，左边(4-7号)代表坏人。别的十进制数表示的状态以此类推。

代码

class Solution {
    
public:bool check(int state,vector<vector<int>>& statements,int n,int& cnt){
    //检测当前枚举情况是否可行，n表示几个人，state拆成二进制看更清楚,cnt代表当前情况有几个好人cnt = 0;//检查每个说真话的人for(int i = 0;i<n;i++){
    if(state>>i&1){
    //突破口，如果当前查询的人假设是好人，就检查他说的话和另一个人之间有无差距！for(int j=0;j<n;j++){
    int state_j = state>>j&1;if(statements[i][j]==0&&state_j||statements[i][j]==1&&!state_j){
    //好人判定为坏人和坏人判定为好人的矛盾情况，要退出！return false;}}cnt++;//找到一个好人}}return true;}int maximumGood(vector<vector<int>>& statements) {
    int n = statements.size();int ans = 0;for(int state = 0;state<(1<<n);state++){
    //枚举所有的可能int cnt = 0;if(check(state,statements,n,cnt)){
    ans = max(ans,cnt);//每次更新最大值}}return ans;}
};

总结

在数据量较少的情况下，可以使用二进制枚举的暴力方式得到答案。在lc的评论区看到一个大佬的类似二进制枚举题目收集，先码一下：

78. 子集
79. 猜字谜
80. 得分最高的单词集合
81. 最多可达成的换楼请求数目
82. 两个回文子序列长度的最大乘积
    另外，n<=20 的题目一般是暗示 状态压缩/二进制枚举/回溯