How can I maximize the score in the Score After Flipping Matrix problem?

The key is to apply a greedy approach where you flip rows to maximize the leftmost bit, and then flip columns based on the number of 1's in each column.

What is the main algorithmic pattern for solving Score After Flipping Matrix?

The problem follows the greedy choice plus invariant validation pattern, where you make local optimal decisions (flipping rows and columns) and validate the overall configuration.

What is the time complexity of the solution for Score After Flipping Matrix?

The time complexity is O(m * n), where m is the number of rows and n is the number of columns in the matrix.

Can the Score After Flipping Matrix problem be solved with dynamic programming?

No, dynamic programming is not the best approach for this problem; the optimal solution involves greedy choices with row and column flips, followed by invariant validation.

How do I avoid common mistakes in the Score After Flipping Matrix problem?

Focus on flipping rows to ensure the most significant bit is 1, then validate column flips based on the number of 1's and 0's in each column to maximize the score.

#861

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

翻转矩阵后的得分

给你一个大小为 m x n 的二元矩阵 grid ，矩阵中每个元素的值为 0 或 1 。一次移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1 ，将所有 1 都更改为 0 。在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总…

数组贪心位运算矩阵

题目描述

给你一个大小为 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

lightbulb

解题思路

方法一：贪心

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

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

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

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

1

2

3

4

5

6

7

8

9

10

11

12

13

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

speed

复杂度分析

指标	值
时间	O(m \cdot n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Look for an approach that efficiently handles the greedy choice of flipping rows and columns.
question_mark
Ensure the candidate can correctly apply invariant validation to the matrix after row flips.
question_mark
The candidate should demonstrate the ability to compute the final score efficiently.

warning

常见陷阱

外企场景

error
Failing to flip rows initially to ensure the most significant bit is 1.
error
Not correctly validating column flips based on the number of 1's and 0's.
error
Overcomplicating the solution by not sticking to the greedy choice plus invariant validation pattern.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider the scenario where m or n is at the upper limit of 20, testing the scalability of the approach.
arrow_right_alt
Modify the problem to allow flipping only rows or only columns, testing how the solution adapts to different constraints.
arrow_right_alt
Introduce additional constraints on which rows and columns can be flipped based on certain conditions, adding complexity to the problem.

help

常见问题

外企场景

继续练习

#864 获取所有钥匙的最短路径 #832 翻转图像 #807 保持城市天际线