Question

861. 翻转矩阵后的得分

English Version

题目描述

给你一个大小为 m x n 的二元矩阵 grid ，矩阵中每个元素的值为 0 或 1 。

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

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

在执行任意次 移动 后（含 0 次），返回可能的最高分数。

 

示例 1：

输入：grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
输出：39
解释：0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

示例 2：

输入：grid = [[0]]
输出：1

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 20
• grid[i][j] 为 0 或 1

解法

方法一：贪心

我们注意到，对于任意一个翻转方案，翻转的次序不影响最后的结果。因此我们可以先考虑所有的行翻转，再考虑所有的列翻转。

每一行的数字要尽可能大，因此，我们遍历每一行，若行首元素为 $0$，则将该行进行翻转。

接下来，对于每一列 $j$，我们统计该列中 $0$ 和 $1$ 的数量，令 $cnt$ 为其中的最大值，则该列的贡献为 $cnt \times 2^{n - j - 1}$。对所有列的贡献进行累加，即可得到答案。

时间复杂度 $O(m \times n)$，空间复杂度 $O(1)$。其中 $m$, $n$ 分别为矩阵的行数和列数。

class Solution:
  def matrixScore(self, grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    for i in range(m):
      if grid[i][0] == 0:
        for j in range(n):
          grid[i][j] ^= 1
    ans = 0
    for j in range(n):
      cnt = sum(grid[i][j] for i in range(m))
      ans += max(cnt, m - cnt) * (1 << (n - j - 1))
    return ans

class Solution {
  public int matrixScore(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; ++i) {
      if (grid[i][0] == 0) {
        for (int j = 0; j < n; ++j) {
          grid[i][j] ^= 1;
        }
      }
    }
    int ans = 0;
    for (int j = 0; j < n; ++j) {
      int cnt = 0;
      for (int i = 0; i < m; ++i) {
        cnt += grid[i][j];
      }
      ans += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
    }
    return ans;
  }
}

class Solution {
public:
  int matrixScore(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    for (int i = 0; i < m; ++i) {
      if (grid[i][0] == 0) {
        for (int j = 0; j < n; ++j) {
          grid[i][j] ^= 1;
        }
      }
    }
    int ans = 0;
    for (int j = 0; j < n; ++j) {
      int cnt = 0;
      for (int i = 0; i < m; ++i) {
        cnt += grid[i][j];
      }
      ans += max(cnt, m - cnt) * (1 << (n - j - 1));
    }
    return ans;
  }
};

func matrixScore(grid [][]int) int {
  m, n := len(grid), len(grid[0])
  for i := 0; i < m; i++ {
    if grid[i][0] == 0 {
      for j := 0; j < n; j++ {
        grid[i][j] ^= 1
      }
    }
  }
  ans := 0
  for j := 0; j < n; j++ {
    cnt := 0
    for i := 0; i < m; i++ {
      cnt += grid[i][j]
    }
    if cnt < m-cnt {
      cnt = m - cnt
    }
    ans += cnt * (1 << (n - j - 1))
  }
  return ans
}

function matrixScore(grid: number[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  for (let i = 0; i < m; ++i) {
    if (grid[i][0] == 0) {
      for (let j = 0; j < n; ++j) {
        grid[i][j] ^= 1;
      }
    }
  }
  let ans = 0;
  for (let j = 0; j < n; ++j) {
    let cnt = 0;
    for (let i = 0; i < m; ++i) {
      cnt += grid[i][j];
    }
    ans += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
  }
  return ans;
}

public class Solution {
  public int MatrixScore(int[][] grid) {
    int m = grid.Length, n = grid[0].Length;
    for (int i = 0; i < m; ++i) {
      if (grid[i][0] == 0) {
        for (int j = 0; j < n; ++j) {
          grid[i][j] ^= 1;
        }
      }
    }
    int ans = 0;
    for (int j = 0; j < n; ++j) {
      int cnt = 0;
      for (int i = 0; i < m; ++i) {
        if (grid[i][j] == 1) {
          ++cnt;
        }
      }
      ans += Math.Max(cnt, m - cnt) * (1 << (n - j - 1));
    }
    return ans;
  }
}