LeetCode 2125中等数组 · 哈希
银行中的激光束数量 图解题解
这道题到底在问什么
给定一个二进制字符串数组 bank，表示 m 行 n 列的银行平面图，1 是安全设备，0 是空格。两台设备之间存在一束激光，当且仅当它们位于不同的两行 r1 与 r2(其中 r1 < r2)，且这两行之间的所有行都没有任何设备。返回激光束的总数量。
- 输入
- bank=["1100","0000","0110","0010"]
- 输出
- 6
- 输入
- bank=["000","111","000"]
- 输出
- 0
最优解：一步一步想明白
- 3记牢这一句:两个相邻的非空行，激光束数就是两行设备数相乘。为什么是相乘，上一行每台设备都要向下一行的每台设备各连一束，这是一个乘法配对。下面从第 0 行开始，一行一行数过去。
- 4绿格是设备，浅格是空位先看整张图。绿色的格子是安全设备，浅色的是空位。我们要做的事很简单:从最上面一行开始，一行一行往下数，每行数出它有几台设备。手里备两个数，pre 记上一个有设备的行数了几台，一开始是 0；ans 记激光束总数，也从 0 起步。
- 5逐格数本行设备数 cur扫到第 0 行第 0 列，它是设备(1)，本行计数 +1。这一行到目前为止数到了 1 台设备。继续往右看下一格。
- 6逐格数本行设备数 cur扫到第 0 行第 1 列，它是设备(1)，本行计数 +1。这一行到目前为止数到了 2 台设备。继续往右看下一格。
- 7逐格数本行设备数 cur扫到第 0 行第 2 列，它是空位(0)，跳过不计。这一行到目前为止数到了 2 台设备。继续往右看下一格。
- 8逐格数本行设备数 cur扫到第 0 行第 3 列，它是空位(0)，跳过不计。这一行到目前为止数到了 2 台设备。这是本行最后一格，本行设备数 cur 就定格在 2 了。
- 9第一个非空行，先记住它第 0 行数完，本行有 2 台设备。它是第一个有设备的行，前面还没有可以配对的行，pre 原来是 0，pre 乘 cur 等于 0，暂时连不出激光。把 pre 更新成本行的 2，等着和下一个非空行配对。
- 10逐格数本行设备数 cur扫到第 1 行第 0 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。继续往右看下一格。
- 11逐格数本行设备数 cur扫到第 1 行第 1 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。继续往右看下一格。
- 12逐格数本行设备数 cur扫到第 1 行第 2 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。继续往右看下一格。
- 13逐格数本行设备数 cur扫到第 1 行第 3 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。这是本行最后一格，本行设备数 cur 就定格在 0 了。
- 14空行透明，pre 不变第 1 行数完了，一台设备都没有，cur 是 0。空行就像一层透明玻璃，激光会直接穿过它，所以它不参与任何相乘，pre 也保持原来的 2 不动。总数还是 0，接着看下一行。
- 15逐格数本行设备数 cur扫到第 2 行第 0 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。继续往右看下一格。
- 16逐格数本行设备数 cur扫到第 2 行第 1 列，它是设备(1)，本行计数 +1。这一行到目前为止数到了 1 台设备。继续往右看下一格。
- 17逐格数本行设备数 cur扫到第 2 行第 2 列，它是设备(1)，本行计数 +1。这一行到目前为止数到了 2 台设备。继续往右看下一格。
- 18逐格数本行设备数 cur扫到第 2 行第 3 列，它是空位(0)，跳过不计。这一行到目前为止数到了 2 台设备。这是本行最后一格，本行设备数 cur 就定格在 2 了。
- 19相邻非空行相乘累加第 2 行数完，本行有 2 台设备。它和上一个非空行之间只隔着空行，于是上一行的 2 台设备，每台都要和这一行的 2 台各连一束激光，这一段共 2 乘 2 等于 4 束。累加后总数变成 4。再把 pre 更新成 2。
- 20逐格数本行设备数 cur扫到第 3 行第 0 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。继续往右看下一格。
- 21逐格数本行设备数 cur扫到第 3 行第 1 列，它是空位(0)，跳过不计。这一行到目前为止数到了 0 台设备。继续往右看下一格。
- 22逐格数本行设备数 cur扫到第 3 行第 2 列，它是设备(1)，本行计数 +1。这一行到目前为止数到了 1 台设备。继续往右看下一格。
- 23逐格数本行设备数 cur扫到第 3 行第 3 列，它是空位(0)，跳过不计。这一行到目前为止数到了 1 台设备。这是本行最后一格，本行设备数 cur 就定格在 1 了。
- 24相邻非空行相乘累加第 3 行数完，本行有 1 台设备。它和上一个非空行第 2 行紧挨着，中间没有空行，于是上一行的 2 台设备，每台都要和这一行的 1 台各连一束激光，这一段共 2 乘 1 等于 2 束。累加后总数变成 6。再把 pre 更新成 1。
- 25非空行设备数序列把刚才三个非空行的设备数抽出来排成一排:2、2、1。空行已经被滤掉，剩下的就是能互相连激光的行。相邻的第一对是 2 和 2，它们之间的激光束是 2 乘 2 等于 4 束，先记下这 4 束。
- 26非空行设备数序列往右滑一格看下一对，2 和 1，它们之间是 2 乘 1 等于 2 束。把两段加起来，4 加 2 等于 6。可以看出，答案就是把相邻的设备数两两相乘再全部加起来。
- 27一遍扫描搞定回放一遍。从上往下一行一行数设备:第 0 行 2 台、第 1 行空、第 2 行 2 台、第 3 行 1 台。空行跳过，剩下的相邻两行两两相乘再相加，2 乘 2 加 2 乘 1，正好等于 6。整个过程只从上到下扫了一遍，一个数组配上 pre 和 ans 两个变量就够了。
⚠️ 容易写错的地方
✗ 错：把空行也算进配对，用相邻两行直接相乘
✓ 对：只在非空行之间配对，空行跳过、不更新 pre
空行没有设备，激光会穿过它连到再上面的非空行;若把空行的 0 也拿去乘会漏掉真正的配对
✗ 错：每次都拿当前行和它正上方一行相乘
✓ 对：拿当前行和上一个非空行 pre 相乘
两个非空行中间可能夹着若干空行，正上方那行也许是空的，必须用 pre 记住最近一个有设备的行
✗ 错：两两行嵌套枚举所有设备对，O((mn)²) 统计
✓ 对：一次线性扫描，逐段用乘法一次算清
同一段里上下两行的设备是完全二部相连，直接用个数相乘就是这一段的束数，不必真的两两枚举
✗ 错：答案变量用 int，担心乘积溢出
✓ 对：本题规模下 int 足够，心里知道上界即可
每行最多 n 台设备，单段乘积最大约 n 平方，n 到 500 时约 25 万，远在 int 范围内，不会溢出
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
int numberOfBeams(vector<string>& bank) {
int ans = 0, pre = 0;
for (auto& row : bank) {
int cur = count(row.begin(), row.end(), '1');
if (cur) {
ans += pre * cur;
pre = cur;
}
}
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int numberOfBeams(String[] bank) {
int ans = 0, pre = 0;
for (String row : bank) {
int cur = 0;
for (int i = 0; i < row.length(); ++i) {
cur += row.charAt(i) - '0';
}
if (cur > 0) {
ans += pre * cur;
pre = cur;
}
}
return ans;
}
}复杂度
时间
O(m·n)
m 行 n 列。外层遍历每一行，内层为了数这一行的设备数要把这一行的 n 个字符看一遍，合起来正好把整张图的每个字符访问一次，随格子总数 m 乘 n 线性增长
空间
O(1)
按峰值算。全程只用 pre、cur、ans 这几个整数变量，不额外开与输入规模相关的数组或表，占用是常数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 银行中的激光束数量 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心思路一句话怎么说?+
从上到下逐行数设备数，用 pre 记住上一个非空行的设备数。每遇到一个非空行，就把 pre 乘当前行设备数累加进答案，再更新 pre。相邻两个非空行之间是设备的完全二部配对，束数正好是两行个数相乘，所以整题就是把相邻非空行的设备数两两相乘再求和。
为什么是相乘，不是相加?+
因为两个相邻非空行之间，上面每一台设备都会独立地向下面每一台设备各连一束互不干扰的激光，这是笛卡尔积式的配对，束数等于两边个数的乘积。相加只会得到设备总数，和激光束数没关系。
复杂度是多少，还能再优化吗?+
时间 O(m 乘 n)，因为要把每个字符看一遍数出每行的设备数;空间 O(1)，只用 pre、cur、ans 几个变量。这已经是最优，每个字符至少得读一次才能知道它是不是设备，线性扫描无法再降。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 银行中的激光束数量 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。