| comments | difficulty | edit_url | rating | source | tags | |||||
|---|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
1718 |
第 86 场双周赛 Q3 |
|
给你一个下标从 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 ansclass Solution {
public int maximumRows(int[][] matrix, int numSelect) {
int m = matrix.length, n = matrix[0].length;
int[] rows = new int[m];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 1) {
rows[i] |= 1 << j;
}
}
}
int ans = 0;
for (int mask = 1; mask < 1 << n; ++mask) {
if (Integer.bitCount(mask) != numSelect) {
continue;
}
int t = 0;
for (int x : rows) {
if ((x & mask) == x) {
++t;
}
}
ans = Math.max(ans, t);
}
return ans;
}
}class Solution {
public:
int maximumRows(vector<vector<int>>& matrix, int numSelect) {
int m = matrix.size(), n = matrix[0].size();
int rows[m];
memset(rows, 0, sizeof(rows));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j]) {
rows[i] |= 1 << j;
}
}
}
int ans = 0;
for (int mask = 1; mask < 1 << n; ++mask) {
if (__builtin_popcount(mask) != numSelect) {
continue;
}
int t = 0;
for (int x : rows) {
t += (x & mask) == x;
}
ans = max(ans, t);
}
return ans;
}
};func maximumRows(matrix [][]int, numSelect int) (ans int) {
m, n := len(matrix), len(matrix[0])
rows := make([]int, m)
for i, row := range matrix {
for j, x := range row {
if x == 1 {
rows[i] |= 1 << j
}
}
}
for mask := 1; mask < 1<<n; mask++ {
if bits.OnesCount(uint(mask)) != numSelect {
continue
}
t := 0
for _, x := range rows {
if (x & mask) == x {
t++
}
}
if ans < t {
ans = t
}
}
return
}function maximumRows(matrix: number[][], numSelect: number): number {
const [m, n] = [matrix.length, matrix[0].length];
const rows: number[] = Array(m).fill(0);
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (matrix[i][j]) {
rows[i] |= 1 << j;
}
}
}
let ans = 0;
for (let mask = 1; mask < 1 << n; ++mask) {
if (bitCount(mask) !== numSelect) {
continue;
}
let t = 0;
for (const x of rows) {
if ((x & mask) === x) {
++t;
}
}
ans = Math.max(ans, t);
}
return ans;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}