2022秋招备战！每天写至少一篇Leetcode里Hard难度题目的题解

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

游戏中存在两种角色：

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

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

二进制枚举

首先看数据范围

2 <= n <= 15

一眼状压dp或者dfs枚举。

题意比较绕人，但是只要想到我们可以枚举到所有的情况再判断是否合法，也就不那么绕人了。

本题dfs和二进制枚举都是可以过的。二进制枚举的代码非常简洁好懂。

首先我们制造出2^n个n位的二进制串

for (int i = 0; i < (1 << n); i++)

每一个二进制串包含01两种情况。

1表示是好人，0表示是坏人。

我们从前往后对每个二进制位进行枚举，分析每个好人。

由于好人说话永远是对的，因此我们要从这里进行突破，判断该二进制串是否合法。

我们可以对好人的所有判断进行枚举，再和当前情况进行比较

if ((i >> j & 1) == 1) {
    for(int k = 0; k < n; k++) {
        if ((s[j][k] == 1 && (i >> k & 1) == 0 ) || (s[j][k] == 0 && (i >> k & 1) == 1) ){
            flag = false;
            break; 
        }
    }
    cur++;  
} 

比如说好人j说另外一个人k是坏人，然而在本字串里k被标记成了好人，这个情况就是不合法情况。

直接跳出循环。

如果合法，统计所有的好人数量，再和最终结果进行比较就好。

完整代码:

class Solution {
public:
    int maximumGood(vector<vector<int>>& s) {
        int n = s.size();
        int res = 0;

        for (int i = 0; i < (1 << n); i++) {
            bool flag = true;
            int cur = 0;
            for (int j = 0; j < n; j++) {
                if (!flag) break;
                if ((i >> j & 1) == 1) {
                    for(int k = 0; k < n; k++) {
                        if ((s[j][k] == 1 && (i >> k & 1) == 0 ) || (s[j][k] == 0 && (i >> k & 1) == 1) ) {
                            flag = false;
                            break;
                        }
                    }
                    cur++;  
                } 
            }
            if (flag) res = max(cur, res);
        }
        return res;
    }
};

类似题目:
一些二进制枚举题来自草莓奶昔🍓

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