Anti-theft security devices are activated inside a bank. You are given a 0-indexed binary string array bank
representing the floor plan of the bank, which is an m x n
2D matrix. bank[i]
represents the ith
row, consisting of '0'
s and '1'
s. '0'
means the cell is empty, while'1'
means the cell has a security device.
There is one laser beam between any two security devices if both conditions are met:
- The two devices are located on two different rows:
r1
andr2
, wherer1 < r2
. - For each row
i
wherer1 < i < r2
, there are no security devices in theith
row.
Laser beams are independent, i.e., one beam does not interfere nor join with another.
Return the total number of laser beams in the bank.
Example 1:
Input: bank = ["011001","000000","010100","001000"] Output: 8 Explanation: Between each of the following device pairs, there is one beam. In total, there are 8 beams: * 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] Note that there is no beam between any device on the 0th row with any on the 3rd row. This is because the 2nd row contains security devices, which breaks the second condition.
Example 2:
Input: bank = ["000","111","000"] Output: 0 Explanation: There does not exist two devices located on two different rows.
Constraints:
m == bank.length
n == bank[i].length
1 <= m, n <= 500
bank[i][j]
is either'0'
or'1'
.
Solution: Rule of product
Just need to remember the # of devices of prev non-empty row.
# of beams between two non-empty row equals to row[i] * row[j]
ans += prev * curr
Time complexity: O(m*n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int numberOfBeams(vector<string>& bank) { int ans = 0; int prev = 0; for (const string& row : bank) if (int curr = count(begin(row), end(row), '1')) { ans += prev * curr; prev = curr; } return ans; } }; |
Python3
1 2 3 4 5 6 7 8 9 |
# Author: Huahua class Solution: def numberOfBeams(self, bank: List[str]) -> int: ans = prev = 0 for row in bank: if curr := row.count('1'): ans += prev * curr prev = curr return ans |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment