角矩形的数量

Submission

运行时间: 77 ms

内存: 17.2 MB

class Solution:
    def countCornerRectangles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        allMask = res = 0
        masks = [0]*m
        for r, row in enumerate(grid):
            mask = temp = sum(1<<i for i, v in enumerate(row) if v)
            temp &= allMask
            res += sum(comb((m&temp).bit_count(), 2) for m in masks[:r])
            allMask |= mask
            masks[r] = mask
        return res

Explain

该题解使用了位运算和组合计数的思路。首先对每一行进行预处理，用一个整数 mask 记录该行哪些位置是1。然后利用位与运算，对于当前行 r，计算它与之前每一行 masks[i] (0<=i<r) 的公共1的位置，再利用组合计数，计算出当前行与第i行可以组成的角矩形数量，累加到答案中。最终得到全部的角矩形数量。

时间复杂度: O(m^2)

空间复杂度: O(m)

class Solution:
    def countCornerRectangles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        allMask = res = 0
        masks = [0]*m
        for r, row in enumerate(grid):
            # 计算当前行的掩码 mask，并更新到 allMask 中
            mask = temp = sum(1<<i for i, v in enumerate(row) if v) 
            # temp 保存了当前行与全局 allMask 的公共 1 的位置
            temp &= allMask
            # 统计当前行与之前每一行的角矩形数量
            res += sum(comb((m&temp).bit_count(), 2) for m in masks[:r])
            allMask |= mask
            masks[r] = mask
        return res

Explore

使用整数掩码表示行中1的位置而不是使用行数组本身，主要是出于效率和空间优化的考虑。整数掩码可以将一行中的信息压缩到一个整数中，这样可以极大地减少数据处理的空间复杂度，特别是在行宽较小于整数位数（如32位或64位）的情况下。此外，整数运算（如位与、位或和位计数）通常比数组操作更快，这使得在算法中使用位运算处理掩码比逐个检查数组元素更有效率。

利用位与运算来找出两行之间共同的1的位置虽然在许多情况下都很有效，但在矩阵的宽度非常大时，特别是超过常规整数位数（如32位或64位）的情况下，可能会遇到性能瓶颈。在这种情况下，每行的掩码可能需要多个整数来表示，增加了位运算的复杂度和处理时间。此外，如果矩阵中1的密度非常高，位运算操作的结果仍然是较大的数，这意味着后续的计算，如位计数，需要更多时间来处理更多的1位，也可能导致效率降低。

在计算角矩形时，每一对公共1的位置（即同列的两个1）都可以看作是矩形的两个角。因此，问题转化为在每对行的交集中找到所有可能的1对的组合。组合计数公式`C(n, 2)`，即从n个元素中选择2个的方式数，正好用于计算这种情况。这是因为每两个公共1的位置可以唯一确定一个角矩形。因此，对于每一对行，我们只需要计算其交集中1的个数，然后使用组合公式来计算这些1可以组成多少个矩形。

在算法中，`temp &= allMask`操作用于限制`temp`仅包含到当前行为止所有行中共同存在的1的位置。`allMask`是一个累积的掩码，它通过位或操作`|=`跟踪了到当前行为止，哪些列至少有一个1。这样，使用`temp &= allMask`确保我们只考虑那些在之前至少出现过一次的列，这有助于减少后续运算的不必要计算，优化整体的计算效率。通过这种方式，我们可以快速且准确地找到两个行之间可能形成角矩形的列对，提升算法性能。