leetcode讲解--861. Score After Flipping Matrix

题目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 = 39Note:1 <= A.length <= 201 <= A[0].length <= 20A[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); } }}