【算法】【哈希表,回溯,位运算】力扣2397. 被列覆盖的最多行数

2024-01-07 22:25:48

2397. 被列覆盖的最多行数


【算法】【哈希表,回溯,位运算】力扣2397. 被列覆盖的最多行数

题目描述

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

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

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

  1. 对于满足 matrix[row][col] == 1 的每个单元格 matrix[row][col](0 <= col <= n - 1),col 均存在于 s 中,或者
  2. 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 行。

示例 2:

输入:

matrix = [[1],[0]]
numSelect = 1

输出:2

解释:
选择唯一的一列,两行都被覆盖了,因为整个矩阵都被覆盖了。所以我们返回 2。

解决方案1(哈希表回溯)

预处理

我们可以创建一个哈希表 rows_in_cols_with_one,预先记录下每一列的哪一行上有 1;再用哈希表 one_rows 记录每一行有多少个 1。

from collections import defaultdict, Counter
from typing import List

class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        m, n = len(matrix), len(matrix[0])
        rows_have_one = defaultdict(set)
        ones_in_rows = [0] * m
        for ri, row_ele in enumerate(matrix):
            for ci, col_ele in enumerate(row_ele):
                if col_ele == 1:
                    rows_have_one[ci].add(ri)
                    ones_in_rows[ri] += 1

回溯

如果选择了一列,那么就找到对应的有 1 的行,将对应的行的 1 的个数减一。撤回操作中,将对应的行曾经减去的 1 都加回来。

		# 初始答案为:原来就没有1的行的个数
        ans = 0
        for row_one in ones_in_rows:
            if row_one == 0:
                ans += 1
    
        def backtrack(col_idx, cov_cnt, rest_sele_num):
            if rest_sele_num == 0:  # 没得选,直接进行更新
                nonlocal ans
                ans = max(ans, cov_cnt)
                return
            if col_idx == n:  # 超出最大列,无法枚举其它列
                return

            # 选这一列
            for next_col in range(col_idx, n):
                new_cov = 0
                rows = rows_have_one[next_col]
                row_change = Counter()
                # 遍历当前的列对应的行,更新选择后的效果
                for ri in rows:
                    ones_in_rows[ri] -= 1
                    row_change[ri] += 1
                    if ones_in_rows[ri] == 0:
                        new_cov += 1
                backtrack(next_col + 1, cov_cnt + new_cov, rest_sele_num - 1)
                # 撤回对这一列的选择
                for ri, cha in row_change.items():
                    ones_in_rows[ri] += cha

        backtrack(0, ans, numSelect)
        return ans

解决方案1完整代码

class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        m, n = len(matrix), len(matrix[0])
        rows_have_one = defaultdict(set)
        ones_in_rows = [0] * m
        for ri, row_ele in enumerate(matrix):
            for ci, col_ele in enumerate(row_ele):
                if col_ele == 1:
                    # 如果 matrix[ri][ci] 为 1 说明该列对应的行有 1
                    # 记录在该列对应的行中
                    rows_have_one[ci].add(ri)
                    # 记录在该行上的 1 的个数中。
                    ones_in_rows[ri] += 1

        ans = 0
        for row_one in ones_in_rows:
            if row_one == 0:
                ans += 1

        def backtrack(col_idx, cov_cnt, rest_sele_num):
            if rest_sele_num == 0:  # 没得选,直接进行更新
                nonlocal ans
                ans = max(ans, cov_cnt)
                return
            if col_idx == n:  # 超出最大列,无法枚举其它列
                return

            # 选这一列
            for next_col in range(col_idx, n):
                new_cov = 0
                rows = rows_have_one[next_col]
                row_change = Counter()
                # 遍历当前的列对应的行,更新选择后的效果
                for ri in rows:
                    ones_in_rows[ri] -= 1
                    row_change[ri] += 1
                    if ones_in_rows[ri] == 0:
                        new_cov += 1
                backtrack(next_col + 1, cov_cnt + new_cov, rest_sele_num - 1)
                # 撤回对这一列的选择
                for ri, cha in row_change.items():
                    ones_in_rows[ri] += cha

        backtrack(0, ans, numSelect)
        return ans

解决方案2(位运算回溯)

我们可以利用位运算进行解决。把每一行抽象成一个二进制数字,把列的集合 s 抽象成一个二进制数字。现在我们只需要将每一行的二进制表示记录在数组 masks 中即可。

例子

那么,现在举个例子:
假设矩阵有3行3列,最开始的时候,s = 000,代表没有选择任何列
矩阵表示为:

000
010
001
  • 我们拿出 010 这一行,将它的二进制表示赋值给变量 m ,此时m = 2,也就是二进制的 010
  • 在选择第二列后,有s = 2,即二进制的 010

虽然变量 m 代表 010 这一行,变量 s 代表所选择的列,似乎行和列不一样。

但此时,只要知道变量 s 二进制表示中的 1 与变量 m 二进制表示中的 1 重合,那就说明,我们现在所选择的列可以使得这一行被覆盖了。

如何计算当前行是否被覆盖?

上文可知,关键在于变量 s 二进制表示中的 1 与变量 m 二进制表示中的 1 是否重合,现有如下两种方法。

  • 朴素方法:用for循环进行逐个位上的比较
  • 位运算方法:我们只需要知道 m & ~s 是否为0,如果为0,代表 m 中的 1 都被覆盖
    本文使用的是位运算方法

预处理

class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        m, n = len(matrix), len(matrix[0])
        masks = [0] * m
        for ri, row_ele in enumerate(matrix):
            for ci, col_ele in enumerate(row_ele):
                # 记录第ri行的第ci列上的值
                masks[ri] |= (col_ele << ci)
                
        ans = 0

回溯

回溯的过程与解决方案1类似,但是利用位运算后性能约为解决方案1的两倍,因为不需要对哈希表进行反复修改。

        def backtrack(numSelect: int, idx: int, s: int):
            nonlocal ans
            if numSelect == 0:
                cover_rows = 0
                for m in masks:
                    # m代表每一行的二进制数,
                    # 如果 m & ~s结果为0,说明:
                    # m的二进制表示中的 1 ,也就是个一行上的 1 ,
                    # 都被选择的列给消除了。
                    is_no_one = True if m & ~s == 0 else False
                    cover_rows += is_no_one

                ans = max(ans, cover_rows)
            if idx == n:
                return 
            backtrack(numSelect, idx + 1, s)      # 不选当前列
            s |= (1 << idx)                 # 选择当前列
            backtrack(numSelect - 1, idx + 1, s)  # 选择当前列后再次递归。
        backtrack(numSelect, 0, 0)
        return ans

解决方案2完整代码

class Solution:
    def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
        m, n = len(matrix), len(matrix[0])
        masks = [0] * m
        for ri, row_ele in enumerate(matrix):
            for ci, col_ele in enumerate(row_ele):
                masks[ri] |= (col_ele << ci) # 记录第ri行的第ci列上的值
        ans = 0
        def backtrack(numSelect: int, idx: int, s: int):
            nonlocal ans
            if numSelect == 0:
                cover_rows = 0
                for m in masks:
                    # m代表每一行的二进制数,
                    # 如果 m & ~s结果为0,说明:
                    # m的二进制表示中的 1 ,也就是个一行上的 1 ,
                    # 都被选择的列给消除了。
                    is_no_one = True if m & ~s == 0 else False
                    cover_rows += is_no_one

                ans = max(ans, cover_rows)
            if idx == n:
                return 
            backtrack(numSelect, idx + 1, s)      # 不选当前列
            s |= (1 << idx)                 # 选择当前列
            backtrack(numSelect - 1, idx + 1, s)  # 选择当前列后再次递归。
        backtrack(numSelect, 0, 0)
        return ans

文章来源:https://blog.csdn.net/weixin_73108148/article/details/135383921
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。