Medium

题目描述

给你一个大小为 m x n 的二进制矩阵 grid 。

一次 移动 就是选择任一行或者列，并转换该行或者列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 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

解题思路

这是一道贪心算法题目，关键在于理解二进制数的权重分布。

核心思路：

  1. 最高位优先原则：在二进制表示中，最高位（最左边）的权重最大。对于 n 位二进制数，最高位的权重是 2^(n-1)，而其他所有位的权重之和最多为 2^(n-1)-1。因此，保证最高位为 1 比其他位都重要。

  2. 贪心策略：

    • 第一步：确保每一行的最高位都是 1。如果某行最高位是 0，就翻转这一行
    • 第二步：对于每一列（从第二列开始），统计该列中 1 的个数。如果 0 的个数多于 1 的个数，就翻转这一列

  3. 为什么这样是最优的：

    • 翻转行操作不会影响列之间的相对关系，所以先处理行是安全的
    • 在保证最高位全为 1 的前提下，每一列独立地选择翻转与否，使得该列的 1 尽可能多
    • 由于二进制的权重特性，高位的 1 比低位更重要，所以按列从左到右贪心处理是最优的

算法步骤：

  1. 遍历每一行，如果第一位是 0，翻转整行
  2. 遍历每一列（从第二列开始），统计该列 1 的个数，如果少于一半就翻转该列
  3. 计算最终得分

代码实现

class Solution {
public:
    int matrixScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 确保每行最高位为1
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; j++) {
                    grid[i][j] = 1 - grid[i][j];
                }
            }
        }
        
        // 对每列进行优化
        for (int j = 1; j < n; j++) {
            int count1 = 0;
            for (int i = 0; i < m; i++) {
                count1 += grid[i][j];
            }
            // 如果0的个数多于1的个数，翻转该列
            if (count1 < m - count1) {
                for (int i = 0; i < m; i++) {
                    grid[i][j] = 1 - grid[i][j];
                }
            }
        }
        
        // 计算最终得分
        int result = 0;
        for (int i = 0; i < m; i++) {
            int rowValue = 0;
            for (int j = 0; j < n; j++) {
                rowValue = rowValue * 2 + grid[i][j];
            }
            result += rowValue;
        }
        
        return result;
    }
};

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 确保每行最高位为1
        for i in range(m):
            if grid[i][0] == 0:
                for j in range(n):
                    grid[i][j] = 1 - grid[i][j]
        
        # 对每列进行优化
        for j in range(1, n):
            count1 = sum(grid[i][j] for i in range(m))
            # 如果0的个数多于1的个数，翻转该列
            if count1 < m - count1:
                for i in range(m):
                    grid[i][j] = 1 - grid[i][j]
        
        # 计算最终得分
        result = 0
        for i in range(m):
            row_value = 0
            for j in range(n):
                row_value = row_value * 2 + grid[i][j]
            result += row_value
        
        return result

public class Solution {
    public int MatrixScore(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        // 确保每行最高位为1
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; j++) {
                    grid[i][j] = 1 - grid[i][j];
                }
            }
        }
        
        // 对每列进行优化
        for (int j = 1; j < n; j++) {
            int count1 = 0;
            for (int i = 0; i < m; i++) {
                count1 += grid[i][j];
            }
            // 如果0的个数多于1的个数，翻转该列
            if (count1 < m - count1) {
                for (int i = 0; i < m; i++) {
                    grid[i][j] = 1 - grid[i][j];
                }
            }
        }
        
        // 计算最终得分
        int result = 0;
        for (int i = 0; i < m; i++) {
            int rowValue = 0;
            for (int j = 0; j < n; j++) {
                rowValue = rowValue * 2 + grid[i][j];
            }
            result += rowValue;
        }
        
        return result;
    }
}

var matrixScore = function(grid) {
    const m = grid.length, n = grid[0].length;
    
    // 确保每行最高位为1
    for (let i = 0; i < m; i++) {
        if (grid[i][0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)需要遍历矩阵常数次，每次都是 O(m × n)
空间复杂度O(1)只使用了常数个额外变量，原地修改矩阵

相关题目