Problem#
給你一個 m×n 的陣列 bank
裡頭只包含 0
(空的), 1
(機器),對於相鄰兩列的機器,對於第 i 列的每台機器會和第 j 列的每台機器用雷射相連,中間不能間隔其他機器,問你總共有多少條雷射?
測資限制#
- 1≤m,n≤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; } };
- 時間複雜度: O(nm)
- 空間複雜度: O(1)
心得#
應該是 Easy