LeetCode/861. 翻转矩阵后的得分

861. 翻转矩阵后的得分

有一个二维矩阵 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. 1 <= A.length <= 20
2. 1 <= A[0].length <= 20
3. A[i][j] 是 0 或 1

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题其实想到的了非常简单，我们要保证每一行构成的二进制数最大，并且可以翻转行和列，那么肯定要将最高位变成一，这样才能保证这个数是所有组合中最大的。然后判断每一列，需要知道每列中1的个数多还是0的个数多，如果1多就不翻转，如果0多就翻转，即取两者出现次数较大的。最后，我们不需要改变原数组就可以计算所有最大数之和，具体来说，已经将最开始的位置变为了1，那么result就是$m \times 2 ^{n - 1}$，其中m为行数，n为列数，然后计算每一列的情况，结果为$k \times 2^{n - i -1}$，其中k为0和1较大出现的次数，i为当前列数索引。这里需要注意一点，就是处理每一列时，需要首先判断该行第一个元素是否为1，也就是判断该行是否进行了翻转，如果翻转，情况就会是1 - A[j][i]，即相反情况。

具体代码如下：

class Solution {
    public int matrixScore(int[][] A) {
        int m = A.length;
        int n = A[0].length;
        //假定每行首都为1
        int result = m * (1 << (n - 1));

        for (int i = 1; i < n; i++) {
            int count = 0;
            for (int j = 0; j < m; j++) {
                //如果行首没有进行翻转，直接加上原本的数字即可
                if (A[j][0] == 1) {
                    count += A[j][i];
                } else { //如果行首进行了翻转，要加上当前数字的相反数，即原先为0现在为1
                    count += (1 - A[j][i]);
                }
            }
            int k = Math.max(count, m - count);
            result = result + k * (1 << (n - i - 1));
        }
        return result;
    }
}