LeetCode 2397中等回溯 · 枚举

被列覆盖的最多行数图解题解

这道题到底在问什么

给定一个 m 行 n 列、只含 0 和 1 的矩阵 matrix,以及一个整数 numSelect,表示必须选出的不同列的数量。若某一行中所有值为 1 的格子所在的列都被选中,或该行本来就没有 1,则这一行被覆盖。返回选出 numSelect 列时能覆盖的最大行数。

输入: matrix=[[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect=2
输出: 3
输入: matrix=[[1],[0]], numSelect=1
输出: 2

最优解：一步一步想明白

3记牢这一句:一行被覆盖,等价于这行所有的 1 都躲在你选的列底下。空行没有 1,天然被覆盖。下面把 3 种选列方案一种一种试过去。
4目标:选 2 列覆盖最多行这就是我们的舞台:4 行 3 列,格子里写着 0 或 1。列从左到右编号 0、1、2。任务是从这 3 列里挑出 2 列,让被覆盖的行尽量多。先把每一行的 1 分布看清楚,下一帧我把每行需要哪些列标出来。
5橙格=这行的 1,绿行=空行把每行的 1 用橙色点亮,它们所在的列就是这行「需要」被选中的列。第 0 行没有 1,整行标绿,它谁都不挑剔、天生就被覆盖。第 1 行需要第 0 列和第 2 列,第 2 行需要第 1 列和第 2 列,第 3 行只需要第 2 列。接下来看哪种选法能满足最多的行。
6开始判定第0列第1列第一种选法,我们把第 0 列和第 1 列选中,这两整列染成琥珀色。选定之后,就该一行一行地问:这行的 1 是不是都被这两列罩住了。从第 0 行开始查。
7第 0 行覆盖第 0 行一个 1 都没有,天然被覆盖,整行标绿,覆盖数记到 1。
8第 1 行漏了第 1 行需要第0列第2列,可是第2列没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 1。
9第 2 行漏了第 2 行需要第1列第2列,可是第2列没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 1。
10第 3 行漏了第 3 行需要第2列,可是第2列没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 1。
11目前最优 1 行第一种选法查完:只有第 0 行那个空行被覆盖,其余三行都有 1 露在没选的列里,一共覆盖 1 行。这是第一手成绩,先把最优记成 1。
12开始判定第0列第2列换第二种选法,这回选中第0列第2列,把它们整列染成琥珀色。前一种选法的结果先记在最优里,现在拿这套新选法重新逐行判定。
13第 0 行覆盖第 0 行一个 1 都没有,天然被覆盖,整行标绿,覆盖数记到 1。
14第 1 行覆盖第 1 行需要第0列第2列,这些列全在选中的第0列第2列里,所有 1 都变绿被罩住,这行覆盖,覆盖数记到 2。
15第 2 行漏了第 2 行需要第1列第2列,可是第1列没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 2。
16第 3 行覆盖第 3 行需要第2列,这些列全在选中的第0列第2列里,所有 1 都变绿被罩住,这行覆盖,覆盖数记到 3。
17目前最优 3 行这种选法覆盖了 3 行,比之前的最优还多,把最优刷新到 3。选到这套列,收获明显更大。
18开始判定第1列第2列换第三种选法,这回选中第1列第2列,把它们整列染成琥珀色。前一种选法的结果先记在最优里,现在拿这套新选法重新逐行判定。
19第 0 行覆盖第 0 行一个 1 都没有,天然被覆盖,整行标绿,覆盖数记到 1。
20第 1 行漏了第 1 行需要第0列第2列,可是第0列没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 1。
21第 2 行覆盖第 2 行需要第1列第2列,这些列全在选中的第1列第2列里,所有 1 都变绿被罩住,这行覆盖,覆盖数记到 2。
22第 3 行覆盖第 3 行需要第2列,这些列全在选中的第1列第2列里,所有 1 都变绿被罩住,这行覆盖,覆盖数记到 3。
23目前最优 3 行这种选法覆盖了 3 行,和之前的最优打平,没有超过,最优保持 3,不更新。
24答案 = 3三种选法全试完了。选第 0 列和第 1 列只盖住 1 行;选第 0 列和第 2 列、以及选第 1 列和第 2 列,都能盖住 3 行。取最大,答案就是 3。这里定格在第 0 列和第 2 列这套:第 0 行空行绿、第 1 行两个 1 全绿、第 3 行的 1 也绿,三行齐了,只有第 2 行因为第 1 列没选而漏红。

⚠️ 容易写错的地方

✗ 错：把「选中列」理解成「这行至少有一个 1 在选中列里」

✓ 对：必须这行所有的 1 都在选中列里

覆盖的定义是行里每个 1 都被罩住,漏一个都不行,理解成「有一个就行」会把答案数大

✗ 错：忘了空行天然被覆盖

✓ 对：没有 1 的行,任何选法下都算被覆盖

空行的需求为空集,恒被满足,漏算它会让答案偏小

✗ 错：只挑 1 最多的那几列

✓ 对：必须枚举所有选法取最大

贪心挑热门列不一定最优,某些列虽然 1 少却是某行唯一的需求,列之间的组合关系只有枚举才看得全

✗ 错：numSelect 为 0 时不处理

✓ 对：选空集,只有空行被覆盖

选 0 列对应 pick 为 0,只有掩码为 0 的空行满足,按同一套逻辑自然成立,不必特判

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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 = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int maximumRows(vector<vector<int>>& matrix, int numSelect) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> masks;
        for (auto& row : matrix) {
            int mask = 0;
            for (int j = 0; j < n; ++j) if (row[j]) mask |= 1 << j;
            masks.push_back(mask);
        }
        int ans = 0;
        for (int pick = 0; pick < (1 << n); ++pick) if (__builtin_popcount((unsigned)pick) == numSelect) {
            int cur = 0;
            for (int mask : masks) if ((mask & pick) == mask) ++cur;
            ans = max(ans, cur);
        }
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int maximumRows(int[][] matrix, int numSelect) {
        int m = matrix.length, n = matrix[0].length;
        int[] masks = new int[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) if (matrix[i][j] == 1) masks[i] |= 1 << j;
        }
        int ans = 0;
        for (int pick = 0; pick < (1 << n); pick++) if (Integer.bitCount(pick) == numSelect) {
            int cur = 0;
            for (int mask : masks) if ((mask & pick) == mask) cur++;
            ans = Math.max(ans, cur);
        }
        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、计数都是常数几个变量,不随规模增长

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着被列覆盖的最多行数的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

这题的核心思路是什么?+

列数 n 很小,最多 12。把每行压成一个二进制掩码记录它的 1 在哪些列,然后枚举从 n 列里选 numSelect 列的每一种方案,对每种方案逐行判断:这行的掩码和选中列的掩码按位与之后是否还等于原掩码,等于就说明这行的 1 全被选中,计入覆盖。所有方案里覆盖行数的最大值就是答案。

为什么可以用枚举而不怕超时?+

因为约束里 m 和 n 都不超过 12。列子集最多 2 的 12 次方也就是 4096 个,每个再扫最多 12 行,总运算量在几万级别,非常小。数据规模小是这里能放心暴力枚举的关键信号。

为什么用位运算而不是集合?+

一行的列集合、一次选法的列集合,都可以用一个整数的二进制位表示,判断包含关系只需一次按位与再比较,是常数时间,比用哈希集合逐列比对快得多也省内存。位运算天然适合这种列数不大的子集枚举。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把被列覆盖的最多行数一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 2397中等回溯 · 枚举

被列覆盖的最多行数图解题解

这道题到底在问什么

输入: matrix=[[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect=2
输出: 3
输入: matrix=[[1],[0]], numSelect=1
输出: 2

最优解：一步一步想明白

3记牢这一句:一行被覆盖,等价于这行所有的 1 都躲在你选的列底下。空行没有 1,天然被覆盖。下面把 3 种选列方案一种一种试过去。
4目标:选 2 列覆盖最多行这就是我们的舞台:4 行 3 列,格子里写着 0 或 1。列从左到右编号 0、1、2。任务是从这 3 列里挑出 2 列,让被覆盖的行尽量多。先把每一行的 1 分布看清楚,下一帧我把每行需要哪些列标出来。
5橙格=这行的 1,绿行=空行把每行的 1 用橙色点亮,它们所在的列就是这行「需要」被选中的列。第 0 行没有 1,整行标绿,它谁都不挑剔、天生就被覆盖。第 1 行需要第 0 列和第 2 列,第 2 行需要第 1 列和第 2 列,第 3 行只需要第 2 列。接下来看哪种选法能满足最多的行。
6开始判定第0列第1列第一种选法,我们把第 0 列和第 1 列选中,这两整列染成琥珀色。选定之后,就该一行一行地问:这行的 1 是不是都被这两列罩住了。从第 0 行开始查。
7第 0 行覆盖第 0 行一个 1 都没有,天然被覆盖,整行标绿,覆盖数记到 1。
8第 1 行漏了第 1 行需要第0列第2列,可是第2列没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 1。
9第 2 行漏了第 2 行需要第1列第2列,可是第2列没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 1。
10第 3 行漏了第 3 行需要第2列,可是第2列没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 1。
11目前最优 1 行第一种选法查完:只有第 0 行那个空行被覆盖,其余三行都有 1 露在没选的列里,一共覆盖 1 行。这是第一手成绩,先把最优记成 1。
12开始判定第0列第2列换第二种选法,这回选中第0列第2列,把它们整列染成琥珀色。前一种选法的结果先记在最优里,现在拿这套新选法重新逐行判定。
13第 0 行覆盖第 0 行一个 1 都没有,天然被覆盖,整行标绿,覆盖数记到 1。
14第 1 行覆盖第 1 行需要第0列第2列,这些列全在选中的第0列第2列里,所有 1 都变绿被罩住,这行覆盖,覆盖数记到 2。
15第 2 行漏了第 2 行需要第1列第2列,可是第1列没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 2。
16第 3 行覆盖第 3 行需要第2列,这些列全在选中的第0列第2列里,所有 1 都变绿被罩住,这行覆盖,覆盖数记到 3。
17目前最优 3 行这种选法覆盖了 3 行,比之前的最优还多,把最优刷新到 3。选到这套列,收获明显更大。
18开始判定第1列第2列换第三种选法,这回选中第1列第2列,把它们整列染成琥珀色。前一种选法的结果先记在最优里,现在拿这套新选法重新逐行判定。
19第 0 行覆盖第 0 行一个 1 都没有,天然被覆盖,整行标绿,覆盖数记到 1。
20第 1 行漏了第 1 行需要第0列第2列,可是第0列没被选中,那里的 1 露在外面变红,只要漏一个,这行就不算覆盖,覆盖数还是 1。
21第 2 行覆盖第 2 行需要第1列第2列,这些列全在选中的第1列第2列里,所有 1 都变绿被罩住,这行覆盖,覆盖数记到 2。
22第 3 行覆盖第 3 行需要第2列,这些列全在选中的第1列第2列里,所有 1 都变绿被罩住,这行覆盖,覆盖数记到 3。
23目前最优 3 行这种选法覆盖了 3 行,和之前的最优打平,没有超过,最优保持 3,不更新。
24答案 = 3三种选法全试完了。选第 0 列和第 1 列只盖住 1 行;选第 0 列和第 2 列、以及选第 1 列和第 2 列,都能盖住 3 行。取最大,答案就是 3。这里定格在第 0 列和第 2 列这套:第 0 行空行绿、第 1 行两个 1 全绿、第 3 行的 1 也绿,三行齐了,只有第 2 行因为第 1 列没选而漏红。

⚠️ 容易写错的地方

✗ 错：把「选中列」理解成「这行至少有一个 1 在选中列里」

✓ 对：必须这行所有的 1 都在选中列里

覆盖的定义是行里每个 1 都被罩住,漏一个都不行,理解成「有一个就行」会把答案数大

✗ 错：忘了空行天然被覆盖

✓ 对：没有 1 的行,任何选法下都算被覆盖

空行的需求为空集,恒被满足,漏算它会让答案偏小

✗ 错：只挑 1 最多的那几列

✓ 对：必须枚举所有选法取最大

贪心挑热门列不一定最优,某些列虽然 1 少却是某行唯一的需求,列之间的组合关系只有枚举才看得全

✗ 错：numSelect 为 0 时不处理

✓ 对：选空集,只有空行被覆盖

选 0 列对应 pick 为 0,只有掩码为 0 的空行满足,按同一套逻辑自然成立,不必特判

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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 = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int maximumRows(vector<vector<int>>& matrix, int numSelect) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> masks;
        for (auto& row : matrix) {
            int mask = 0;
            for (int j = 0; j < n; ++j) if (row[j]) mask |= 1 << j;
            masks.push_back(mask);
        }
        int ans = 0;
        for (int pick = 0; pick < (1 << n); ++pick) if (__builtin_popcount((unsigned)pick) == numSelect) {
            int cur = 0;
            for (int mask : masks) if ((mask & pick) == mask) ++cur;
            ans = max(ans, cur);
        }
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int maximumRows(int[][] matrix, int numSelect) {
        int m = matrix.length, n = matrix[0].length;
        int[] masks = new int[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) if (matrix[i][j] == 1) masks[i] |= 1 << j;
        }
        int ans = 0;
        for (int pick = 0; pick < (1 << n); pick++) if (Integer.bitCount(pick) == numSelect) {
            int cur = 0;
            for (int mask : masks) if ((mask & pick) == mask) cur++;
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}

复杂度

时间

O(m·n + m·2ⁿ)

空间

O(m)

按峰值算。只额外存了 m 个行掩码,是 O(m)。枚举时的 pick、计数都是常数几个变量,不随规模增长

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着被列覆盖的最多行数的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

这题的核心思路是什么?+

为什么可以用枚举而不怕超时?+

为什么用位运算而不是集合?+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

被列覆盖的最多行数 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

被列覆盖的最多行数 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

被列覆盖的最多行数图解题解

被列覆盖的最多行数图解题解