public class Solution {
public int maximumRows(int[][] mat, int numSelect) {
int m = mat.length, n = mat[0].length;
int[] mask = new int[m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
mask[i] |= mat[i][j] << j;
}
}
int ans = 0;
int subset = (1 << numSelect) - 1;
while (subset < (1 << n)) {
int coveredRows = 0;
for (int row : mask) {
if ((row & subset) == row) {
coveredRows++;
}
}
ans = Math.max(ans, coveredRows);
int lb = subset & -subset;
int x = subset + lb;
subset = ((subset ^ x) / lb >> 2) | x;
}
return ans;
}
}
class Solution {
public int maximumRows(int[][] mat, int cols) {
int m = mat.length;
int n = mat[0].length;
int state = 1 << n;
int[] arr = new int[m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] == 1) {
arr[i] ^= (1 << j);
}
}
}
int res = 0;
for (int i = 0; i < state; i++) {
if (Integer.bitCount(i) == cols) {
// System.out.println("状态：" + Integer.toBinaryString(i));
int count = 0;
for (int x : arr) {
if ((((~i) & x) << (32 - n)) == 0) {
count++;
}
}
res = Math.max(res, count);
}
}
return res;
}
}
// 把每一行转换为一个int数，遍历2^(列) - 1个列
// 如果列数的1的个数为cols，统计 (列数 & 行) == 行的所有行的总数，并更新ret
class Solution {
public:
int maximumRows(vector<vector<int>>& mat, int cols) {
int n = mat.size(), m = mat[0].size();
vector<int> row_int(n);
for (int i = 0; i < n; i ++) {
int num = 0;
for (int j = 0; j < m; j ++) {
num *= 2;
num += mat[i][j];
}
row_int[i] = num;
}
// for (int i = 0; i < n; i ++)
// cout << row_int[i] << " ";
int now = 1, ret = 0, cnt = 0;
while (now < (1 << m)) {
if (__builtin_popcount(now) == cols) {
for (int i = 0; i < n; i ++)
// 这里一定要注意 C++ &的优先级低于 == 下面的括号不能省略
if ((row_int[i] & now) == row_int[i]) cnt ++;
ret = max(ret, cnt);
cnt = 0;
}
now ++;
}
return ret;
}
};
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]):
# row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖
ans = max(ans, sum(row & set == row for row in mask))
lb = set & -set
x = set + lb
set = (set ^ x) // lb >> 2 | x
return ans
// gopher's hack
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 }
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 的列编号的集合，
对于每个集合，遍历 mat，统计所有 1 被覆盖的行的个数，个数的最大值即为答案。
代码实现时，我们可以用二进制表示集合，二进制的第 i 位为 1 表示 i 在集合中，
为 0 表示 i 不在集合中。这样可以用二进制枚举集合，同时把 mat 的每一行也用二进制表示，
从而做到 O(1) 判断行中的所有 1 是否被覆盖。
'''
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])):
# 集合的大小等于 cols，符合题目要求
if set.bit_count() == cols:
# row & set = row 表示 row 是 set 的子集，所有 1 都被覆盖
ans = max(ans, sum(row & set == row for row in mask))
return ans
