给你一个下标从?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
?列构成的集合?覆盖?的?最大行数?。
?
class Solution {
public:
int maximumRows(vector<vector<int>>& matrix, int numSelect) {
}
};
由于数据量为1 ~ 12,可见应该是要用指数级的解法,
那么我们不妨考虑暴力回溯,假设矩阵m行n列,从n列中选出numselect列,显然有组合数种选择,那么每次都要计算覆盖的行数,又要m * n次,这样一来时间复杂度为O(2 ^ n * m * n),时间复杂度在1e5到1e6量级左右,应该也可以做,但我们其实可以对每次计算覆盖行数进行优化
由于这是个01矩阵,那么我们可以用一个n位二进制整数表示出一行的状态bit也可以用n位二进制整数表示出当前选择的列数cur,那么bit | cur = cur就说明这是一个覆盖行
时间复杂度: 空间复杂度:O(m)
?
class Solution {
public:
int bits[12] , m , n , ret;
int maximumRows(vector<vector<int>>& matrix, int numSelect) {
memset(bits , 0 , sizeof(bits));
m = matrix.size() , n = matrix[0].size() , ret = 0;
for(int i = 0 ; i < m ; i++)
for(int j = 0 ; j < n ; j++)
if(matrix[i][j])
bits[i] |= (1 << j);
function<void(int , int)> dfs = [&](int x , int cur)
{
if(x == n || __builtin_popcount(cur) == numSelect)
return;
cur |= (1 << x);
int cnt = 0;
for(int i = 0 ; i < m ; i++)
cnt += ((bits[i] | cur) == cur);
ret = max(ret , cnt);
dfs(x + 1 , cur);
cur ^= (1 << x);
dfs(x + 1 , cur);
};
dfs(0 , 0);
return ret;
}
};