LeetCode 筆記 - 419. Battleships in a Board

Posted on 標籤
解析如何在不使用額外空間（O(1) space）的情況下計算矩陣中的戰艦數量。關鍵在於只統計戰艦的「左上角」起點。透過檢查每個戰艦格位上方與左方是否為空，能精確識別出每艘船的首位，達成高效且簡潔的計數邏輯。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 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

也許你也會想看看