银行中的激光束数量

难度: Medium

银行内部的防盗安全装置已经激活。给你一个下标从 0 开始的二进制字符串数组 bank ，表示银行的平面图，这是一个大小为 m x n 的二维矩阵。 bank[i] 表示第 i 行的设备分布，由若干 '0' 和若干 '1' 组成。'0' 表示单元格是空的，而 '1' 表示单元格有一个安全设备。

对任意两个安全设备而言，如果同时满足下面两个条件，则二者之间存在一个激光束：

两个设备位于两个 不同行 ：r₁ 和 r₂ ，其中 r₁ < r₂ 。
满足 r₁ < i < r₂ 的所有行 i ，都 没有安全设备 。

激光束是独立的，也就是说，一个激光束既不会干扰另一个激光束，也不会与另一个激光束合并成一束。

返回银行中激光束的总数量。

示例 1：

输入：bank = ["011001","000000","010100","001000"]
输出：8
解释：在下面每组设备对之间，存在一条激光束。总共是 8 条激光束：
 * bank[0][1] -- bank[2][1]
 * bank[0][1] -- bank[2][3]
 * bank[0][2] -- bank[2][1]
 * bank[0][2] -- bank[2][3]
 * bank[0][5] -- bank[2][1]
 * bank[0][5] -- bank[2][3]
 * bank[2][1] -- bank[3][2]
 * bank[2][3] -- bank[3][2]
注意，第 0 行和第 3 行上的设备之间不存在激光束。
这是因为第 2 行存在安全设备，这不满足第 2 个条件。

示例 2：

输入：bank = ["000","111","000"]
输出：0
解释：不存在两个位于不同行的设备

提示：

m == bank.length
n == bank[i].length
1 <= m, n <= 500
bank[i][j] 为 '0' 或 '1'

Submission

运行时间: 28 ms

内存: 18.4 MB

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        ans = 0
        prevCnt = 0
        for row in bank:
            if '1' not in row:
                continue
            cnt = row.count('1')
            ans += prevCnt * cnt
            prevCnt = cnt
        
        return ans

Explain

这个题解的核心思想是利用一次遍历来计算行与行之间可能形成的激光束数量。对于每一行，首先检查该行是否包含安全设备（即包含'1'）。如果这一行有安全设备，计算这一行的设备数量。然后，将这个数量与前一次记录的行的设备数量相乘，得到的结果就是这两行之间的激光束数量。将这个数量累加到答案中，并更新前一行设备数量的记录。这样，通过一次遍历即可计算出所有可能的激光束数量。

时间复杂度: O(m*n)

空间复杂度: O(1)

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        ans = 0  # 初始化激光束总数
        prevCnt = 0  # 上一行有设备的行的设备数量
        for row in bank:  # 遍历每一行
            if '1' not in row:  # 如果这一行没有设备，跳过
                continue
            cnt = row.count('1')  # 计算当前行的设备数量
            ans += prevCnt * cnt  # 当前行和上一有设备行之间的激光束数量
            prevCnt = cnt  # 更新上一有设备行为当前行
        
        return ans  # 返回激光束的总数量

Explore

是的，题解中的方法确实考虑了两行之间可能存在多行没有设备的情况。在算法实现中，只有当前行包含设备（即包含'1'）时，才会计算与上一行设备行之间的激光束数量，并更新`prevCnt`为当前行的设备数量。如果中间有多行没有设备，这些行会被跳过，不会影响`prevCnt`的值。因此，`prevCnt`始终记录的是最近的一行有设备的行的设备数量，确保了只计算有设备的两行之间的激光束。

在题解的代码中，如果连续多行没有设备，变量`prevCnt`的值不会发生变化。这是因为代码中只有在当前行有设备时，才会更新`prevCnt`的值。连续的空行（没有设备的行）会被跳过，不会进行任何操作，因此`prevCnt`会保持为最后一个有设备的行的设备数量。这种处理方式确保了不会错误地计算不存在的激光束，也不会影响最终的激光束计算结果。

确实如此，题解中提到的算法会自动处理并忽略所有没有设备的中间行。这是通过检查每行是否包含'1'来实现的。只有当行包含'1'时，该行才会被考虑用于计算激光束数量。这样算法自动忽略了所有空行，确保只计算两个有设备的行之间的激光束数量。

当所有行都没有设备时，由于没有行会被计算，`prevCnt`始终为0，因此算法的输出为0。同样，如果只有一行有设备，由于没有其他行与之计算激光束，`prevCnt`也只会被更新一次但不会与另一行相乘，所以输出同样为0。这种输出是合理的，因为没有足够的行来形成激光束，所以激光束的数量应该为0。