Skip to content

Latest commit

 

History

History
256 lines (212 loc) · 7.76 KB

File metadata and controls

256 lines (212 loc) · 7.76 KB
comments difficulty edit_url rating source tags
true
中等
1718
第 86 场双周赛 Q3
位运算
数组
回溯
枚举
矩阵

English Version

题目描述

给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix ;另给你一个整数 numSelect,表示你必须从 matrix 中选择的 不同 列的数量。

如果一行中所有的 1 都被你选中的列所覆盖,则认为这一行被 覆盖 了。

形式上,假设 s = {c1, c2, ...., cnumSelect} 是你选择的列的集合。对于矩阵中的某一行 row ,如果满足下述条件,则认为这一行被集合 s 覆盖

  • 对于满足 matrix[row][col] == 1 的每个单元格 matrix[row][col]0 <= col <= n - 1),col 均存在于 s 中,或者
  • row不存在 值为 1 的单元格。

你需要从矩阵中选出 numSelect 个列,使集合覆盖的行数最大化。

返回一个整数,表示可以由 numSelect 列构成的集合 覆盖最大行数

 

示例 1:

输入:matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2
输出:3
解释:
图示中显示了一种覆盖 3 行的可行办法。
选择 s = {0, 2} 。
- 第 0 行被覆盖,因为其中没有出现 1 。
- 第 1 行被覆盖,因为值为 1 的两列(即 0 和 2)均存在于 s 中。
- 第 2 行未被覆盖,因为 matrix[2][1] == 1 但是 1 未存在于 s 中。
- 第 3 行被覆盖,因为 matrix[2][2] == 1 且 2 存在于 s 中。
因此,可以覆盖 3 行。
另外 s = {1, 2} 也可以覆盖 3 行,但可以证明无法覆盖更多行。

示例 2:

输入:matrix = [[1],[0]], numSelect = 1
输出:2
解释:
选择唯一的一列,两行都被覆盖了,因为整个矩阵都被覆盖了。
所以我们返回 2 。

 

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 12
  • matrix[i][j] 要么是 0 要么是 1
  • 1 <= numSelect <= n

解法

方法一:二进制枚举

我们先将矩阵中的每一行转换成一个二进制数,记录在数组 $rows$ 中,其中 $rows[i]$ 表示第 $i$ 行对应的二进制数,而 $rows[i]$ 这个二进制数的第 $j$ 位表示第 $i$ 行第 $j$ 列的值。

接下来,我们枚举所有的 $2^n$ 种列选择方案,其中 $n$ 为矩阵的列数。对于每一种列选择方案,我们判断是否选中了 numSelect 列,如果不是,则跳过。否则,我们统计矩阵中有多少行中的所有 $1$ 都被选中的列覆盖,即统计有多少行的二进制数 $rows[i]$ 与列选择方案 $mask$ 按位与的结果等于 $rows[i]$,并更新最大的行数。

时间复杂度 $O(2^n \times m)$,空间复杂度 $O(m)$。其中 $m$$n$ 分别为矩阵的行数和列数。

Python3

class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        rows = []
        for row in matrix:
            mask = reduce(or_, (1 << j for j, x in enumerate(row) if x), 0)
            rows.append(mask)

        ans = 0
        for mask in range(1 << len(matrix[0])):
            if mask.bit_count() != numSelect:
                continue
            t = sum((x & mask) == x for x in rows)
            ans = max(ans, t)
        return ans

Java

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

C++

class Solution {
public:
    int maximumRows(vector<vector<int>>& matrix, int numSelect) {
        int m = matrix.size(), n = matrix[0].size();
        int rows[m];
        memset(rows, 0, sizeof(rows));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j]) {
                    rows[i] |= 1 << j;
                }
            }
        }
        int ans = 0;
        for (int mask = 1; mask < 1 << n; ++mask) {
            if (__builtin_popcount(mask) != numSelect) {
                continue;
            }
            int t = 0;
            for (int x : rows) {
                t += (x & mask) == x;
            }
            ans = max(ans, t);
        }
        return ans;
    }
};

Go

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

TypeScript

function maximumRows(matrix: number[][], numSelect: number): number {
    const [m, n] = [matrix.length, matrix[0].length];
    const rows: number[] = Array(m).fill(0);
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (matrix[i][j]) {
                rows[i] |= 1 << j;
            }
        }
    }
    let ans = 0;
    for (let mask = 1; mask < 1 << n; ++mask) {
        if (bitCount(mask) !== numSelect) {
            continue;
        }
        let t = 0;
        for (const x of rows) {
            if ((x & mask) === x) {
                ++t;
            }
        }
        ans = Math.max(ans, t);
    }
    return ans;
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}