算法每日一题: 被列覆盖的最多行数 | 二进制 - 状态压缩

发布时间:2024年01月06日

大家好,我是星恒
今天的题目又是一道有关二进制的题目,有我们之前做的那道 参加考试的最大学生数的 感觉,哈哈,当然,比那道题简单多了,这道题感觉主要的考点就是二进制,大家可以好好总结一下这道题目!

题目: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 列构成的集合 覆盖最大行数
示例:
示例 1:
image.png

输入: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 中。
因此,可以覆盖 3 行。
另外 s = {1, 2} 也可以覆盖 3 行,但可以证明无法覆盖更多行。

示例 2:
image.png

输入:matrix = [[1],[0]], numSelect = 1
输出:2
解释:
选择唯一的一列,两行都被覆盖了,因为整个矩阵都被覆盖了。
所以我们返回 2 。

提示:

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

分析:
遇到这种m,n是比较小的题目,就很有可能是使用二进制来表示,我们先来看看这道题目吧!

这道题目我们最初的思想一定是枚举,将每种竖列的情况枚举出来,然后再将每种情况和每一行比较,看是否可以覆盖,接着计数,最后比较哪种情况最优

没错,我们的大体思路也是这样,但是当我们衡量竖列情况是否可以覆盖横行使,我们需要遍历每个横行的元素,这无疑使我们的复杂度多了一个n;但由于他们的元素都是0,1(或者可以用0,1表示),这时,我们就很容易想到位运算里面的“ | ” (或)运算,我们只要将数列情况和横行情况一位或,如果位或后值不变,这样我们就能确定他全覆盖了

题解:

class Solution {
    public int maximumRows(int[][] matrix, int numSelect) {
        int m = matrix.length;
        int n = matrix[0].length;

        // 将matrix的行用二进制表示
        int[] mask = new int[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                mask[i] += matrix[i][j] << (n - j - 1);
            }
        }
        int res = 0;
        int cur = 0;
        int limit = (1 << n);
        while (++cur < limit) {
            if (Integer.bitCount(cur) != numSelect) {
                continue;
            }
            int t = 0;
            for (int j = 0; j < m; j++) {
                if ((mask[j] & cur) == mask[j]) {
                    ++t;
                }
            }
            res = Math.max(res, t);
        }
        return res;
    }
}

注意:

  • Integer.bitCount(cur)统计数字cur里面有多少个1

如果大家有什么思考和问题,可以在评论区讨论,也可以私信我,很乐意为大家效劳。
好啦,今天的每日一题到这里就结束了,如果大家觉得有用,可以可以给我一个小小的赞呢,我们下期再见!

文章来源:https://blog.csdn.net/m0_61780691/article/details/135418797
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。