Leetcode 2397. Maximum Rows Covered by Columns

[Woodyiiiiiii]

这道题关键在于：如何从n列中随机选择numSelect列。

一开始我试图从1出现频率最大的一列开始，但显然这不对，因为如果频率相同，如何选择呢。

plus图中的constraint表明完全可以遍历所有可能。

所以要使用位运算，讲选中的一列置为1，然后按一行来形成数字。比如选中第0列和第2列，则数字显示为101；最大可能是2*n-1(1 << numSelect)，然后从0遍历，出现1的数字等于numSelect，则进行计算。

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

        int ans = 0;
        for (int i = 0; i < limit; ++i) {
            int k = 0;
            for (int j = 0; j < n; ++j) {
                if ((i & (1 << j)) != 0) {
                    ++k;
                }
            }
            if (k == numSelect) {
                int cnt = 0;
                for (int[] ints : matrix) {
                    boolean flag = true;
                    for (int j = 0; j < n; ++j) {
                        if ((i & (1 << j)) == 0 && ints[j] == 1) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        ++cnt;
                    }
                }
                ans = Math.max(ans, cnt);
            }
        }

        return ans;
    }

}

时间复杂度O(mnn)。

---

• https://leetcode.com/problems/maximum-rows-covered-by-columns/description/
• https://leetcode.com/problems/maximum-rows-covered-by-columns/solutions/2524684/check-all-subsets/