给你一个大小为 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,则将该行每个元素进行翻转,即 grid[i][j] ^= 1
。
接着,遍历每一列,若该列中 1 的个数小于 0 的个数,则将该列进行翻转。实际过程中,并不需要对列进行翻转,只需要取 max(cnt, m - cnt)
,即表示 1 的个数,再乘上该位的大小 1 << (n - j - 1)
,即求得当前列的大小。累加每一列大小即可。
时间复杂度
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;
}