返回介绍

solution / 2100-2199 / 2151.Maximum Good People Based on Statements / README

发布于 2024-06-17 01:03:09 字数 6196 浏览 0 评论 0 收藏 0

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

English Version

题目描述

游戏中存在两种角色:

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

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

解法

方法一:二进制枚举

二进制枚举好人的状态 $mask$,由于“好人只说真话”,我们借此判断 $statements$ 与 $mask$ 是否存在矛盾,不存在则获取 $mask$ 中好人的数量 $cnt$。迭代获取最大的合法 $cnt$。

时间复杂度 $O(2^n*n^2)$,其中 $n$ 表示 $statements$ 的长度。

class Solution:
  def maximumGood(self, statements: List[List[int]]) -> int:
    def check(mask):
      cnt = 0
      for i, s in enumerate(statements):
        if (mask >> i) & 1:
          for j, v in enumerate(s):
            if v < 2 and ((mask >> j) & 1) != v:
              return 0
          cnt += 1
      return cnt

    return max(check(mask) for mask in range(1, 1 << len(statements)))
class Solution {
  public int maximumGood(int[][] statements) {
    int ans = 0;
    for (int mask = 1; mask < 1 << statements.length; ++mask) {
      ans = Math.max(ans, check(mask, statements));
    }
    return ans;
  }

  private int check(int mask, int[][] statements) {
    int cnt = 0;
    int n = statements.length;
    for (int i = 0; i < n; ++i) {
      if (((mask >> i) & 1) == 1) {
        for (int j = 0; j < n; ++j) {
          int v = statements[i][j];
          if (v < 2 && ((mask >> j) & 1) != v) {
            return 0;
          }
        }
        ++cnt;
      }
    }
    return cnt;
  }
}
class Solution {
public:
  int maximumGood(vector<vector<int>>& statements) {
    int ans = 0;
    for (int mask = 1; mask < 1 << statements.size(); ++mask) ans = max(ans, check(mask, statements));
    return ans;
  }

  int check(int mask, vector<vector<int>>& statements) {
    int cnt = 0;
    int n = statements.size();
    for (int i = 0; i < n; ++i) {
      if ((mask >> i) & 1) {
        for (int j = 0; j < n; ++j) {
          int v = statements[i][j];
          if (v < 2 && ((mask >> j) & 1) != v) return 0;
        }
        ++cnt;
      }
    }
    return cnt;
  }
};
func maximumGood(statements [][]int) int {
  n := len(statements)
  check := func(mask int) int {
    cnt := 0
    for i, s := range statements {
      if ((mask >> i) & 1) == 1 {
        for j, v := range s {
          if v < 2 && ((mask>>j)&1) != v {
            return 0
          }
        }
        cnt++
      }
    }
    return cnt
  }
  ans := 0
  for mask := 1; mask < 1<<n; mask++ {
    ans = max(ans, check(mask))
  }
  return ans
}
function maximumGood(statements: number[][]): number {
  const n = statements.length;
  function check(mask) {
    let cnt = 0;
    for (let i = 0; i < n; ++i) {
      if ((mask >> i) & 1) {
        for (let j = 0; j < n; ++j) {
          const v = statements[i][j];
          if (v < 2 && ((mask >> j) & 1) != v) {
            return 0;
          }
        }
        ++cnt;
      }
    }
    return cnt;
  }
  let ans = 0;
  for (let mask = 1; mask < 1 << n; ++mask) {
    ans = Math.max(ans, check(mask));
  }
  return ans;
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文