LeetCode每日一题(2397. Maximum Rows Covered by Columns)

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

---

想起来容易写起来难， 很容易想到用 bit mask 来解这个问题， 每一行作为一个数， 我们把我们选择的列所对应的位置 0， 如果结果是 0， 那这行就是被覆盖了。 一开始的思路是， 遍历从 0 到 1 << matrix[0].len(), 如果数字中 0 的数量等于 numSelect 我们就检查当前数字 n 与 matrix 中每一行的数字进行 bit and 操作的结果， 如果为 0，则证明可以覆盖此行。但是这里有个前置 0 的问题， 我们没法数前置的 0， 所以我们还需要进行一次曲线救国， 我们从数 0 改为数 1， 只要 1 的数量跟 numSelect 相等即可， 然后我们用一个全为 1 的 mask 与 n 做 xor 操作， 这样我们等于把每一位做翻转，刚才是 1 的位现在全部变为 0 了， 这样就达到了我们开始设想的效果。

---

impl Solution {
    fn to_int(row: &Vec<i32>) -> i32 {
        row.into_iter().fold(0, |mut s, &v| {
            s *= 2;
            s += v;
            s
        })
    }
    fn check_ones(mut num: i32, ones: i32) -> bool {
        let mut count = 0;
        while num > 0 {
            count += num & 1;
            num = num >> 1;
        }
        count == ones
    }
    pub fn maximum_rows(matrix: Vec<Vec<i32>>, num_select: i32) -> i32 {
        let nums: Vec<i32> = matrix.iter().map(|l| Solution::to_int(l)).collect();
        let mut ans = 0;
        let mask = (1 << matrix[0].len()) - 1;
        for mut n in 0..1 << matrix[0].len() {
            if Solution::check_ones(n, num_select) {
                n ^= mask;
                let mut c = 0;
                for &t in &nums {
                    if n & t == 0 {
                        c += 1;
                    }
                }
                ans = ans.max(c);
            }
        }
        ans
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36