【力扣每日一题】力扣2397被列覆盖的最多行数

题目

题源

力扣2397被覆盖的最多行数

题目概述

即给出一个由0，1组成的二维数组matrix，如

0,0,0

1,0,1

0,1,1

0,0,1

并给出我们需要选中的列数numSelect,如

numSelect = 2

我们需要选中一个列集合{列号a,列号b}，使行最多的被覆盖。

行被覆盖的定义：该行的所有1元素都在列号a和列号b中，或者该行为全0。

如：根据上述例子我们选出列集合{0,2}或{1,2}

{0,2}集合覆盖了行0,1,3? {1,2}集合覆盖了行0,2,3

返回被覆盖的行数3。

思路分析

一开始实在想不出什么好办法,采用了暴力解析的方式,代码非常复杂,后来看了解析才知道原来这么简单：

1. 由于每一行都是由至多12个0或1组成，可以把每一行都看作是一个二进制数a；
2. 选中的行使用1表示，未选中的行使用0表示，可以得到另一个二进制数b;
3. 当a&b=b时表示这一行被全覆盖了；
4. 保存被覆盖的最大值。

代码实现

java实现

public class Solution {
    public int maximumRows(int[][] matrix, int numSelect) {
        // 行数
        int maxRow = matrix.length;
        // 列数
        int maxCol = matrix[0].length;
        if (maxCol == 1) {
            return maxRow;
        }
        // 把每行都看作二进制数据
        int[] bitArray = new int[maxRow];
        for (int i = 0; i < maxRow; i++){
            for (int j = 0; j < maxCol; j++) {
                bitArray[i] += matrix[i][j] << (maxCol - j - 1);
            }
        }

        // 结果
        int result = 0;
        // 一共有maxCol个bit位
        int limit = 1 << maxCol;
        // 当前选中的列 如：1转为二进制为0001b，表示只选中了最后一列
        int current = 0;
        for (int i = 0; i < numSelect; i++) {
            current+= (1 <<i);
        }
        while(current < limit) {
            // 不需要考虑列数与要求不符合的情况
            if (Integer.bitCount(current) != numSelect) {
                current++;
                continue;
            }
            // 当某一行的二进制表示与当前选中的列数相与结果不变，即当前列的全部1元素被选中列数覆盖
            // （若该行的二进制表示某一位为1，而这一行未被选中即current该位为0，1 & 0结果为0）
            // （若该行的二进制表示某一位为0，而这一行未被选中即current该位为0，0 & 0结果为0）
            // （若该行的二进制表示某一位为1，而这一行被选中即current该位为1，1 & 1结果为1）
            // （若该行的二进制表示某一位为0，而这一行被选中即current该位为1，0 & 1结果为0）
            int temp = 0;
            for (int i = 0; i < maxRow; i++) {
                if ((current & bitArray[i]) == bitArray[i]) {
                    temp++;
                }
            }
            result = result > temp ? result : temp;
            current++;
        }
        return result;
    }
}

c++实现

class Solution {
public:
    // 计算当前值选中了几列
    int coutBit(int num) {
        int i = 0;
        while (num > 0) {
            i += num % 2;
            num /= 2;
        }
        return i;
    }
    int maximumRows(vector<vector<int>>& matrix, int numSelect) {
        int maxRow = matrix.size();
        int maxCol = matrix[0].size();

        // 每一行转为二进制数
        int* bitArray = new int[maxRow] {0};
        for (int i = 0; i < maxRow; i++) {
            for (int j = 0; j < maxCol; j++) {
                int t = matrix[i][j] << (maxCol - j - 1);
                bitArray[i] += t;
            }
        }
        int result = 0;
        int limit = 1 << maxCol;
        int current = 0;
        for (int i = 0; i < numSelect; i++) {
            current += (1 << i);
        }
        while (current < limit) {
            // 选中行数不符跳过
            if (coutBit(current) != numSelect) {
                current++;
                continue;
            }
            // 当某一行的二进制表示与当前选中的列数相与结果不变，即当前列的全部1元素被选中列数覆盖
            // （若该行的二进制表示某一位为1，而这一行未被选中即current该位为0，1 & 0结果为0）
            // （若该行的二进制表示某一位为0，而这一行未被选中即current该位为0，0 & 0结果为0）
            // （若该行的二进制表示某一位为1，而这一行被选中即current该位为1，1 & 1结果为1）
            // （若该行的二进制表示某一位为0，而这一行被选中即current该位为1，0 & 1结果为0）
            int temp = 0;
            for (int i = 0; i < maxRow; i++) {
                if ((bitArray[i] & current) == bitArray[i]){
                    temp++;
                }
            }
            result = temp > result ? temp : result;
            current++;
        }
        return result;
    }
};