题目描述
思路解析动画文字版
记牢这一句:一行被覆盖,等价于这行所有的 1 都躲在你选的列底下。空行没有 1,天然被覆盖。下面把 3 种选列方案一种一种试过去。
先认识这张矩阵 · 4 行 3 列：这就是我们的舞台:4 行 3 列,格子里写着 0 或 1。列从左到右编号 0、1、2。任务是从这 3 列里挑出 2 列,让被覆盖的行尽量多。先把每一行的 1 分布看清楚,下一帧我把每行需要哪些列标出来。
把每行需要的列标出来 · 空行天然覆盖：把每行的 1 用橙色点亮,它们所在的列就是这行「需要」被选中的列。第 0 行没有 1,整行标绿,它谁都不挑剔、天生就被覆盖。第 1 行需要第 0 列和第 2 列,第 2 行需要第 1 列和第 2 列,第 3 行只需要第 2 列。接下来看哪种选法能满足最多的行。
第一种选法 · 选中 第0列 第1列：第一种选法,我们把第 0 列和第 1 列选中,这两整列染成琥珀色。选定之后,就该一行一行地问:这行的 1 是不是都被这两列罩住了。从第 0 行开始查。
第一种选法 · 查第 0 行 · 覆盖：第 0 行一个 1 都没有,天然被覆盖,整行标绿,覆盖数记到 1。
第一种选法 · 查第 1 行 · 未覆盖：第 1 行需要 第0列 第2列,可是 第2列 没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 1。
第一种选法 · 查第 2 行 · 未覆盖：第 2 行需要 第1列 第2列,可是 第2列 没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 1。
第一种选法 · 查第 3 行 · 未覆盖：第 3 行需要 第2列,可是 第2列 没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 1。
第一种选法结算 · 覆盖 1 行,刷新最优：第一种选法查完:只有第 0 行那个空行被覆盖,其余三行都有 1 露在没选的列里,一共覆盖 1 行。这是第一手成绩,先把最优记成 1。
第二种选法 · 选中 第0列 第2列：换第二种选法,这回选中 第0列 第2列,把它们整列染成琥珀色。前一种选法的结果先记在最优里,现在拿这套新选法重新逐行判定。
第二种选法 · 查第 0 行 · 覆盖：第 0 行一个 1 都没有,天然被覆盖,整行标绿,覆盖数记到 1。
第二种选法 · 查第 1 行 · 覆盖：第 1 行需要 第0列 第2列,这些列全在选中的 第0列 第2列 里,所有 1 都变绿被罩住,这行覆盖,覆盖数记到 2。
第二种选法 · 查第 2 行 · 未覆盖：第 2 行需要 第1列 第2列,可是 第1列 没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 2。
第二种选法 · 查第 3 行 · 覆盖：第 3 行需要 第2列,这些列全在选中的 第0列 第2列 里,所有 1 都变绿被罩住,这行覆盖,覆盖数记到 3。
第二种选法结算 · 覆盖 3 行,刷新最优：这种选法覆盖了 3 行,比之前的最优还多,把最优刷新到 3。选到这套列,收获明显更大。
第三种选法 · 选中 第1列 第2列：换第三种选法,这回选中 第1列 第2列,把它们整列染成琥珀色。前一种选法的结果先记在最优里,现在拿这套新选法重新逐行判定。
第三种选法 · 查第 0 行 · 覆盖：第 0 行一个 1 都没有,天然被覆盖,整行标绿,覆盖数记到 1。
第三种选法 · 查第 1 行 · 未覆盖：第 1 行需要 第0列 第2列,可是 第0列 没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 1。
第三种选法 · 查第 2 行 · 覆盖：第 2 行需要 第1列 第2列,这些列全在选中的 第1列 第2列 里,所有 1 都变绿被罩住,这行覆盖,覆盖数记到 2。
第三种选法 · 查第 3 行 · 覆盖：第 3 行需要 第2列,这些列全在选中的 第1列 第2列 里,所有 1 都变绿被罩住,这行覆盖,覆盖数记到 3。
第三种选法结算 · 覆盖 3 行,打平已有：这种选法覆盖了 3 行,和之前的最优打平,没有超过,最优保持 3,不更新。
回放 · 3 种选法比完,最多覆盖 3 行：三种选法全试完了。选第 0 列和第 1 列只盖住 1 行;选第 0 列和第 2 列、以及选第 1 列和第 2 列,都能盖住 3 行。取最大,答案就是 3。这里定格在第 0 列和第 2 列这套:第 0 行空行绿、第 1 行两个 1 全绿、第 3 行的 1 也绿,三行齐了,只有第 2 行因为第 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 *from string import *from operator import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int: m, n = len(matrix), len(matrix[0]) masks = [] for row in matrix: mask = 0 for j, v in enumerate(row): if v: mask |= 1 << j masks.append(mask) ans = 0 for cols in combinations(range(n), numSelect): pick = 0 for c in cols: pick |= 1 << c ans = max(ans, sum((mask & pick) == mask for mask in masks)) return ans复杂度
- 时间：O(m·n + m·2ⁿ)，先花 O(m 乘 n) 把每行压成掩码。枚举选法时,C plus plus 和 Java 遍历 2 的 n 次方个 pick,每个 pick 扫 m 行做一次按位与判断,是 O(m 乘 2 的 n 次方);Python 只枚举 C(n, numSelect) 个组合,更少,但同阶封顶。n 最多 12,规模完全可控
- 空间：O(m)，按峰值算。只额外存了 m 个行掩码,是 O(m)。枚举时的 pick、计数都是常数几个变量,不随规模增长
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问为什么可以用枚举而不怕超时?
追问为什么用位运算而不是集合?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
生成不含相邻零的二进制字符串
LeetCode 3211 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题