题目
结果
代码
矩阵的第一列必全为1，而只有行变换才能确保这一点。所以先进行行变换，通过翻转将第一列置1，这一定是行变换的最优解，这样行变换的任务就完成了。
接着是列变换，判断标准是0和1的数目。
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| class Solution {
public int matrixScore(int[][] A) {
for (var row : A) {
if (row[0] == 0) {
reverseRow(row);
}
}
for (int i = 1; i < A[0].length; i++) {
int countOne = 0, countZero = 0;
for (int[] row : A) {
if (row[i] == 0) {
countZero++;
} else {
countOne++;
}
}
if (countZero > countOne) {
reverseCol(A, i);
}
}
return sum(A);
}
private void reverseRow(int[] row) {
for (int i = 0; i < row.length; i++) {
if (row[i] == 0) {
row[i] = 1;
} else {
row[i] = 0;
}
}
}
private void reverseCol(int[][] A, int col) {
for (int i = 0; i < A.length; i++) {
if (A[i][col] == 0) {
A[i][col] = 1;
} else {
A[i][col] = 0;
}
}
}
private int sum(int[][] A) {
int sum = 0;
for (int[] B : A) {
sum += sum(B);
}
return sum;
}
private int sum(int[] A) {
int sum = 0;
for (int num : A) {
sum = sum * 2 + num;
}
return sum;
}
}
|
复杂度
时间复杂度：O（n²）
空间复杂度：O（1）