題目

  • 題目連結
  • 目標函式 : numIslands(grid)
    • Input : grid: List[List[str]]
    • Output : int

解題概念

  • 題意 : 給定一 m x n 的二維陣列 grid，其中 "1" 代表陸地、"0" 代表水，需要回傳 Island 的數量
  • Island 之定義 :
    • 四面環水
    • 相鄰之陸地需要水平或垂直向連接
    • 超出陣列的元素皆視為水

我的寫法

  • 想法 : 此題是經典的 Flood Fill Algorithm 的題目，而其中會使用到 DFS 的概念
    • 說明請詳見程式碼
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    def numIslands(self, grid):
        
        def DFS(i, j):
            # 若超出陣列，代表已碰到水域，直接 return 即可
            # 最後的 grid[i][j] != "1" 代表若該格已探索過也直接 return
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != "1":
                return

            grid[i][j] = "-1" # 標示為已探索過

            # 朝四個方向去探索
            DFS(i - 1, j)
            DFS(i + 1, j)
            DFS(i, j - 1)
            DFS(i, j + 1)
            return

        cnt = 0 # 紀錄 island 的數量
        # 使用雙重迴圈去探索每個格子
        for j in range(len(grid[0])):
            for i in range(len(grid)):
                if grid[i][j] == "1":s
                    DFS(i, j)
                    cnt += 1

        return cnt
  • 成效 :
    • Time Complexity : $O(n^2)$
    • Runtime: 208 ms (faster than 81.33%)
    • Memory Usage: 28.66 MB (more than 69.57%)

解答 or 其他優秀寫法

  • 想法 : 也可使用 BFS 的寫法
    • 另外，還可以使用了在 【Leetcode解題】542. 01 Matrix 中所使用到的寫法 : 宣告了 DIR = [0, 1, 0, -1, 0]，這種寫法可以快速處理上下左右的格子，非常漂亮!
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    def numIslands(self, grid):
        
        DIR = [0, 1, 0, -1, 0]
        cnt = 0

        for j in xrange(len(grid[0])):
            for i in xrange(len(grid)):
                if grid[i][j] == "1":
                    cnt += 1

                    # BFS
                    queue = [[i, j]]
                    while len(queue) != 0:
                        node = queue.pop(0)
                        for k in xrange(4):
                            new_i = node[0] + DIR[k]
                            new_j = node[1] + DIR[k + 1]
                            if 0 <= new_i < len(grid) and 0 <= new_j < len(grid[0]) and grid[new_i][new_j] == "1":
                                grid[new_i][new_j] = "-1"
                                queue.append([new_i, new_j])


        return cnt
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 233 ms (faster than 59.25%)
    • Memory Usage: 28.47 MB (more than 96.53%)