Loading [MathJax]/jax/output/HTML-CSS/jax.js

Leetcode 2125 - Number of Laser Beams in a Bank

題目

Problem#

給你一個 m×n 的陣列 bank 裡頭只包含 0(空的), 1(機器),對於相鄰兩列的機器,對於第 i 列的每台機器會和第 j 列的每台機器用雷射相連,中間不能間隔其他機器,問你總共有多少條雷射?

測資限制#

  • 1m,n500

想法#

統計每列有幾台機器,維護上一個 >0 的列(i)的機器數量,接著繼續往下一列(j)統計機器數量,接著將第 i 列的機器數量與第 j 列的機器數量相乘,便得到 i 列與 j 列中間有幾條雷射,接著跑完所有列,加總即可。

AC Code#

Copy
class Solution {
public:
int numberOfBeams(vector<string>& bank)
{
int n = bank.size(), m = bank[0].size();
int ans = 0;
int last = -1;
for(int i = 0; i < n; i++)
{
int cnt = 0;
for(int j = 0; j < m; j++)
{
if(bank[i][j] == '1')
cnt++;
}
if(cnt)
{
if(last != -1)
{
ans += last * cnt;
}
last = cnt;
}
}
return ans;
}
};
view raw leetcode/2125.cpp delivered with ❤ by emgithub
  • 時間複雜度: O(nm)
  • 空間複雜度: O(1)

心得#

應該是 Easy