Hard

题目描述

有两种类型的人：

  • 好人：总是说真话的人。
  • 坏人：可能说真话也可能说谎的人。

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

示例 2：

输入：statements = [[2,0],[0,2]]
输出：1

约束条件：

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

解题思路

这是一个状态枚举问题。由于人数最多只有 15 人，我们可以使用位掩码来枚举所有可能的好人和坏人的组合。

核心思路：

  1. 状态枚举：使用位掩码表示每个人是好人（1）还是坏人（0），总共有 2^n 种可能的状态。

  2. 一致性检验：对于每种状态，我们需要检验是否满足以下约束：

    • 好人的所有陈述都必须与当前状态一致
    • 坏人的陈述可以是真话也可以是假话，所以不需要检验

  3. 具体验证过程：

    • 遍历所有被标记为好人的人
    • 检查他们的每个陈述是否与当前状态匹配
    • 如果陈述为 1（认为某人是好人），那么该人在当前状态中也必须是好人
    • 如果陈述为 0（认为某人是坏人），那么该人在当前状态中也必须是坏人
    • 如果陈述为 2（没有陈述），则跳过

  4. 优化：可以使用位运算来高效地操作和检查状态。

时间复杂度为 O(n² × 2^n)，空间复杂度为 O(1)。由于 n ≤ 15，这种解法完全可行。

代码实现

class Solution {
public:
    int maximumGood(vector<vector<int>>& statements) {
        int n = statements.size();
        int maxGood = 0;
        
        // 枚举所有可能的状态（位掩码）
        for (int mask = 0; mask < (1 << n); mask++) {
            bool valid = true;
            
            // 检查当前状态是否有效
            for (int i = 0; i < n && valid; i++) {
                // 如果 i 是好人，检查他的所有陈述
                if (mask & (1 << i)) {
                    for (int j = 0; j < n; j++) {
                        if (statements[i][j] != 2) {
                            // 检查陈述是否与当前状态一致
                            bool jIsGood = (mask & (1 << j)) != 0;
                            if ((statements[i][j] == 1) != jIsGood) {
                                valid = false;
                                break;
                            }
                        }
                    }
                }
            }
            
            if (valid) {
                maxGood = max(maxGood, __builtin_popcount(mask));
            }
        }
        
        return maxGood;
    }
};

class Solution:
    def maximumGood(self, statements: List[List[int]]) -> int:
        n = len(statements)
        max_good = 0
        
        # 枚举所有可能的状态（位掩码）
        for mask in range(1 << n):
            valid = True
            
            # 检查当前状态是否有效
            for i in range(n):
                # 如果 i 是好人，检查他的所有陈述
                if mask & (1 << i):
                    for j in range(n):
                        if statements[i][j] != 2:
                            # 检查陈述是否与当前状态一致
                            j_is_good = bool(mask & (1 << j))
                            if (statements[i][j] == 1) != j_is_good:
                                valid = False
                                break
                    if not valid:
                        break
            
            if valid:
                max_good = max(max_good, bin(mask).count('1'))
        
        return max_good

public class Solution {
    public int MaximumGood(int[][] statements) {
        int n = statements.Length;
        int maxGood = 0;
        
        // 枚举所有可能的状态（位掩码）
        for (int mask = 0; mask < (1 << n); mask++) {
            bool valid = true;
            
            // 检查当前状态是否有效
            for (int i = 0; i < n && valid; i++) {
                // 如果 i 是好人，检查他的所有陈述
                if ((mask & (1 << i)) != 0) {
                    for (int j = 0; j < n; j++) {
                        if (statements[i][j] != 2) {
                            // 检查陈述是否与当前状态一致
                            bool jIsGood = (mask & (1 << j)) != 0;
                            if ((statements[i][j] == 1) != jIsGood) {
                                valid = false;
                                break;
                            }
                        }
                    }
                }
            }
            
            if (valid) {
                maxGood = Math.Max(maxGood, System.Numerics.BitOperations.PopCount((uint)mask));
            }
        }
        
        return maxGood;
    }
}

var maximumGood = function(statements) {
    const n = statements.length;
    let maxGood = 0;
    
    // Try all possible combinations of good/bad people (2^n possibilities)
    for (let mask = 0; mask < (1 << n); mask++) {
        if (isValidAssignment(mask, statements)) {
            maxGood = Math.max(maxGood, countBits(mask));
        }
    }
    
    return maxGood;
};

function isValidAssignment(mask, statements) {
    const n = statements.length;
    
    // Check each person's statements
    for (let i = 0; i < n; i++) {
        // If person i is good (bit is set), their statements must be true
        if (mask & (1 << i)) {
            for (let j = 0; j < n; j++) {
                if (statements[i][j] !== 2) {
                    const jIsGood = (mask & (1 << j)) !== 0;
                    const statementSaysGood = statements[i][j] === 1;
                    
                    // Good person's statement must match reality
                    if (jIsGood !== statementSaysGood) {
                        return false;
                    }
                }
            }
        }
    }
    
    return true;
}

function countBits(mask) {
    let count = 0;
    while (mask > 0) {
        count += mask & 1;
        mask >>= 1;
    }
    return count;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数值说明
时间复杂度O(n² × 2^n)需要枚举 2^n 种状态，对每种状态需要验证 n² 个陈述
空间复杂度O(1)只使用常数额外空间

相关题目