LeetCode 题解工作台
基于陈述统计最多好人数
游戏中存在两种角色： 好人 ：该角色只说真话。 坏人 ：该角色可能说真话，也可能说假话。 给你一个下标从 0 开始的二维整数数组 statements ，大小为 n x n ，表示 n 个玩家对彼此角色的陈述。具体来说， statements[i][j] 可以是下述值之一： 0 表示 i 的陈述认为…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 回溯·pruning
答案摘要
二进制枚举好人的状态 ，由于“好人只说真话”，我们借此判断 与 是否存在矛盾，不存在则获取 中好人的数量 。迭代获取最大的合法 。 时间复杂度 ，其中 表示 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
游戏中存在两种角色：
- 好人：该角色只说真话。
- 坏人：该角色可能说真话，也可能说假话。
给你一个下标从 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
解题思路
方法一：二进制枚举
二进制枚举好人的状态 ，由于“好人只说真话”，我们借此判断 与 是否存在矛盾，不存在则获取 中好人的数量 。迭代获取最大的合法 。
时间复杂度 ，其中 表示 的长度。
class Solution:
def maximumGood(self, statements: List[List[int]]) -> int:
def check(mask: int) -> int:
cnt = 0
for i, row in enumerate(statements):
if mask >> i & 1:
for j, x in enumerate(row):
if x < 2 and (mask >> j & 1) != x:
return 0
cnt += 1
return cnt
return max(check(i) for i in range(1, 1 << len(statements)))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n*2^n) because each of the 2^n assignments requires checking up to n statements. Space complexity is O(n) for recursion and temporary assignment storage. Bitmask usage avoids storing all assignments explicitly. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you recognize this as a backtracking problem with bitmask enumeration?
- question_mark
Can you optimize by pruning assignments that violate statements early?
- question_mark
How do you efficiently count good people in each valid assignment?
常见陷阱
外企场景- error
Failing to validate only statements made by assumed good people.
- error
Not pruning immediately when a contradiction arises, leading to excessive computation.
- error
Confusing the bitmask representation and miscounting good people in final assignments.
进阶变体
外企场景- arrow_right_alt
Allowing statements to include uncertainty beyond 0,1,2, requiring conditional validation.
- arrow_right_alt
Maximizing good people under weighted statements where some statements carry more importance.
- arrow_right_alt
Finding all valid maximum sets of good people rather than just the count.