LeetCode 861. 翻转矩阵后的得分

约 4 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 矩阵 贪心 位运算

题目描述

✅ 861. 翻转矩阵后的得分

image-20260929105031487

image-20260929105031678

题意分析

每次可以选择整行或整列，把其中的 0、1 互换。将每行从左到右看作高位到低位的二进制数，求任意次操作后所有行数值之和的最大值。同一行或列翻转两次等于不翻，只需考虑最终是否翻转。

解法：位权贪心 + 逻辑翻转

核心思路

[!blue]

第一列的位权是 2^(n - 1)，其余列在同一行中的位权之和只有 2^(n - 1) - 1。若某行最终首位为 0，再翻转这一整行，即使低位全部损失，最高位的收益仍然更多。因此最优结果的每一行首位都必须为 1。

可以约定第一列不做列翻转，再把原首位为 0 的行翻转。这个约定不会缩小最优方案范围：若某个方案翻转了第一列，把它的所有行翻转标记和所有列翻转标记一起取反，相当于每个格子额外翻转两次，最终矩阵不变，而第一列的列翻转已被取消。此时为保证首位为 1，各行的翻转选择就由原首位唯一确定。

行翻转确定后，剩余每列互不影响。设第 j 列在行翻转后有 ones 个 1，不翻列贡献 ones * 2^(n - 1 - j)，翻列则有 m - ones 个 1。只需选择 1 更多的方案，分别最大化每一列的贡献，合起来就是最大总分。

代码不必真的修改矩阵。原首位为 0 时令 rowFlip = 1，否则为 0，用 grid[i][j] ^ rowFlip 得到该格在行翻转后的值。第一列已经全为 1，可以直接计入 m * 2^(n - 1)，其余列再逐个统计。

解题步骤

  1. 将首列全一的贡献计入初始答案。
  2. 逐个处理剩余列，按原首位推算行翻转后的格值。
  3. 比较翻列前后 1 的数量，取较多者。
  4. 乘当前列位权并累加。

某列的 0、1 数量相同，翻或不翻贡献一样。只有一列时，初始化已把全部格子变成 1 对应的得分计入，循环无需执行。

代码实现

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

        int answer = m * (1 << (n - 1));

        for (int j = 1; j < n; j++) {
            int ones = 0;

            for (int i = 0; i < m; i++) {
                // 行翻转由首位决定，同一行所有格子使用相同翻转标记。
                int rowFlip = grid[i][0] == 0 ? 1 : 0;

                ones += grid[i][j] ^ rowFlip;
            }

            // 当前列可翻或不翻，选择一的数量更多的一种。
            int best = Math.max(ones, m - ones);

            answer += best * (1 << (n - 1 - j));
        }

        return answer;
    }
}

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

    answer := m * (1 << (n - 1))
    for j := 1; j < n; j++ {
        ones := 0
        for i := 0; i < m; i++ {
            // 行翻转由首位决定，同一行所有格子使用相同翻转标记。
            rowFlip := 0
            if grid[i][0] == 0 {
                rowFlip = 1
            }
            ones += grid[i][j] ^ rowFlip
        }
        // 当前列可翻或不翻，选择一的数量更多的一种。
        best := ones
        if m-ones > best {
            best = m - ones
        }
        answer += best * (1 << (n - 1 - j))
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(mn)$。
  • 空间复杂度：$O(1)$，只计算逻辑翻转，不修改输入矩阵。

关键点总结

[!green]

  • 最高位优先由位权大小严格保证。
  • 列翻转只改变本列贡献，可以独立选多数。
  • 行翻转标记由首位决定，在同一行内保持一致。

易错点总结

[!yellow]

  • 忽略行翻转，直接统计原列中一的个数：后续列的有效格值不正确。
  • 把位权写成从左到右递增：高低位含义反了。
  • 已经计入首列，又在循环里重复累计：最高位被算两次。
  • 只取 ones，不考虑 m-ones：漏掉翻列可以增加得分的情况。

相似题目

题目 难度 关联与区别
1072. 按列翻转得到最大值等行数 中等 同样翻转整列，原题最大化行内全相等的行数，本题还可翻行且按二进制位权最大化总分。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/12114884
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！