LeetCode中翻转矩阵后的得分题解-java

题目

861. 翻转矩阵后的得分

难度中等164

有一个二维矩阵 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

题解

思路

题目要求每行表示的数的和最大，那么我们很容易就想到可以让每行表示的数尽可能的大。由于每行为一个二进制数，那么我们肯定希望所有位置都尽可能为 1，尤其是数字的高位，最好就是 1。我们通过观察样例发现，每行的第一个数字都为 1。我们想下，的确不论如何翻转，第一列全为 1的结果一定大于其它任何结果的。所以我们先把最高位为 0 的行翻转，并且那些最高位为 1 的是不能行翻转的。对于样例 1，进行如下的变换：

0011
1010
1100

变为

1100
1010
1100

（只有第一行操作了行翻转）
好的，我们再去考虑列翻转。对于每列，我们肯定希望 1 越多越好，因为每个 1 都会让那行的数字更大。那么统计每列中 0 和 1 的个数，如果 0 多就列翻转，否则不列翻转。对于样例 1，变换继续：

1100
1010
1100

变为

1111
1011
1111

（第三列第四列操作了列翻转）
然后这题就结束了（贪心完了）。

代码实现
直接按上述思路实现即可。如果追求短代码更高效率，2 个 O(n^2) 的循环是可以合并起来的，不需要行翻转直接统计每列的 0 或 1 个数，方法就是如果 A[i][0] 为 0，A[i][j] 的值翻转一下，具体写法可以自己尝试一下。

class Solution {
  public int matrixScore(int[][] A) {
    int m = A.length, n = A[0].length;
    int result = 0;
    for (int i = 0; i < m; i++) {
      // 如果第 i 行以 0 开头
      if (A[i][0] == 0) {
        // 行翻转
        for (int j = 0; j < n; j++) {
          A[i][j] ^= 1;
        }
      }
    }
    for (int j = 0; j < n; j++) {
      int cnt = 0;
      // 统计第 j 列有多少个 1。
      for (int i = 0; i < m; i++) {
        cnt += A[i][j];
      }
      // max(cnt, m - cnt) 表示这个位置最多有多少个 1。 1<<(n-j-1) 表示这个位置的1的大小。
      result += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
    }
    return result;
  }
}