LeetCode 筆記 - 419. Battleships in a Board

題目在此 419. Battleships in a Board

給定一個 m x n 的矩陣,船可能是 1 x k 或 k x 1,不會有相鄰的船
計算總共有幾艘船
image 23

解題思維

遇到這題是因為朋友丟了這題說,這題應該要在 O(1) space 內做完
喔?聽起來有點好玩,我來看看

這題的關鍵其實是找到每艘船的左上角第一次出現在的 X
而第一次出現的 X 與剩下 n - 1 的X,有個差別是

第一個 X 上方跟左方都不會有 X

一但發現一個 X 上方跟左方都沒有 X 的話,就可以計算為一艘船了
完成✅

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:

if not board:
return 0

length_y = len(board)
length_x = len(board[0])

count = 0
for y in range(length_y):
for x in range(length_x):
if board[y][x] != 'X':
continue

last_y = y - 1
last_x = x - 1

if not (0 <= last_y and board[last_y][x] == 'X') and not (0 <= last_x and board[y][last_x] == 'X'):
count += 1

return count

也許你也會想看看