题目

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: 39Explanation: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/2){            flipColumn(A, columnNum);        }    }}
    

变种

跟朋友讨论这个题目的时候，他也看错了题，他看成要同时翻转某个元素所在的行和列。那么这么一来题目就变复杂了很多。

首先还是依据一个性质：首位权重最大，所以我们尝试让第一列全1：

哪些情况是翻不出全1的呢？