题目描述
思路解析
一句话答案：LeetCode 861 翻转矩阵后的得分：每行每列都能整体翻转，贪心先翻行让首列全 1 保住最高位，再逐列取「1 更多」的方向按位权累加求和，时间复杂度 O(m·n)。
整行整列随便翻，怎么让每行读成的二进制数加起来最大
给一个只含 0 和 1 的矩阵，一次操作是挑一整行或一整列，把里面 0 变 1、1 变 0，翻几次都行。翻完后每一行读成一个二进制数，比如 1101 就是 13，各行的值相加就是得分。题面给的 grid=[[0,0,1,1],[1,0,1,0],[1,1,0,0]]，最优翻法能拿到 39，求的就是最大得分。
为什么不能只盯着「让 1 尽量多」去翻
一个直觉是让整张矩阵的 1 越多越好，哪行哪列 0 多就翻哪个。可同样是 1，位置不同值差很远：每行最左是最高位，4 列的行里首位的 1 值 8，末位的 1 只值 1。为凑几个末位的 1 放走首位的 1，总分反而下掉，所以数 1 的总数没用，得看每个 1 落在哪一位。
先翻行抢下最高位，再逐列让 1 不少于 0
把翻法拆成固定两步，顺序不能反。第一步只翻行：逐行看首位，首位是 0 就整行翻一次让它变 1，本来是 1 就不动，这样每行最高位都抢到 1、首列全变成 1。这一步是贪心，也就是先拿下最值钱的那一位、不为小的让步。第二步只翻列：首列已全 1 不必再碰，从第二列起逐列数 1 的个数，只要 1 比 0 少就整列翻过来，让这列 1 不少于 0。两步做完得分最大。
翻完行后各列彼此独立，一列的贡献能直接算出来
第一步定下后首列绝不再翻，各列就彼此独立，翻一列动不到别的列。既然独立，每列单独取「1 最多」的方向就是这列最优，合起来就是全局最优。一列翻或不翻只有两种结果：不翻是 cnt 个 1，翻了是 m 减 cnt 个 1，要较大的那个。每个 1 的价值都是这列的位权，也就是第 j 列贡献 2 的 (n 减 j 减 1) 次方(n 为列数)，所以这列添的分就是 max(cnt, m - cnt) 乘位权，矩阵不用真改。
拿题面这张 3×4 矩阵走一遍到 39
先翻行。第 0 行首位是 0，整行翻成 [1,1,0,0]；第 1、2 行首位都是 1，不动，仍是 [1,0,1,0] 和 [1,1,0,0]。
再逐列算，n=4。第 0 列 [1,1,1]，cnt=3，取 max(3,0)=3，位权 2³=8，贡献 24。第 1 列 [1,0,1]，cnt=2，取 max(2,1)=2，位权 2²=4，累计 32。第 2 列 [0,1,0]，cnt=1，取 max(1,2)=2，位权 2¹=2，累计 36。第 3 列 [0,0,0]，cnt=0，取 max(0,3)=3，位权 2⁰=1，累计 39。
另一条验法：翻过 1 少于 0 的第 2、3 列后每行是 1111、1001、1111，即 15、9、15，加起来 39。
两遍扫矩阵就够，行别回头、列别把等号翻反
翻行扫一遍、数列扫一遍，每个格子只碰常数次，时间 O(m·n)；原地做只用几个计数变量，空间 O(1)。翻完行别回头——首列已全是 1，再翻任一行都会把值 8 的最高位弄丢，行只在第一步处理一次。判断列翻不翻时等号别搞反：1 少于 0 才翻、相等不动，写成「1 不少于 0 就翻」会把好列翻坏。边界也想清：单格非 0 即 1，答案就是 1；全 0 矩阵也能靠翻行把首列凑满，得分不会是 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这把尺子:首列必须全 1(最高位优先),其余每列让 1 尽量多——1 少于 0 才翻、相等不动,最终 1 不少于 0。下面每一帧都在套它。
输入矩阵 · 3×4 · 绿=1 蓝=0：这是原始矩阵,绿色格是 1、蓝色格是 0。我们先处理行、再处理列。先想清楚:每行的最左边是最高位,一个高位的 1 抵得上后面好几位,所以最该先抢的就是首列。
第一步 · 逐行看首位：紫色这一列是首列,也就是每行的最高位。我们一行一行检查它的首位:是 1 就不动,是 0 就把整行翻过来。先从第 0 行开始。
第 0 行 · 首位 = 0：轮到第 0 行,内容是 [0, 0, 1, 1]。它的首位是 0。首位是 0,最高位还没抢到手,这一整行得翻一次。
翻转第 0 行：整行翻过来(红色闪一下),第 0 行变成 [1, 1, 0, 0],首位现在是 1,最高位拿下了。
第 1 行 · 首位 = 1：轮到第 1 行,内容是 [1, 0, 1, 0]。它的首位是 1。首位已经是 1,最高位到手,这一行不用动。
第 1 行保持不动：第 1 行原样保留,首位本来就是 1,白翻还会把它弄丢,不动它。
第 2 行 · 首位 = 1：轮到第 2 行,内容是 [1, 1, 0, 0]。它的首位是 1。首位已经是 1,最高位到手,这一行不用动。
第 2 行保持不动：第 2 行原样保留,首位本来就是 1,白翻还会把它弄丢,不动它。
第一步完成 · 首列全是 1：第一步收工。看紫色的首列,现在三个格全是 1,每一行的最高位都抢到了手。矩阵变成 [1,1,0,0]、[1,0,1,0]、[1,1,0,0]。接下来处理其余各列,让低位也尽量多挣分。
第二步 · 逐列数 1 的个数：第二步换个方向,逐列看。每一列数一数有几个 1,如果 1 的个数少于 0,就把整列翻过来;相等就不翻,目标是让每列 1 不少于 0。注意首列已经全是 1 了,翻它只会变差,所以从第 1 列起真正可能动手。
第 0 列 · 1 的个数 = 3：看第 0 列(紫色),从上到下是 [1, 1, 1]。数一下:1 有 3 个,0 有 0 个。这是首列,刚抢成全 1,自然不用翻。
第 0 列保持不动：第 0 列保持不动,1 本来就有 3 个、不少于 0,翻了反而变少。
第 1 列 · 1 的个数 = 2：看第 1 列(紫色),从上到下是 [1, 0, 1]。数一下:1 有 2 个,0 有 1 个。1 不少于 0,保持不动。
第 1 列保持不动：第 1 列保持不动,1 本来就有 2 个、不少于 0,翻了反而变少。
第 2 列 · 1 的个数 = 1：看第 2 列(紫色),从上到下是 [0, 1, 0]。数一下:1 有 1 个,0 有 2 个。1 少于 0,这一列翻过来更划算。
翻转第 2 列：整列翻过来(红色闪一下),第 2 列变成 [1, 0, 1],现在 1 有 2 个,1 不少于 0 了。
第 3 列 · 1 的个数 = 0：看第 3 列(紫色),从上到下是 [0, 0, 0]。数一下:1 有 0 个,0 有 3 个。1 少于 0,这一列翻过来更划算。
翻转第 3 列：整列翻过来(红色闪一下),第 3 列变成 [1, 1, 1],现在 1 有 3 个,1 不少于 0 了。
第二步完成 · 每列 1 不少于 0：第二步收工,矩阵不再翻动了。现在每一行是 [1111]、[1001]、[1111]。最后一步,把每一行当成二进制数算出来,再加到一起。
第 0 行二进制 = 1111 = 15：把第 0 行(紫色)按二进制读:1111,换成十进制就是 15。累计得分加上它,现在是 15。
第 1 行二进制 = 1001 = 9：把第 1 行(紫色)按二进制读:1001,换成十进制就是 9。累计得分加上它,现在是 24。
第 2 行二进制 = 1111 = 15：把第 2 行(紫色)按二进制读:1111,换成十进制就是 15。累计得分加上它,现在是 39。
全部完成 · 最大得分 = 39：三行加起来:15 加 9 加 15,等于 39。这就是最大得分。先翻行保最高位、再翻列让每列 1 不少于 0,这套贪心一定最优。
边界先想清:单格非 0 即 1 答案都是 1;全 0 矩阵翻完每行也能凑满。
两个高频追问:两步各自局部最优叠成全局最优;列可用计数公式免去真翻。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *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复杂度
- 时间：O(m·n)，逐行翻一遍、逐列数一遍,每个格子只被碰常数次
- 空间：O(1)，原地翻转,只用计数变量,不开额外矩阵
易错点
面试追问把动画讲成自己的话
追问为什么「先翻行保首列、再翻列让 1 尽量多」这套贪心能保证全局最优?
追问处理列时为什么可以不真的翻矩阵,直接用计数公式算?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
螺旋矩阵 III
LeetCode 885 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题