/
_861.java
executable file
·67 lines (59 loc) · 1.85 KB
/
_861.java
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
64
65
66
67
package com.hit.basmath.learn.others;
/**
* 861. Score After Flipping Matrix
* <p>
* We have a two dimensional matrix A where each value is 0 or 1.
* <p>
* A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.
* <p>
* After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.
* <p>
* Return the highest possible score.
* <p>
* Example 1:
* <p>
* Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
* Output: 39
* Explanation:
* Toggled to [[1,1,1,1],[1,0,0,1],[1,1,1,1]].
* 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39
* <p>
* Note:
* <p>
* 1 <= A.length <= 20
* 1 <= A[0].length <= 20
* A[i][j] is 0 or 1.
*/
public class _861 {
public int matrixScore(int[][] A) {
int N = A.length,
M = A[0].length;
// Optimize, step1: flip all rows starting with a zero
for (int i = 0; i < N; ++i) {
if (A[i][0] == 0)
flipRow(A, i);
}
// Optimize, step 2: flip all columns where the number of zeros is larger than the number of ones
for (int col = 1; col < M; ++col) {
int sumCol = 0;
for (int i = 0; i < N; ++i)
sumCol += A[i][col];
if (sumCol * 2 < N)
flipCol(A, col);
}
// Count final sum
int total = 0;
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
total += A[i][j] * (1 << (M - j - 1));
return total;
}
private void flipRow(int[][] a, int r) {
for (int i = 0; i < a[r].length; ++i)
a[r][i] = (a[r][i] ^ 1);
}
private void flipCol(int[][] a, int c) {
for (int i = 0; i < a.length; ++i)
a[i][c] = (a[i][c] ^ 1);
}
}