合肥市网站建设 小程序,万网域名注册流程,设计制作活动主题,公司网络维护主要做什么LeetCode每日一题
2397.被列覆盖的最多行数
2397. 被列覆盖的最多行数 - 力扣#xff08;LeetCode#xff09;
题目描述
给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix #xff1b;另给你一个整数 numSelect#xff0c;表示你必须从 matrix 中选择的 不同 …LeetCode每日一题
2397.被列覆盖的最多行数
2397. 被列覆盖的最多行数 - 力扣LeetCode
题目描述
给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix 另给你一个整数 numSelect表示你必须从 matrix 中选择的 不同 列的数量。
如果一行中所有的 1 都被你选中的列所覆盖则认为这一行被 覆盖 了。
形式上假设 s {c1, c2, ...., cnumSelect} 是你选择的列的集合。对于矩阵中的某一行 row 如果满足下述条件则认为这一行被集合 s 覆盖
对于满足 matrix[row][col] 1 的每个单元格 matrix[row][col]0 col n - 1col 均存在于 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
思路
算法小白的我看不懂题,使用cv大法
代码
C
class Solution {
public:int maximumRows(vectorvectorint matrix, int numSelect) {int m matrix.size();int n matrix[0].size();vectorint mask(m, 0);for (int i 0; i m; i) {for (int j 0; j n; j){mask[i] matrix[i][j] (n - j - 1);}}int res 0;int cur 0;int limit (1 n);while ((cur) limit) {if (__builtin_popcount(cur) ! numSelect) {continue;}int t 0;for (int j 0; j m; j) {if ((mask[j] cur) mask[j]) {t;}}res max(res, t);}return res;}
};Java
class Solution {public int maximumRows(int[][] matrix, int numSelect) {int m matrix.length;int n matrix[0].length;int[] mask new int[m];for (int i 0; i m; i) {for (int j 0; j n; j){mask[i] matrix[i][j] (n - j - 1);}}int res 0;int cur 0;int limit (1 n);while (cur limit) {if (Integer.bitCount(cur) ! numSelect) {continue;}int t 0;for (int j 0; j m; j) {if ((mask[j] cur) mask[j]) {t;}}res Math.max(res, t);}return res;}
}
