LeetCode 题解工作台
被列覆盖的最多行数
给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix ；另给你一个整数 numSelect ，表示你必须从 matrix 中选择的 不同 列的数量。 如果一行中所有的 1 都被你选中的列所覆盖，则认为这一行被 覆盖 了。 形式上 ，假设 s = {c 1 , c 2 , ....…
5
题型
5
代码语言
3
相关题
当前训练重点
中等 · 回溯·pruning
答案摘要
我们先将矩阵中的每一行转换成一个二进制数，记录在数组 中，其中 表示第 行对应的二进制数，而 这个二进制数的第 位表示第 行第 列的值。 接下来，我们枚举所有的 种列选择方案，其中 为矩阵的列数。对于每一种列选择方案，我们判断是否选中了 `numSelect` 列，如果不是，则跳过。否则，我们统计矩阵中有多少行中的所有 都被选中的列覆盖，即统计有多少行的二进制数 与列选择方案…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 回溯·pruning 题型思路
题目描述
给你一个下标从 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.lengthn == matrix[i].length1 <= m, n <= 12matrix[i][j]要么是0要么是11 <= numSelect <= n
解题思路
方法一：二进制枚举
我们先将矩阵中的每一行转换成一个二进制数，记录在数组 中，其中 表示第 行对应的二进制数，而 这个二进制数的第 位表示第 行第 列的值。
接下来，我们枚举所有的 种列选择方案，其中 为矩阵的列数。对于每一种列选择方案，我们判断是否选中了 numSelect 列，如果不是，则跳过。否则，我们统计矩阵中有多少行中的所有 都被选中的列覆盖，即统计有多少行的二进制数 与列选择方案 按位与的结果等于 ，并更新最大的行数。
时间复杂度 ，空间复杂度 。其中 和 分别为矩阵的行数和列数。
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
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(C(n, numSelect) * m) due to generating combinations of columns and checking all rows. Space complexity is O(m) for storing bitmasks and recursion stack usage during backtracking. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if you understand recursive backtracking with pruning.
- question_mark
Tests efficient row coverage checks using bit manipulation.
- question_mark
Wants candidates to reason about combinatorial limits and avoid unnecessary computation.
常见陷阱
外企场景- error
Not handling rows with all zeros correctly, which are automatically covered.
- error
Inefficiently checking row coverage without bitmasking, causing timeouts.
- error
Failing to prune column combinations that cannot improve the current maximum.
进阶变体
外企场景- arrow_right_alt
Maximize rows covered when selecting up to numSelect columns instead of exactly.
- arrow_right_alt
Find the minimum number of columns needed to cover all rows.
- arrow_right_alt
Optimize coverage when matrix dimensions are larger and require advanced pruning.