題目在此 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 的話，就可以計算為一艘船了
完成✅
程式碼
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
|
也許你也會想看看
