LeetCode 2125: Number of Laser Beams in a Bank (Row Devices Product)
LeetCode 2125CountingGreedyToday we solve LeetCode 2125 - Number of Laser Beams in a Bank.
Source: https://leetcode.com/problems/number-of-laser-beams-in-a-bank/
English
Problem Summary
Given a binary string array bank, each '1' is a security device. A laser beam forms between two devices in different rows if all rows between them contain no devices. Return the total number of beams.
Key Insight
Only rows with at least one device matter. If previous non-empty row has prev devices and current non-empty row has cur devices, they contribute prev * cur beams. Then set prev = cur.
Algorithm
- Initialize prev = 0, ans = 0.
- For each row, count ones as cur.
- If cur == 0, skip this row.
- Otherwise, add prev * cur to answer and update prev = cur.
Complexity Analysis
Time: O(mn), scanning each cell once.
Space: O(1).
Common Pitfalls
- Multiplying adjacent rows directly without skipping zero-device rows.
- Resetting prev to 0 on empty rows (wrong).
- Overcomplicating with prefix structures when one pass is enough.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int numberOfBeams(String[] bank) {
int prev = 0, ans = 0;
for (String row : bank) {
int cur = 0;
for (int i = 0; i < row.length(); i++) {
if (row.charAt(i) == '1') cur++;
}
if (cur == 0) continue;
ans += prev * cur;
prev = cur;
}
return ans;
}
}func numberOfBeams(bank []string) int {
prev, ans := 0, 0
for _, row := range bank {
cur := 0
for i := 0; i < len(row); i++ {
if row[i] == '1' {
cur++
}
}
if cur == 0 {
continue
}
ans += prev * cur
prev = cur
}
return ans
}class Solution {
public:
int numberOfBeams(vector<string>& bank) {
int prev = 0, ans = 0;
for (const string& row : bank) {
int cur = 0;
for (char c : row) if (c == '1') cur++;
if (cur == 0) continue;
ans += prev * cur;
prev = cur;
}
return ans;
}
};class Solution:
def numberOfBeams(self, bank: list[str]) -> int:
prev = 0
ans = 0
for row in bank:
cur = row.count('1')
if cur == 0:
continue
ans += prev * cur
prev = cur
return ansvar numberOfBeams = function(bank) {
let prev = 0, ans = 0;
for (const row of bank) {
let cur = 0;
for (const ch of row) if (ch === '1') cur++;
if (cur === 0) continue;
ans += prev * cur;
prev = cur;
}
return ans;
};中文
题目概述
给定二进制字符串数组 bank，每个 '1' 表示一个安防设备。若两台设备位于不同行，且它们之间的所有行都没有设备，则二者之间会形成一条激光束。求总激光束数量。
核心思路
真正有贡献的是“非空行”（设备数 > 0）。设上一条非空行设备数是 prev，当前非空行是 cur，则两行之间贡献 prev * cur 条激光束，然后更新 prev = cur。
算法步骤
- 初始化 prev = 0，ans = 0。
- 逐行统计设备数 cur。
- 若 cur == 0，该行跳过。
- 否则累加 prev * cur，并更新 prev = cur。
复杂度分析
时间复杂度：O(mn)（每个格子扫描一次）。
空间复杂度：O(1)。
常见陷阱
- 直接按相邻物理行相乘，忽略中间空行应被跳过。
- 遇到空行就把 prev 清零，会漏算后续合法连接。
- 使用复杂结构反而增加错误风险，一次遍历足够。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int numberOfBeams(String[] bank) {
int prev = 0, ans = 0;
for (String row : bank) {
int cur = 0;
for (int i = 0; i < row.length(); i++) {
if (row.charAt(i) == '1') cur++;
}
if (cur == 0) continue;
ans += prev * cur;
prev = cur;
}
return ans;
}
}func numberOfBeams(bank []string) int {
prev, ans := 0, 0
for _, row := range bank {
cur := 0
for i := 0; i < len(row); i++ {
if row[i] == '1' {
cur++
}
}
if cur == 0 {
continue
}
ans += prev * cur
prev = cur
}
return ans
}class Solution {
public:
int numberOfBeams(vector<string>& bank) {
int prev = 0, ans = 0;
for (const string& row : bank) {
int cur = 0;
for (char c : row) if (c == '1') cur++;
if (cur == 0) continue;
ans += prev * cur;
prev = cur;
}
return ans;
}
};class Solution:
def numberOfBeams(self, bank: list[str]) -> int:
prev = 0
ans = 0
for row in bank:
cur = row.count('1')
if cur == 0:
continue
ans += prev * cur
prev = cur
return ansvar numberOfBeams = function(bank) {
let prev = 0, ans = 0;
for (const row of bank) {
let cur = 0;
for (const ch of row) if (ch === '1') cur++;
if (cur === 0) continue;
ans += prev * cur;
prev = cur;
}
return ans;
};
Comments