被列覆盖的最多行数

标签: 位运算 数组 回溯 枚举 矩阵

难度: Medium

给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix ；另给你一个整数 numSelect，表示你必须从 matrix 中选择的 不同 列的数量。

如果一行中所有的 1 都被你选中的列所覆盖，则认为这一行被 覆盖 了。

形式上，假设 s = {c1, c2, ...., cnumSelect} 是你选择的列的集合。对于矩阵中的某一行 row ，如果满足下述条件，则认为这一行被集合 s 覆盖：

  • 对于满足 matrix[row][col] == 1 的每个单元格 matrix[row][col]（0 <= col <= n - 1），col 均存在于 s 中，或者
  • row 中 不存在 值为 1 的单元格。

你需要从矩阵中选出 numSelect 个列，使集合覆盖的行数最大化。

返回一个整数，表示可以由 numSelect 列构成的集合 覆盖 的 最大行数 。

示例 1：

输入：matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2
输出：3
解释：
图示中显示了一种覆盖 3 行的可行办法。
选择 s = {0, 2} 。
- 第 0 行被覆盖，因为其中没有出现 1 。
- 第 1 行被覆盖，因为值为 1 的两列（即 0 和 2）均存在于 s 中。
- 第 2 行未被覆盖，因为 matrix[2][1] == 1 但是 1 未存在于 s 中。
- 第 3 行被覆盖，因为 matrix[2][2] == 1 且 2 存在于 s 中。
因此，可以覆盖 3 行。
另外 s = {1, 2} 也可以覆盖 3 行，但可以证明无法覆盖更多行。

示例 2：

输入：matrix = [[1],[0]], numSelect = 1
输出：2
解释：
选择唯一的一列，两行都被覆盖了，因为整个矩阵都被覆盖了。
所以我们返回 2 。

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 12
  • matrix[i][j] 要么是 0 要么是 1
  • 1 <= numSelect <= n

Submission

运行时间: 24 ms

内存: 16.7 MB

class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        rows = []
        for row in matrix:
            mask = reduce(or_, (1 << j for j, x in enumerate(row) if x), 0)
            rows.append(mask)

        ans = 0
        for mask in range(1 << len(matrix[0])):
            if mask.bit_count() != numSelect:
                continue
            t = sum((x & mask) == x for x in rows)
            ans = max(ans, t)
        return ans

Explain

此题解使用了位运算和掩码的概念来解决问题。首先，将每行的1所在的列位置转换为二进制数的掩码，例如行[1,0,1]转换为掩码5（101 in binary）。之后，生成所有可能的列组合掩码，并检查每个组合是否由精确的'numSelect'位1。对于每个有效的列掩码，计算有多少行可以完全被这些列覆盖，即行掩码和列掩码的与操作结果等于行掩码本身。最后，找到可以覆盖最多行的列组合，并返回覆盖行数。

时间复杂度: O(m * 2^n)

空间复杂度: O(m)

class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        rows = []
        # 为每行生成一个掩码
        for row in matrix:
            # 使用位运算创建掩码，标记1的位置
            mask = reduce(or_, (1 << j for j, x in enumerate(row) if x), 0)
            rows.append(mask)

        ans = 0
        # 遍历所有可能的列组合掩码
        for mask in range(1 << len(matrix[0])):
            # 确保掩码中有numSelect个1
            if mask.bit_count() != numSelect:
                continue
            # 计算有多少行被当前掩码覆盖
            t = sum((x & mask) == x for x in rows)
            # 更新最大覆盖行数
            ans = max(ans, t)
        return ans

Explore

在题解中，为了确保生成的列掩码包含恰好numSelect个1，使用了二进制数的`bit_count()`方法。这个方法计算一个整数（在此场景中，是列掩码）的二进制表示中1的数量。在遍历所有可能的列掩码时，通过检查每个掩码的`bit_count()`是否等于numSelect来筛选出符合条件的掩码。这样，只有那些恰好包含numSelect个1的掩码会被进一步用于计算覆盖行数。

题解中选择使用位掩码来表示列的组合主要因为位运算提供了一种高效的方式来处理集合并、交和测试等操作。与数组或列表相比，位掩码能够更快地进行并集和交集操作，且在空间复杂度上也更为优越，尤其是在处理大量数据时。此外，位掩码使得检查和修改集合中元素的状态变得简单且快速，这对于算法中需要频繁进行这类操作的情况非常适合。

在计算行被覆盖的情况时，行掩码和列掩码进行与操作的结果如果等于行掩码本身，意味着列掩码中包含了行掩码中所有标记为1的位。这表示选定的列完全覆盖了该行中所有为1的列。因此，这个条件被用来检查一个给定的列组合（表示为列掩码）是否能够完全覆盖某一行。如果所有需要的列都被选中，那么与操作的结果就会与行掩码一致，从而确认该行被完全覆盖。

在算法中，空行（即所有元素都为0的行）的掩码值将为0。当计算一个空行是否被某个列掩码覆盖时，由于0与任何数的与操作结果仍为0，这意味着任何列掩码都会被视为覆盖了空行。因此，在统计覆盖行数时，空行总是被计算在内，而不需要特别的处理。这简化了算法的实现，同时确保了算法的正确性，因为空行确实无需任何特定列即可被视作“被覆盖”。