leetcode在力扣 App 中打开
调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

游戏中存在两种角色:

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

给你一个下标从 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] 的值为 012
  • statements[i][i] == 2
通过次数
6.7K
提交次数
13K
通过率
52.0%


相关企业

提示 1
You should test every possible assignment of good and bad people, using a bitmask.

提示 2
In each bitmask, if the person i is good, then his statements should be consistent with the bitmask in order for the assignment to be valid.

提示 3
If the assignment is valid, count how many people are good and keep track of the maximum.

相似题目

评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
statements =
[[2,1,2],[1,2,2],[2,0,2]]
Source