LeetCode 2397. 被列覆盖的最多行数：二进制枚举

【LetMeFly】2397.被列覆盖的最多行数：二进制枚举

力扣题目链接：https://leetcode.cn/problems/maximum-rows-covered-by-columns/

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

方法一：二进制枚举

使用二进制枚举每一列“选中与不选”的情况。对于某种选择情况：

首先选择的列的要总数为numSelect。接下来开始遍历每一行。对于某一行：

遍历这一行的每一个元素。如果矩阵中这个元素为1但是没有选择这一行，则此行无效。否则遍历完成时此行累加。

累加合法的行，即为“选择”下的结果。

所有合法选择中的最大结果即为答案。

时间复杂度 $O(2^n\times mn)$ ，其中 $ma t r i x$ 有 $m$ 行 $n$ 列
空间复杂度 $O (1)$

AC代码

C++

class Solution {
public:int maximumRows(vector<vector<int>>& matrix, int numSelect) {int ans = 0;int m = matrix.size(), n = matrix[0].size();for (int state = 0; state < (1 << n); state++) {if (__builtin_popcount(state) != numSelect) {continue;}int thisAns = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] && !(state & (1 << j))) {goto loop;}}thisAns++;loop:;}ans = max(ans, thisAns);}return ans;}
};

Python

# from typing import Listclass Solution:def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:ans = 0m, n = len(matrix), len(matrix[0])for state in range(1 << n):if bin(state).count('1') != numSelect:continuethisAns = 0for i in range(m):can = Truefor j in range(n):if matrix[i][j] and not state & (1 << j):can = FalsebreakthisAns += canans = max(ans, thisAns)return ans