题目描述
思路解析动画文字版
记牢这把尺子:每行压成一串 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题