LeetCode每日一题 | 2397. 被列覆盖的最多行数

题目描述

原题链接

给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix ；另给你一个整数 numSelect，表示你必须从 matrix 中选择的 不同 列的数量。

如果一行中所有的 1 都被你选中的列所覆盖，则认为这一行被 覆盖 了。

形式上，假设 s = {c1, c2, …, cnumSelect} 是你选择的列的集合。对于矩阵中的某一行 row ，如果满足下述条件，则认为这一行被集合 s 覆盖：

对于满足 matrix[row][col] == 1 的每个单元格 matrix[row][col]（0 <= col <= n - 1），col 均存在于 s 中，或者
row 中 不存在 值为 1 的单元格。
你需要从矩阵中选出 numSelect 个列，使集合覆盖的行数最大化。

返回一个整数，表示可以由 numSelect 列构成的集合 覆盖 的 最大行数 。

问题分析

由于矩阵的列数小于等于12，因此我们可以将每一行的01值看作二进制表示的数，并将其转化为对应的十进制数。

借助Golang的bits.OnesCount函数，枚举选择列的全部情况i，通过i与每一行对应的十进制数（蕴含了二进制的信息），进行与操作，判断该行是否被覆盖。

最终，统计所有列情况对应的覆盖行数的最大值。

程序代码（Golang 版本）

func maximumRows(matrix [][]int, numSelect int) int {
   
    m := len(matrix)
    if m == 0 {
   
        return 0
    }
    n := len(matrix[0])
    if numSelect >= n {
   
        return m
    }
    // 将每一行的二进制数转换成十进制数
    nums := make([]int, m)
    for i := 0; i < m; i++ {
   
        for j := 0; j < n; j++ {
   
            nums[i] += matrix[i][j] << (n - j - 1)
        }
    }
    res, maxNum := 0, 1 << n
    for i := 1; i < maxNum; i++ {
   
        if bits.OnesCount(uint(i)) != numSelect {
   
            continue;
        }
        cnt := 0
        for j := 0; j < m; j++ {
   
            if (nums[j] & i) == nums[j] {
   
                cnt++;
            }
        }
        res = max(res, cnt)
    }
    return res
}