银行中的激光束数量

难度:

标签:

题目描述

银行内部的防盗安全装置已经激活。给你一个下标从 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'

代码结果

运行时间: 28 ms, 内存: 18.4 MB

/*
题目思路:
1. 使用Java Stream来简化遍历和计算逻辑。
2. 首先过滤掉没有设备的行。
3. 使用reduce方法计算激光束的数量。
*/
import java.util.Arrays;
public class Solution {
    public int numberOfBeams(String[] bank) {
        return Arrays.stream(bank)
            .mapToInt(row -> (int) row.chars().filter(c -> c == '1').count())
            .filter(count -> count > 0)
            .reduce(0, (total, currentCount) -> {
                int beams = total + currentCount * (total == 0 ? 0 : currentCount);
                return beams == total ? beams : beams + total;
            });
    }
}

解释

方法:

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

时间复杂度:

O(m*n)

空间复杂度:

O(1)

代码细节讲解

🦆

题解中提到的方法是通过计算设备数量并将其与上一行设备数量相乘来统计激光束，那么这种计算方式是否考虑了两行之间可能存在多行没有设备的情况？

▷

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

🦆

在题解的代码中，出现连续多行没有设备时，变量`prevCnt`的值会如何变化？是否会影响最终的激光束计算？

▷

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

🦆

题解中提到，如果一行中没有设备，则跳过该行。请问这是否意味着算法会自动处理并忽略所有中间空行，以只计算两个有设备行之间的激光束？

▷

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

🦆

当所有行都没有设备或只有一行有设备时，算法的输出是什么？这种情况下的输出是否合理？

▷

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

银行中的激光束数量

题目描述

代码结果

解释

代码细节讲解

相关问题