博客

有一个二维矩阵 A 其中每个元素的值为 0 或 1 。

移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。

在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。

返回尽可能高的分数。

示例：

输入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]

输出：39

解释：

转换为 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]

0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

提示：

1 <= A.length <= 20

1 <= A[0].length <= 20

A[i][j] 是 0 或 1

思路：


1000>0111,所以先把所有第一列不是1的行进行行反转。然后再判断各列是否需要翻转。反转的策略是这一列0的数是否大于列数的一半，若大于一半，就要翻转。

public int matrixScore(int[][] A) {
		 int l1 = A.length;
		 int l2 = A[0].length;
		 
		 //先根据第一列是否为0进行横向翻转
		 for(int i=0;i<l1;i++) {
			 if(A[i][0]==0) {
				 for(int j=0;j<l2;j++)
					 A[i][j] = A[i][j]==0?1:0;
			 }
		 }
		 
		 //列反转
		 for(int j=1;j<l2;j++) {
			 if(check(A,j)) {
				 for(int i=0;i<l1;i++)
					 A[i][j]=A[i][j]==0?1:0;
			 }
		 }
		 
		 int sum = 0;
		 for(int i=0;i<l1;i++)
			 for(int j=0;j<l2;j++) {
				 sum += A[i][j]* Math.pow(2, l2-j-1);
			 }
		 return sum;
	 }
	 
	 //判断纵向是否需要翻转
	 public  boolean check(int[][] A,int j) {
		 int just = A.length/2;
		 int l1 = A.length;
		 int n = 0;

		 for(int i=0;i<l1;i++) {
			if(A[i][j]==0)
				 n++;
			if(n>just)
				return true;
		 }
		 return false;
	 }