1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
public int maximumRows(int[][] matrix, int numSelect) {
List<Integer> nums = new ArrayList<>();
this.collectAllCombinations(0, numSelect, matrix[0].length, 0, 0, nums);
List<Integer> rowBits = this.arrayRow2Bit(matrix);
int ans = 0;
for (Integer num : nums) {
int count = 0;
for (Integer rowBit : rowBits) {
if ((num | rowBit) == num) {
count++;
}
}
ans = Math.max(ans, count);
}
return ans;
}
private List<Integer> arrayRow2Bit(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int m = matrix.length;
int n = matrix[0].length;
for (int i = 0; i < m; i++) {
int num = 0;
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 1) {
num |= 1 << j;
}
}
ans.add(num);
}
return ans;
}
private void collectAllCombinations(int start, int size, int n, int bitNum, int num, List<Integer> nums) {
if (bitNum == size) {
nums.add(num);
return;
}
for (int i = start; i < n; i++) {
int numCopy = num;
bitNum++;
num |= 1 << i;
this.collectAllCombinations(i + 1, size, n, bitNum, num, nums);
bitNum--;
num = numCopy;
}
}
}
|
