原题链接:
https://leetcode.cn/problems/maximum-rows-covered-by-columns/
枚举题 基础做法很简单 枚举出所有可选列的组合 模拟题意操作一遍 然后返回结果即可

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution:
    """
    先枚举出出所有列==cols的可能组合
    然后再按照枚举结果 将所有列覆盖 然后返回结果
    """

    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:

        m = len(matrix)
        n = len(matrix[0])
        h = []

        # 当前所选择的列 所选的列数总和
        def dfs(c: int, total: int, s: list):
            if total == numSelect:
                h.append(list(s))
                return

            if c < 0 or c >= n:
                return
            # 不取当前的c 直接下一层dfs
            dfs(c + 1, total, s)
            s.append(c)
            # 取当前的c total+1 然后下一层
            dfs(c + 1, total + 1, s)
            s.remove(c)

        dfs(0, 0, [])

        # 计算被覆盖的行数
        def countAns():
            res = 0
            for i in range(m):
                flag = True
                for j in range(n):
                    if matrix[i][j] == 1:
                        flag = False
                        break
                res = res + flag
            return res

        ans = 0
		# 这里注意一定要用深拷贝
		# python数组都是地址调用 否则后续对martrix的修改会直接影响到back数组 这样对martix进行备份也就没有意义了
        back = copy.deepcopy(matrix)

        # 然后根据所有 枚举出来的列的组合进行模拟
        for arr in h:
            for c in arr:
                for i in range(m):
                    matrix[i][c] = 0
            ans = max(ans, countAns())
			# 这里用深拷贝的原因与之前相同
            matrix = copy.deepcopy(back)
        return ans

优化1:
上述思路在最后判断答案时使用了深拷贝进行模拟后然后枚举答案
在这一步可以优化一下
对于任意一种列组合的情况下遍历矩阵时 假设i行j列为1 那么我们只需要判断 这个当前的第j行 是否处于我们当前所枚举的列组合之中即可 如果存在则证明这个1 是可以被覆盖
优化代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
      ans = 0
# 枚举所有列的组合
      for arr in h:
          tmp = 0
          for i in range(m):
              flag = True
              for j in range(n):
			# 对每行元素进行判断 如果当前列为1 且当前列并在枚举的列的集合 
			# flag置为false 即该行没有被覆盖
                  if matrix[i][j] == 1 and arr.count(j) == 0:
                      flag = False
                      break
              tmp = tmp + flag
          ans = max(ans, tmp)

优化2:
在上一步的基础我们可以继续进行优化 之前我们采用枚举策略是直接枚举矩阵元素
但我们可以考虑用二进制的方式代表集合
二进制的第i位为1表示i在集合中 为0表示i不在集合中
这样可以用二进制枚举集合 同时把mat的每一行也用二进制表示 从而做到O(1)判断行中的所有1是否被覆盖
优化代码:

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
class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        m, n = len(matrix), len(matrix[0])
        # 用于代表原矩阵
        # i行 其中二进制 就代表原矩阵的0 1分布
        arr = m * [0]

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 1:
                    # 第i行 第j列为1 则直接mask[i] | 2^j-1 即将mask[i]的第j位置为1
                    arr[i] |= 1 << j

        # 一共n列
        h = 1 << n

        ans = 0

        # 枚举所有列选举的方案
        for s in range(h):
            # 如果当前枚举的方案中的列数符合题目要求 则进行判断
            if s.bit_count() == numSelect:
                tmp = 0
                for row in arr:
                    # 如果row为s的子集 即代表row中1 都可以被枚举方案s 中的列覆盖
                    if row & s == row:
                        tmp = tmp + 1
                ans = max(ans, tmp)

        return ans