2397-被列覆盖的最多行数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:06 2023-09-13 17:01:06 Updated    

给你一个下标从 0 开始的 m x n 二进制矩阵 mat 和一个整数 cols ，表示你需要选出的列数。

如果一行中，所有的 1 都被你选中的列所覆盖，那么我们称这一行 被覆盖 了。

请你返回在选择 cols 列的情况下， 被覆盖 的行数 最大 为多少。

示例 1：

**输入：** mat = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], cols = 2
**输出：** 3
**解释：**
如上图所示，覆盖 3 行的一种可行办法是选择第 0 和第 2 列。
可以看出，不存在大于 3 行被覆盖的方案，所以我们返回 3 。

示例 2：

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

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 12
  • mat[i][j] 要么是 0 要么是 1 。
  • 1 <= cols <= n

本题 视频讲解 已出炉，欢迎点赞三连，在评论区分享你对这场双周赛的看法~

由于数据范围很小，我们可以枚举所有大小为 cols 的列编号的集合，对于每个集合，遍历 mat，统计所有 1 被覆盖的行的个数，个数的最大值即为答案。

代码实现时，我们可以用二进制表示集合，二进制的第 i 位为 1 表示 i 在集合中，为 0 表示 i 不在集合中。这样可以用二进制枚举集合，同时把 mat 的每一行也用二进制表示，从而做到 O(1) 判断行中的所有 1 是否被覆盖。

[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def maximumRows(self, mat: List[List[int]], cols: int) -> int:
        ans = 0
        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(mat)]
        for set in range(1 << len(mat[0])):
            if set.bit_count() == cols:  # 集合的大小等于 cols，符合题目要求
                ans = max(ans, sum(row & set == row for row in mask))  # row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖
        return ans
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func maximumRows(mat [][]int, cols int) (ans int) {
	m, n := len(mat), len(mat[0])
	mask := make([]int, m)
	for i, row := range mat {
		for j, v := range row {
			mask[i] |= v << j
		}
	}
	for set := 0; set < 1<<n; set++ {
		if bits.OnesCount(uint(set)) != cols { // 跳过大小不等于 cols 的集合
			continue
		}
		cnt := 0
		for _, row := range mask {
			if row&set == row { // row 是 set 的子集，所有 1 都被覆盖
				cnt++
			}
		}
		ans = max(ans, cnt)
	}
	return
}

func max(a, b int) int { if b > a { return b }; return a }

上面的代码有很多无效枚举，即大小不等于 cols 的集合，如何优化呢？

通过使用 Gosper’s Hack，我们可以在 O(1) 的时间内找到下一个大小为 cols 的集合。

视频讲解 中介绍了这个算法。

复杂度分析

  • 时间复杂度：O(m\cdot C_{n}^{\textit{cols} })。其中 m 为 mat 的行数，n 为 mat 的列数。
  • 空间复杂度：O(m)。
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maximumRows(self, mat: List[List[int]], cols: int) -> int:
        ans = 0
        mask = [sum(v << j for j, v in enumerate(row)) for i, row in enumerate(mat)]
        set = (1 << cols) - 1
        while set < 1 << len(mat[0]):
            ans = max(ans, sum(row & set == row for row in mask))  # row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖
            lb = set & -set
            x = set + lb
            set = (set ^ x) // lb >> 2 | x
        return ans
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func maximumRows(mat [][]int, cols int) (ans int) {
	m, n := len(mat), len(mat[0])
	mask := make([]int, m)
	for i, row := range mat {
		for j, v := range row {
			mask[i] |= v << j
		}
	}
	for set := 1<<cols - 1; set < 1<<n; {
		cnt := 0
		for _, row := range mask {
			if row&set == row { // row 是 set 的子集，所有 1 都被覆盖
				cnt++
			}
		}
		ans = max(ans, cnt)
		lb := set & -set
		x := set + lb
		// 下式等价于 set = (set^x)/lb>>2 | x
		set = (set^x)>>bits.TrailingZeros(uint(lb))>>2 | x
	}
	return
}

func max(a, b int) int { if b > a { return b }; return a }
 Comments
On this page
2397-被列覆盖的最多行数