题目描述
思路解析
一句话答案：LeetCode 1072 按列翻转得到最多相等行：把每行以首元素为基准规范化成 0/1 模式，模式相同的行能一起翻成行内全相等，哈希数出现最多的那种模式即答案，时间 O(m·n)。
翻列翻的是什么，最后要数哪种行
给一个只含 0 和 1 的矩阵 matrix，一次操作是挑一整列、把这列里每个 0 和 1 全部取反，可以翻任意多列。要数的不是两行彼此相等，而是某一行自己内部的值全都一样（全 0 或全 1）。翻完之后最多能有多少行做到行内全相等？题面示例 matrix=[[0,1],[1,0]]，翻第 0 列后两行各自全相等，答案是 2。
枚举所有翻法，2ⁿ 会把时间拖垮
n 列里每一列都有翻或不翻两个选择，把所有翻法枚举一遍就是 2ⁿ 种组合，每种还要扫一遍矩阵数出有几行达标，合计 O(2ⁿ·m·n)。列数刚到二十，2ⁿ 就过百万，这条硬枚举的路根本走不动，得找个只扫一遍矩阵就能定答案的办法。
翻掉一整列，行内的相对模式为什么纹丝不动
先盯住单独一行：要让它行内全相等，翻法其实是定死的——凡是和首元素不同的那些列都翻掉，这行立刻变成全 0 或全 1。所以每行都自带一张『翻法清单』。
这张清单只记录行内各格与首元素的相对关系，而翻一整列恰恰动不了这层关系：某格本来和首元素相同，翻这列时首元素也在这列、跟着一起翻，两者仍旧相同；本来不同的也依然不同。既然翻列不改变行内的相对模式，两行能不能用同一组翻列一起达标，就只看它们的相对模式是否完全一致。把每行按『和首元素相同记 0、不同记 1』压成一串 0/1 模式，模式相同的行就是能一起翻齐的行。
统一以首元素定 0 与 1，再拿哈希数模式
落到代码上只有两步。第一步规范化：所有行用同一个口径，以首元素为基准、同记 0 异记 1，这么一压，原始就相同的行和每一位都相反的互补行会得到同一串模式、落进同一个键。第二步计数：把每行的模式丢进哈希表，按键累加次数、平均常数时间就能存取，最后取出现次数最多的那种模式，它的次数就是能同时行内全相等的最大行数。口径必须全表统一，若一行拿首元素当基准、另一行拿别的列，同类就会被拆散、答案跟着错。
对着题面两个矩阵，亲手数一遍模式
第一个示例 matrix=[[0,1],[1,1]]：第一行 [0,1] 首元素是 0，保留原样，模式记成 01；第二行 [1,1] 首元素是 1，每一位异或 1、也就是两位相同得 0 不同得 1，翻过来模式记成 00。两串模式各出现 1 次，最多 1 行，答案 1。第二个示例 matrix=[[0,1],[1,0]]：第一行 [0,1] 模式还是 01；第二行 [1,0] 首元素是 1，异或 1 之后也得到 01。同一串 01 出现了 2 次，答案是 2——对应翻第 0 列，两行正好各自全相等。
互补行凭什么同组，模式全不同又剩几行
复杂度上，每格只参与一次模式计算，时间 O(m·n)；哈希表最坏要存 m 个长度为 n 的键，空间 O(m·n)。有两处地方容易想岔。一处是互补的两行，像 [0,1] 和 [1,0]，表面每位都相反，规范化后却落到同一个键、能一起达标数成 2，别被相反的外表骗过去。另一处是每行模式各不相同时，哈希表里每个键都只有 1，最多只能有一行做到行内全相等。最后别把题意读成『找两行相等』，它要的是一行内部全相同，目标看错，后面全白算。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这把尺子:每行压成一串 0/1 模式,首位永远是 0,模式一样的行能一起翻成行内全相等。下面每一帧都在套它。
输入矩阵 · 4×4 · 绿=1 蓝=0：这是原始矩阵,绿格是 1、蓝格是 0。我们一行一行处理,给每行算一个模式串,再把模式丢进右边的计数表。先想清楚一件事:每行单独都能翻成行内全相等(把和首格不同的列翻掉就行),所以要数的不是一行行不行,关键是哪些行需要翻的列一模一样、能一起翻齐。模式串记的,就是每行该翻哪些列。
基准列 · 每行第 0 个元素：高亮的这一列是每行的「基准」,也就是各行的第 0 个元素。规范化的做法是:让基准位永远记成 0,其余每格和基准比,一样记 0、不一样记 1。这串 0/1 其实是一张「翻法清单」:记 1 的列要翻、记 0 的列不翻,翻完整行就都和首格对齐、变成全相等。两行如果清单(模式)一模一样,要翻的列就完全相同,自然能用同一组翻列一起变齐,所以模式才是判断的依据。
第 0 行 · 基准 = 0：轮到第 0 行(紫色),内容是 [0, 1, 1, 0]。它的基准是首元素 0。接下来每个格子和这个基准比一比,一样写 0、不一样写 1,拼出这行的模式。
第 0 行 · 第 0 格 = 0 → 记 0：第 0 格就是基准本身,和自己当然相同,记成 0。模式开头先有一个 0,后面所有格都拿它当尺子。
第 0 行 · 第 1 格 = 1 → 记 1：第 1 格是 1,基准是 0,两者不同,记 1。模式拼到 01。
第 0 行 · 第 2 格 = 1 → 记 1：第 2 格是 1,基准是 0,两者不同,记 1。模式拼到 011。
第 0 行 · 第 3 格 = 0 → 记 0：第 3 格是 0,基准是 0,两者相同,记 0。模式拼到 0110。
第 0 行模式 = 0110 入表：第 0 行的模式是 0110。把它丢进右边计数表,出现 1 次。当前能凑齐行内全相等的行数最多是 1。
第 1 行 · 基准 = 1：轮到第 1 行(紫色),内容是 [1, 0, 0, 1]。它的基准是首元素 1。接下来每个格子和这个基准比一比,一样写 0、不一样写 1,拼出这行的模式。
第 1 行规范化 → 0110：第 1 行每个格子和基准 1 比:相同记 0、不同记 1,拼出来是 0110。注意,这和前面第 0 行的模式一模一样。
第 1 行模式 = 0110 入表：模式 0110 入表,现在出现 2 次。计数表里最高的一格是 2,它就是目前能凑齐行内全相等的最大行数。
第 2 行 · 基准 = 0：轮到第 2 行(紫色),内容是 [0, 0, 1, 0]。它的基准是首元素 0。接下来每个格子和这个基准比一比,一样写 0、不一样写 1,拼出这行的模式。
第 2 行规范化 → 0010：第 2 行每个格子和基准 0 比:相同记 0、不同记 1,拼出来是 0010。这是一个新模式。
第 2 行模式 = 0010 入表：模式 0010 入表,现在出现 1 次。计数表里最高的一格是 2,它就是目前能凑齐行内全相等的最大行数。
第 3 行 · 基准 = 1：轮到第 3 行(紫色),内容是 [1, 0, 0, 1]。它的基准是首元素 1。接下来每个格子和这个基准比一比,一样写 0、不一样写 1,拼出这行的模式。
第 3 行规范化 → 0110：第 3 行每个格子和基准 1 比:相同记 0、不同记 1,拼出来是 0110。注意,这和前面第 0 行的模式一模一样。
第 3 行模式 = 0110 入表：模式 0110 入表,现在出现 3 次。计数表里最高的一格是 3,它就是目前能凑齐行内全相等的最大行数。
统计完成 · 最多的模式 = 0110(3 次)：四行都规范化完了。计数表里 0110 出现 3 次、0010 出现 1 次。次数最多的是 0110,有 3 行。也就是说,有一组翻列能让这 3 行同时变成行内全相等。答案就是这个最大次数 3。
验证 · 翻第 1 列和第 2 列：验证一下 0110 这组。模式里记 1 的位是第 1 列和第 2 列(闪红的两列),把它们整列翻过来,就能让所有 0110 的行各自变成行内全相等。下一帧看翻完的样子。
翻完 · 第 0、1、3 行行内全相等：翻完第 1、2 列:第 0 行变成 0000、第 1 行和第 3 行都变成 1111,这三行各自行内全相等(紫色高亮)。第 2 行变成 0100,还是混的、不达标。达标的恰好 3 行,和模式 0110 的出现次数对上了。
答案 = 3：整道题收束成一句话:把每行规范化成模式,模式相同的行能一起翻成行内全相等,哈希数出现次数最多的那种模式,次数就是答案。这里是 3。一次扫描就解决,不用真去枚举翻哪些列。
边界先想清:互补的两行(如 01 和 10)规范化后同模式,能一起达标记 2;模式各不相同时最多只有 1 行。
两个高频追问:模式就是每行的翻法清单,清单相同(同模式)就能用同一组翻列一起翻齐;计数取最大用哈希最自然,排序或位压缩是可选权衡。
参考代码
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 maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int: cnt = Counter() for row in matrix: t = tuple(row) if row[0] == 0 else tuple(x ^ 1 for x in row) cnt[t] += 1 return max(cnt.values())复杂度
- 时间：O(m·n)，每行扫一遍算模式、各格只碰一次;哈希插入与查询平均 O(1)
- 空间：O(m·n)，哈希表最多存 m 个模式键,每个键长 n;最坏全不同就是 m·n
易错点
面试追问把动画讲成自己的话
追问为什么「模式相同」就一定能用同一组翻列让这些行同时变成行内全相等?
追问这道题为什么哈希表是最自然的工具,能不能不用哈希?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
航班预订统计
LeetCode 1109 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题