LeetCode 861. 翻转矩阵后的得分

Categories:

题目描述
思路分析
1. 解法一：贪心（推荐）
相似题目

题目描述

✅ 861. 翻转矩阵后的得分

思路分析

解法一：贪心（推荐）

核心思路：

每一行代表一个二进制数，最高位（最左列）权重最大，首先保证每行最高位为 1：若某行最高位为 0，翻转该行

处理完行翻转后，对每一列，统计该列中 1 的数量，若 0 的数量更多（即 1 的数量 < 行数/2），则翻转该列

对于某列 j，若第 0 列与第 j 列相同，则 grid[i][j] 的当前值等于 grid[i][0] XOR grid[i][j]（经过行翻转后等效为 1 XOR grid[i][j]），即翻转后的结果

可以不实际修改矩阵，通过数学推导直接计算最终得分

复杂度分析：

时间复杂度：O(m × n)，其中 m 为行数，n 为列数

空间复杂度：O(1)，原地计算，不使用额外空间

class Solution {
  public int matrixScore(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;

    // 第一步：确保每行最高位为 1（若最高位为 0 则翻转该行）
    for (int i = 0; i < m; i++) {
      if (grid[i][0] == 0) {
        for (int j = 0; j < n; j++) {
          grid[i][j] ^= 1;
        }
      }
    }

    // 第二步：对每列（除第一列），若 0 的数量更多则翻转该列
    int score = 0;
    for (int j = 0; j < n; j++) {
      int ones = 0;
      for (int i = 0; i < m; i++) {
        ones += grid[i][j];
      }
      // 取该列中 1 的最大数量
      score += Math.max(ones, m - ones) * (1 << (n - 1 - j));
    }

    return score;
  }
}

func matrixScore(grid [][]int) int {
    m := len(grid)
    n := len(grid[0])

    // 第一步：确保每行最高位为 1
    for i := 0; i < m; i++ {
        if grid[i][0] == 0 {
            for j := 0; j < n; j++ {
                grid[i][j] ^= 1
            }
        }
    }

    // 第二步：对每列取最多 1 的方案累加得分
    score := 0
    for j := 0; j < n; j++ {
        ones := 0
        for i := 0; i < m; i++ {
            ones += grid[i][j]
        }
        // 该列贡献 = max(ones, zeros) * 列权重
        if ones < m-ones {
            ones = m - ones
        }
        score += ones * (1 << (n - 1 - j))
    }

    return score
}

相似题目

题目	难度	考察点
1284. 转化为全零矩阵的最少翻转次数	困难	位运算、BFS
1529. 灯泡开关 IV	中等	贪心
421. 数组中两个数的最大异或值	中等	位运算、字典树
78. 子集	中等	位运算、回溯
136. 只出现一次的数字	简单	位运算
338. 比特位计数	简单	位运算、动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/12114884