Medium

题目描述

给定一个 m x n 的二进制矩阵 matrix 和一个整数 numSelect。

你的目标是从矩阵中选择恰好 numSelect 个不同的列，使得覆盖的行数尽可能多。

如果一行中的所有 1 都位于你选择的列中，则该行被认为是被覆盖的。如果一行没有任何 1，它也被认为是被覆盖的。

更正式地，设我们考虑 selected = {c1, c2, ...., cnumSelect} 作为你选择的列的集合。行 i 被 selected 覆盖当且仅当：

  • 对于每个 matrix[i][j] == 1 的单元格，列 j 在 selected 中。
  • 或者，行 i 中没有值为 1 的单元格。

返回一组 numSelect 列可以覆盖的最大行数。

示例 1：

输入：matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2
输出：3
解释：覆盖 3 行的一种可能方法如图所示。
我们选择 s = {0, 2}。
- 行 0 被覆盖，因为它没有 1。
- 行 1 被覆盖，因为值为 1 的列（即 0 和 2）都在 s 中。
- 行 2 没有被覆盖，因为 matrix[2][1] == 1 但 1 不在 s 中。
- 行 3 被覆盖，因为 matrix[2][2] == 1 且 2 在 s 中。
因此，我们可以覆盖三行。

示例 2：

输入：matrix = [[1],[0]], numSelect = 1
输出：2
解释：选择唯一的列将导致两行都被覆盖，因为选择了整个矩阵。

约束条件：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 12
  • matrix[i][j] 是 0 或 1
  • 1 <= numSelect <= n

解题思路

这道题要求选择恰好 numSelect 个列来覆盖最多的行。我们需要理解"覆盖"的含义：一行被覆盖当且仅当该行中所有的 1 都位于我们选择的列中。

思路分析：

由于约束条件中 n <= 12，我们可以使用暴力枚举的方法。核心思路是枚举所有可能的列组合，对于每种组合计算能覆盖的行数，取最大值。

  1. 枚举方法：可以使用回溯法或位操作来枚举所有大小为 numSelect 的列组合
  2. 覆盖判断：对于每个选定的列组合，检查每一行是否被覆盖
  3. 优化思路：可以预处理每行的 1 位置，然后检查这些位置是否都在选定列中

具体实现：

  • 使用位掩码表示选择的列集合
  • 对每个可能的列组合，遍历所有行检查是否被覆盖
  • 一行被覆盖的条件：该行所有为 1 的位置对应的列都在选择的列集合中

时间复杂度为 O(C(n, numSelect) × m × n)，在给定约束下是可接受的。

代码实现

class Solution {
public:
    int maximumRows(vector<vector<int>>& matrix, int numSelect) {
        int m = matrix.size(), n = matrix[0].size();
        int maxCovered = 0;
        
        // 枚举所有可能的列组合
        function<void(int, int, int)> backtrack = [&](int start, int selected, int mask) {
            if (selected == numSelect) {
                // 计算当前列组合能覆盖多少行
                int covered = 0;
                for (int i = 0; i < m; i++) {
                    bool canCover = true;
                    for (int j = 0; j < n; j++) {
                        if (matrix[i][j] == 1 && !(mask & (1 << j))) {
                            canCover = false;
                            break;
                        }
                    }
                    if (canCover) covered++;
                }
                maxCovered = max(maxCovered, covered);
                return;
            }
            
            for (int i = start; i < n; i++) {
                backtrack(i + 1, selected + 1, mask | (1 << i));
            }
        };
        
        backtrack(0, 0, 0);
        return maxCovered;
    }
};

class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        m, n = len(matrix), len(matrix[0])
        max_covered = 0
        
        def backtrack(start, selected, mask):
            nonlocal max_covered
            
            if selected == numSelect:
                # 计算当前列组合能覆盖多少行
                covered = 0
                for i in range(m):
                    can_cover = True
                    for j in range(n):
                        if matrix[i][j] == 1 and not (mask & (1 << j)):
                            can_cover = False
                            break
                    if can_cover:
                        covered += 1
                max_covered = max(max_covered, covered)
                return
            
            for i in range(start, n):
                backtrack(i + 1, selected + 1, mask | (1 << i))
        
        backtrack(0, 0, 0)
        return max_covered

public class Solution {
    public int MaximumRows(int[][] matrix, int numSelect) {
        int m = matrix.Length, n = matrix[0].Length;
        int maxCovered = 0;
        
        void Backtrack(int start, int selected, int mask) {
            if (selected == numSelect) {
                // 计算当前列组合能覆盖多少行
                int covered = 0;
                for (int i = 0; i < m; i++) {
                    bool canCover = true;
                    for (int j = 0; j < n; j++) {
                        if (matrix[i][j] == 1 && (mask & (1 << j)) == 0) {
                            canCover = false;
                            break;
                        }
                    }
                    if (canCover) covered++;
                }
                maxCovered = Math.Max(maxCovered, covered);
                return;
            }
            
            for (int i = start; i < n; i++) {
                Backtrack(i + 1, selected + 1, mask | (1 << i));
            }
        }
        
        Backtrack(0, 0, 0);
        return maxCovered;
    }
}

/**
 * @param {number[][]} matrix
 * @param {number} numSelect
 * @return {number}
 */
var maximumRows = function(matrix, numSelect) {
    const m = matrix.length;
    const n = matrix[0].length;
    let maxRows = 0;
    
    function generateCombinations(start, selected, count) {
        if (count === numSelect) {
            let coveredRows = 0;
            for (let i = 0; i < m; i++) {
                let isCovered = true;
                for (let j = 0; j < n; j++) {
                    if (matrix[i][j] === 1 && !selected.has(j)) {
                        isCovered = false;
                        break;
                    }
                }
                if (isCovered) coveredRows++;
            }
            maxRows = Math.max(maxRows, coveredRows);
            return;
        }
        
        for (let i = start; i < n; i++) {
            selected.add(i);
            generateCombinations(i + 1, selected, count + 1);
            selected.delete(i);
        }
    }
    
    generateCombinations(0, new Set(), 0);
    return maxRows;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(C(n, numSelect) × m × n)，其中 C(n, numSelect) 是组合数，需要枚举所有可能的列组合，对每个组合检查所有行
空间复杂度O(numSelect)，递归调用栈的深度为 numSelect

相关题目