LeetCode 861. 翻转矩阵后的得分
目录
题目描述
题意分析
给一个只含 0 和 1 的 $m \times n$ 矩阵。一次操作可以把任意一整行或任意一整列的所有元素取反（0 变 1、1 变 0），操作次数不限。每一行按从左到右当作一个二进制数，得分是所有行的十进制值之和，问能拿到的最高得分。
先看操作的性质：同一行翻两次等于没翻，所以每行的状态只有「翻」与「不翻」两种，列同理。整个方案本质上是「选一个行子集 + 选一个列子集」，共 $2^m \cdot 2^n$ 种，$m, n$ 最大 20 时是 $2^{40}$，枚举不可行——但这个数字也提示答案不需要复杂结构，只要能证明每一步的最优选择即可。
再看操作的顺序：行翻转与列翻转互相独立，作用在某个格子上的效果就是两次异或，先后无关。这条性质很关键，它允许我们把决策拆成「先定所有行、再定所有列」两个阶段而不损失最优性。
最后看目标函数：第
j列（从 0 开始）在每一行里的位权是 $2^{n-1-j}$，最左列权重最大。一个熟悉的二进制事实是 $2^{n-1} > 2^{n-2} + \dots + 2^0$，即最高位的一个 1 比后面所有位全是 1 加起来还大。这句话直接决定了贪心的优先级。边界：矩阵至少 $1 \times 1$；某行本来就以 1 开头时不该翻；
n = 1时只有最高位一列，答案就是行数m。
解法：贪心（行先、列后）+ 直接计分
核心思路
暴力做法是枚举行翻转的 $2^m$ 种组合，对每种组合再逐列决定翻不翻（列的最优选择在行确定后是显然的：哪边 1 多留哪边）。这样是 $O(2^m \cdot mn)$，$m = 20$ 时就是上亿次矩阵扫描，不可行。
瓶颈在于「行怎么翻」被当成了自由变量。但由位权的性质可以把它钉死：每一行都必须让第 0 列为 1。理由是，无论后面 $n-1$ 位怎么安排，它们的总和最多是 $2^{n-1} - 1$，严格小于最高位的 $2^{n-1}$。所以只要某行最高位是 0，把这一行整体翻转必然使该行的值变大，绝不会更差。于是行的决策完全确定：
grid[i][0] == 0就翻这一行，否则不翻。行定死之后，列的决策也变得显然。对第
j列（j >= 1），统计行翻转生效后该列有多少个 1，记为ones。若翻这一列，1 的个数变成m - ones。该列对总分的贡献是「1 的个数 × 位权」，所以取max(ones, m - ones)即可。这里之所以能逐列独立决策，是因为列翻转只影响自己这一列，不会改变其他列的 1 的分布。第 0 列为什么不参与列翻转的比较？因为行阶段已经把它全部变成了 1，它的 1 的个数是
m，已是上限，翻转只会更差。它的贡献固定为 $m \cdot 2^{n-1}$，直接作为答案初值。还有一个实现上的化简：不需要真的修改矩阵。第
i行是否翻转由grid[i][0]唯一决定，令rowFlip = (grid[i][0] == 0) ? 1 : 0，那么格子(i, j)在行翻转生效后的值就是grid[i][j] ^ rowFlip。异或一个 0/1 标志正好表达「翻或不翻」，省掉一次 $O(mn)$ 的原地改写，也避免了改坏输入。不变量：外层按列从左往右推进，处理完第
j列时，answer恰好等于「最优方案下，第 0 到j列这些位所贡献的分数之和」。因为各列贡献可加且互不影响，逐列累加得到的就是全局最优。
解题步骤
- 答案初值取
m * (1 << (n - 1))：行翻转保证第 0 列全是 1，m行每行在最高位贡献 $2^{n-1}$。把这一项直接算成初值，比先改矩阵再统一计分少一次遍历。- 列循环从
j = 1开始：第 0 列已经在初值里结算完毕，且它不该再翻，从 1 起既省事又避免误翻最高位。- 对每列统计
ones：内层遍历所有行，rowFlip = grid[i][0] == 0 ? 1 : 0，累加grid[i][j] ^ rowFlip。rowFlip在内层现算而不是预处理成数组，是因为它只是一次比较，开数组反而多占 $O(m)$ 空间。- 取
best = max(ones, m - ones)：ones是不翻这列的 1 的个数，m - ones是翻了之后的个数，谁大取谁。二者相等时（m为偶数且恰好各半）翻不翻都一样，取哪个都对。- 累加
best * (1 << (n - 1 - j))：位权按列下标递减。用1 << (n-1-j)而不是循环乘 2，既清晰又不会累积误差。- 返回
answer。以
grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]走一遍，m = 3、n = 4。行阶段：第 0 行首位是 0，
rowFlip = 1，逻辑上变成[1,1,0,0]；第 1 行首位是 1，rowFlip = 0，保持[1,0,1,0]；第 2 行首位是 1，保持[1,1,0,0]。初值：
answer = 3 * (1 << 3) = 3 * 8 = 24，对应三行的最高位各贡献 8。
j = 1（位权 4）：三行在该列的有效值分别是0 ^ 1 = 1、0 ^ 0 = 0、1 ^ 0 = 1，ones = 2。m - ones = 1，取best = 2（不翻这列）。answer += 2 * 4 = 8，累计 32。
j = 2（位权 2）：有效值1 ^ 1 = 0、1 ^ 0 = 1、0 ^ 0 = 0，ones = 1。m - ones = 2，取best = 2（翻这列更划算）。answer += 2 * 2 = 4，累计 36。
j = 3（位权 1）：有效值1 ^ 1 = 0、0 ^ 0 = 0、0 ^ 0 = 0，ones = 0。m - ones = 3，取best = 3（翻这列）。answer += 3 * 1 = 3，累计 39。返回 39。验证一下：翻第 0 行、再翻第 2 列和第 3 列，矩阵变为
[[1,1,1,1],[1,0,0,1],[1,1,1,1]]，三行的值是 15、9、15，和正是 39。顺带看看贪心顺序不能颠倒：若先按「让每列 1 最多」去翻列，第 0 列原本是
[0,1,1]，1 已占多数不会翻，第 0 行的最高位就永远停在 0，该行最多只能拿到 7 分，而正确方案能拿 15。这就是「高位优先」必须凌驾于「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)$。外层遍历 $n-1$ 列、内层遍历 $m$ 行，每个格子只被读一次；行翻转标志由
grid[i][0]现场推出，不需要额外的预处理遍历。- 空间复杂度：$O(1)$。只用了
answer、ones、best、rowFlip几个标量，既没有复制矩阵，也没有开行翻转数组——「不真的翻转、用异或代替」正是省下这部分空间的原因。
关键点总结
- 位权决定贪心优先级：$2^{k} > 2^{k-1} + \dots + 2^0$，所以高位的一个 1 永远比低位全填 1 更值钱，凡是「按二进制计分」的题都先保高位。
- 行操作与列操作互相独立（对每个格子只是两次异或，与顺序无关），这条性质才允许把决策拆成「先行后列」两个阶段而不损失最优性；不先确认独立性就分阶段贪心是危险的。
- 决策一旦被证明唯一（每行首位必须为 1），就不再是搜索问题；把 $2^m$ 的枚举压成 $O(1)$ 的判断，靠的是证明而不是剪枝。
- 不必真的修改输入：用一个 0/1 标志与原值异或，就能表达「翻转后的有效值」，既省空间又避免破坏调用方数据。这个技巧在各类翻转题里通用。
- 第 0 列已被行阶段拉满，不参与列阶段的
max比较；把它的贡献直接算进答案初值，能少写一段特判。- 面试视角：先讲清「为什么每行必须以 1 开头」的严格不等式，再讲「列之间互不影响所以可以逐列取多数」，两句话就是完整证明。能主动说出「不需要真的翻转矩阵」通常是加分项。
易错点总结
- 先按列贪心再按行贪心：
[[0,0,1,1],[1,0,1,0],[1,1,0,0]]中第 0 列是[0,1,1]，按「1 多不翻」会保留第 0 行的首位 0，最终得分 32 而不是 39。- 列循环从
j = 0开始并参与max比较：[[0],[0],[1]]这类首列 0 居多的输入会把已经全 1 的最高位翻回去，得分从m掉到更小。- 忘记把第 0 列的贡献算进初值：答案会少 $m \cdot 2^{n-1}$，
[[1]]会返回 0 而不是 1。- 位权写成
1 << j：[[1,0]]中第 1 列本应权重 1，写成1 << 1 = 2会让低位比高位还重，得分算成 4 而正确答案是 3。rowFlip判定用grid[i][j]而不是grid[i][0]：翻转是整行的统一决策，用当前列的值判定等于每列各翻各的，[[0,1],[1,0]]会算出高于真实上限的分数。- 真的原地翻转矩阵却漏掉第 0 列：改写时只从
j = 1开始异或，第 0 列仍是原值，后续若再读grid[i][0]判定rowFlip就会得到相反结论，逻辑自相矛盾。best只取ones不比较m - ones：[[1,0],[1,0]]中第 1 列ones = 0，不翻得 0 分，正确应翻转得2 * 1 = 2，总分从 8 变 6。- 用
Math.pow算位权：返回double再转int，n较大时浮点舍入会让1 << 19附近出现偏差；位运算既准确又快。- 误以为可以翻转单个格子：题目只允许整行或整列翻转，若按单格自由翻转，任何矩阵都能拉满成全 1，
[[0,1],[1,0]]会算出 6 而正确答案是 5。m与n取反：grid.length是行数、grid[0].length是列数，弄反会让1 << (n-1)的移位数错误，非方阵输入上直接算错甚至移位越界。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 670. 最大交换 | 中等 | 同为「高位优先」贪心，但只能交换一次，要找最靠后的最大数字 |
| 421. 数组中两个数的最大异或值 | 中等 | 从最高位往下逐位确定答案，用字典树或哈希验证该位能否取 1 |
| 995. K 连续位的最小翻转次数 | 困难 | 翻转窗口长度固定，必须用差分数组维护累计翻转次数，无法逐位独立决策 |
| 48. 旋转图像 | 中等 | 同为整行整列级别的矩阵变换，考的是原地转置加翻转的分解 |
| 73. 矩阵置零 | 中等 | 也用首行首列承载标记信息，与本题「用 grid[i][0] 推出行状态」思路相通 |