LeetCode 题解工作台
银行中的激光束数量
银行内部的防盗安全装置已经激活。给你一个下标从 0 开始的二进制字符串数组 bank ，表示银行的平面图，这是一个大小为 m x n 的二维矩阵。 bank[i] 表示第 i 行的设备分布，由若干 '0' 和若干 '1' 组成。 '0' 表示单元格是空的，而 '1' 表示单元格有一个安全设备。 对任…
4
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·数学
答案摘要
我们可以逐行统计每行的安全设备数量，如果当前行没有安全设备，直接跳过，否则我们将当前行的安全设备数量乘以前一行的安全设备数量，累加到答案中。然后更新前一行的安全设备数量为当前行的安全设备数量。 时间复杂度 $O(m \times n)$，其中 和 分别为行数和列数。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
银行内部的防盗安全装置已经激活。给你一个下标从 0 开始的二进制字符串数组 bank ，表示银行的平面图，这是一个大小为 m x n 的二维矩阵。 bank[i] 表示第 i 行的设备分布，由若干 '0' 和若干 '1' 组成。'0' 表示单元格是空的，而 '1' 表示单元格有一个安全设备。
对任意两个安全设备而言，如果同时 满足下面两个条件，则二者之间存在 一个 激光束：
- 两个设备位于两个 不同行 ：
r1和r2，其中r1 < r2。 - 满足
r1 < i < r2的 所有 行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.lengthn == bank[i].length1 <= m, n <= 500bank[i][j]为'0'或'1'
解题思路
方法一：逐行统计
我们可以逐行统计每行的安全设备数量，如果当前行没有安全设备，直接跳过，否则我们将当前行的安全设备数量乘以前一行的安全设备数量，累加到答案中。然后更新前一行的安全设备数量为当前行的安全设备数量。
时间复杂度 ，其中 和 分别为行数和列数。空间复杂度 。
class Solution:
def numberOfBeams(self, bank: List[str]) -> int:
ans = pre = 0
for row in bank:
if (cur := row.count("1")) > 0:
ans += pre * cur
pre = cur
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(M * N) because each cell in the bank matrix is checked once to count devices. Space complexity is O(1) extra space, aside from storing temporary counts per row, making it efficient for large matrices. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Emphasize counting devices per row and skipping empty rows for efficiency.
- question_mark
Ask why multiplying counts of consecutive non-empty rows correctly represents laser beams.
- question_mark
Check if candidates handle large bank matrices without nested cell-to-cell comparisons.
常见陷阱
外企场景- error
Counting beams for rows with zero devices, which incorrectly inflates the total.
- error
Multiplying non-consecutive rows and ignoring the requirement of no intermediate devices.
- error
Iterating through each possible cell pair, leading to timeouts for large matrices.
进阶变体
外企场景- arrow_right_alt
Modify the problem to include diagonal laser beams and adjust counting accordingly.
- arrow_right_alt
Consider banks with variable row lengths and handle missing cells in the array.
- arrow_right_alt
Count beams when devices can only connect within a maximum row distance instead of any row.