题目分析

本题是周赛的第三题，难度不大，算法思想也非常巧妙，看一下数据范围是否能相出算法？

状态压缩

行和列的范围都是12，因此我们可以暴力枚举，每一位都可以选择或者不选，共有2的n次方种方式，对于每种方式我们要筛选一下列数是否满足cols。

因为int可以表示32位的0和1，可以用int数字来表示每一位的状态，因此称之为状态压缩。

我们记选中的为0，对于某个满足的选择方式，可以表达为一个二进制数。原数组的每一行也可以表达一个二进制数，如果两个数想与等于0，说明原数组中的每一个1都被我们选择了。

算法的时间复杂度为$ O(n \times 2^n \times log(n)) $，空间复杂度为O(n)。

class Solution {
    public int maximumRows(int[][] mat, int cols) {
        int row = mat.length;
        int col = mat[0].length;
        int[] arr = new int[row];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (mat[i][j] == 1) {
                    arr[i] |= 1 << j;
                }
            }
        }
        int res = 0;
        for (int x = 0; x < (1 << col); x++) {
            if (getOne(x) == col - cols) {
                int cnt = 0;
                for (int i = 0; i < row; i++) {
                    if ((x & arr[i]) == 0) {
                        cnt++;
                    }
                }
                res = Math.max(res, cnt);
            }
        }
        return res;
    }

    private int getOne(int x) {
        int res = 0;
        while (x != 0) {
            x ^= (x & -x);
            res++;
        }
        return res;
    }
}

刷题总结

这种题目难度不大，但是需要对二进制的表示非常熟悉，因此小伙伴们要多加练习。