共计 1552 个字符，预计需要花费 4 分钟才能阅读完成。
题目
We have a two dimensional matrix A where each value is 0 or 1.
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.
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.
Return the highest possible score.
Example 1:
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
Note:
1 <= A.length <= 20
1 <= A[0].length <= 20
A[i][j] is 0 or 1.
题目地址
讲解
这道题我刚开始没看懂，我先入为主以为 0 和 1 的总数是不变的，你把多少个 0 变成 1，就要把其他的相应个数的 1 变为 0。后来看懂了，flip 可以是行或者列，每个 flip 操作把该行或者列的所有 0 变成 1，所有 1 变成 0。然后每行看做一个二进制数，把所有行加起来作为返回结果。问怎么翻转结果才最大？
看懂题目之后，我们来想一下，二进制数有个特点，第一个数比其他数加起来还重要，意思是比如：1000 比 0111 还大。所以我们要让第一位变成 1，不惜任何代价，哪怕其他三位全都因此变成 0。
第二步，我们要在保证第一步，也就是所有行首为 1 的前提下，再次优化。那么我就想到，按列进行优化，如果这一列的 0 比 1 多，就 flip 一下。
Java 代码
class Solution {
public int matrixScore(int[][] A) {
for(int i=0;i<A.length;i++){
if(A[i][0]!=1){
flip(A[i]);
}
}
for(int i=0;i<A[0].length;i++){
dealColumn(A, i);
}
int result=0;
for(int i=0;i<A.length;i++){
int column=0;
for(int j=0;j<A[0].length;j++){
System.out.print(A[i][j]);
column <<= 1;
if(A[i][j]==1){
column += A[i][j];
}
}
System.out.println(“\n”);
result += column;
}
return result;
}
private void flip(int[] A){
for(int i=0;i<A.length;i++){
if(A[i]==0){
A[i] = 1;
}else{
A[i] = 0;
}
}
}
private void flipColumn(int[][] A, int columnNum){
for(int i=0;i<A.length;i++){
if(A[i][columnNum]==0){
A[i][columnNum]=1;
}else{
A[i][columnNum]=0;
}
}
}
private void dealColumn(int[][] A, int columnNum){
int count=0;
for(int i=0;i<A.length;i++){
if(A[i][columnNum]==0){
count++;
}
}
if(count>A.length/2){
flipColumn(A, columnNum);
}
}
}
