README_EN.md

2397. Maximum Rows Covered by Columns

中文文档

Description

You are given a 0-indexed m x n binary matrix matrix and an integer numSelect, which denotes the number of distinct columns you must select from matrix.

Let us consider s = {c1, c2, ...., cnumSelect} as the set of columns selected by you. A row row is covered by s if:

• For each cell matrix[row][col] (0 <= col <= n - 1) where matrix[row][col] == 1, col is present in s or,
• No cell in row has a value of 1.

You need to choose numSelect columns such that the number of rows that are covered is maximized.

Return the maximum number of rows that can be covered by a set of numSelect columns.

 

Example 1:

Input: matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2
Output: 3
Explanation: One possible way to cover 3 rows is shown in the diagram above.
We choose s = {0, 2}.
- Row 0 is covered because it has no occurrences of 1.
- Row 1 is covered because the columns with value 1, i.e. 0 and 2 are present in s.
- Row 2 is not covered because matrix[2][1] == 1 but 1 is not present in s.
- Row 3 is covered because matrix[2][2] == 1 and 2 is present in s.
Thus, we can cover three rows.
Note that s = {1, 2} will also cover 3 rows, but it can be shown that no more than three rows can be covered.

Example 2:

Input: matrix = [[1],[0]], numSelect = 1
Output: 2
Explanation: Selecting the only column will result in both rows being covered since the entire matrix is selected.
Therefore, we return 2.

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 12
• matrix[i][j] is either 0 or 1.
• 1 <= numSelect <= n

Solutions

Python3

class Solution:
    def maximumRows(self, mat: List[List[int]], cols: int) -> int:
        def dfs(mask, i):
            if i > n or mask.bit_count() > cols:
                return
            nonlocal ans
            if i == n:
                t = sum((v & mask) == v for v in arr)
                ans = max(ans, t)
                return
            dfs(mask, i + 1)
            dfs(mask | 1 << i, i + 1)

        arr = []
        ans, n = 0, len(mat[0])
        for i, row in enumerate(mat):
            x = 0
            for j, v in enumerate(row):
                x |= v << j
            arr.append(x)
        dfs(0, 0)
        return ans

class Solution:
    def maximumRows(self, mat: List[List[int]], cols: int) -> int:
        arr = []
        for i, row in enumerate(mat):
            x = 0
            for j, v in enumerate(row):
                x |= v << j
            arr.append(x)
        ans, n = 0, len(mat[0])
        for mask in range(1, 1 << n | 1):
            if mask.bit_count() > cols:
                continue
            t = sum((v & mask) == v for v in arr)
            ans = max(ans, t)
        return ans

Java

class Solution {
    private int ans;
    public int maximumRows(int[][] mat, int cols) {
        int m = mat.length, n = mat[0].length;
        int[] arr = new int[m];
        for (int i = 0; i < m; ++i) {
            int x = 0;
            for (int j = 0; j < n; ++j) {
                x |= mat[i][j] << j;
            }
            arr[i] = x;
        }
        int ans = 0;
        for (int mask = 1; mask <= 1 << n; ++mask) {
            if (Integer.bitCount(mask) > cols) {
                continue;
            }
            int t = 0;
            for (int v : arr) {
                if ((v & mask) == v) {
                    ++t;
                }
            }
            ans = Math.max(ans, t);
        }
        return ans;
    }
}

C++

class Solution {
public:
    int maximumRows(vector<vector<int>>& mat, int cols) {
        int m = mat.size(), n = mat[0].size();
        vector<int> arr(m);
        for (int i = 0; i < m; ++i) {
            int x = 0;
            for (int j = 0; j < n; ++j) x |= mat[i][j] << j;
            arr[i] = x;
        }
        int ans = 0;
        for (int mask = 1; mask <= 1 << n; ++mask) {
            if (__builtin_popcount(mask) > cols) continue;
            int t = 0;
            for (int v : arr) t += (v & mask) == v;
            ans = max(ans, t);
        }
        return ans;
    }
};

Go

func maximumRows(mat [][]int, cols int) int {
	m, n := len(mat), len(mat[0])
	arr := make([]int, m)
	for i, row := range mat {
		x := 0
		for j, v := range row {
			x |= v << j
		}
		arr[i] = x
	}
	ans := 0
	for mask := 1; mask <= 1<<n; mask++ {
		if bits.OnesCount(uint(mask)) != cols {
			continue
		}
		t := 0
		for _, v := range arr {
			if (v & mask) == v {
				t++
			}
		}
		ans = max(ans, t)
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

TypeScript

...