Medium

题目描述

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

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

提示：

  • m == bank.length
  • n == bank[i].length
  • 1 <= m, n <= 500
  • bank[i][j] 要么是 '0' ，要么是 '1' 。

解题思路

这道题的关键在于理解激光束的形成条件：只有在两个不同行且中间没有安全设备的行之间，才会有激光束连接。

核心思路：

  1. 首先统计每一行的安全设备数量（即字符'1’的个数）
  2. 跳过没有安全设备的行（设备数为0的行）
  3. 对于相邻的两个有设备的行，激光束数量 = 第一行设备数 × 第二行设备数

算法步骤：

  1. 遍历所有行，计算每行的设备数量
  2. 将设备数量大于0的行的设备数存储到数组中
  3. 遍历相邻的有设备的行，累加它们之间的激光束数量

时间复杂度分析：

  • 需要遍历所有字符统计设备数：O(m×n)
  • 计算激光束数量：O(k)，其中k是有设备的行数
  • 总时间复杂度：O(m×n)

这种方法简洁高效，避免了复杂的行间判断，直接利用数学关系求解。

代码实现

class Solution {
public:
    int numberOfBeams(vector<string>& bank) {
        vector<int> devices;
        
        // 统计每行的设备数量
        for (const string& row : bank) {
            int count = 0;
            for (char c : row) {
                if (c == '1') count++;
            }
            if (count > 0) {
                devices.push_back(count);
            }
        }
        
        // 计算激光束总数
        int result = 0;
        for (int i = 1; i < devices.size(); i++) {
            result += devices[i-1] * devices[i];
        }
        
        return result;
    }
};

class Solution:
    def numberOfBeams(self, bank: List[str]) -> int:
        devices = []
        
        # 统计每行的设备数量
        for row in bank:
            count = row.count('1')
            if count > 0:
                devices.append(count)
        
        # 计算激光束总数
        result = 0
        for i in range(1, len(devices)):
            result += devices[i-1] * devices[i]
        
        return result

public class Solution {
    public int NumberOfBeams(string[] bank) {
        List<int> devices = new List<int>();
        
        // 统计每行的设备数量
        foreach (string row in bank) {
            int count = 0;
            foreach (char c in row) {
                if (c == '1') count++;
            }
            if (count > 0) {
                devices.Add(count);
            }
        }
        
        // 计算激光束总数
        int result = 0;
        for (int i = 1; i < devices.Count; i++) {
            result += devices[i-1] * devices[i];
        }
        
        return result;
    }
}

/**
 * @param {string[]} bank
 * @return {number}
 */
var numberOfBeams = function(bank) {
    const devices = [];
    
    // 统计每行的设备数量
    for (const row of bank) {
        const count = (row.match(/1/g) || []).length;
        if (count > 0) {
            devices.push(count);
        }
    }
    
    // 计算激光束总数
    let result = 0;
    for (let i = 1; i < devices.length; i++) {
        result += devices[i-1] * devices[i];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n)需要遍历所有字符统计设备数量，m为行数，n为列数
空间复杂度O(m)最坏情况下所有行都有设备，需要存储m个设备数量

相关题目