Leetcode 2125 - Number of Laser Beams in a Bank

題目

Problem#

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

測資限制#

• $1 \le m, n \le 500$

想法#

統計每列有幾台機器，維護上一個 $> 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

• 時間複雜度: $\mathcal{O}(nm)$
• 空間複雜度: $\mathcal{O}(1)$

心得#

應該是 Easy