200. Number of Islands

Photo by Derek Oyen on Unsplash
Photo by Derek Oyen on Unsplash
解這題的想法是,對每一個未訪問過的 land,用 DFS 或 BFS 去訪問相鄰 lands。當相鄰 cell 為 land 時,再繼續訪問其相鄰 lands,一直無法再擴張為止。這樣就得到一個 island。然後,再找下一個未訪問過的 land 做上述相同的動作,一直到所有的 land 都被訪問過。
Table of Contents
  1. Problem
  2. Solution
  3. DFS
  4. BFS
  5. 參考

Problem

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.

Solution

解這題的想法是,對每一個未訪問過的 land,用 DFS 或 BFS 去訪問相鄰 lands。當相鄰 cell 為 land 時,再繼續訪問其相鄰 lands,一直無法再擴張為止。這樣就得到一個 island。然後,再找下一個未訪問過的 land 做上述相同的動作,一直到所有的 land 都被訪問過。

DFS

  • Time: O(mn)
  • Space: O(mn)
class Solution {
    public int numIslands(char[][] grid) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int islands = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid, i, j, visited);
                    islands++;
                }
            }
        }
        return islands;
    }

    private void dfs(char[][] grid, int i, int j, boolean[][] visited) {
        visited[i][j] = true;
        int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int[] dir : dirs) {
            int r = i + dir[0];
            int c = j + dir[1];
            if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) continue;
            if (visited[r][c] || grid[r][c] == '0') continue;
            dfs(grid, r, c, visited);
        }
    }
}

BFS

  • Time: O(mn)
  • Space: O(mn)
class Solution {
    public int numIslands(char[][] grid) {
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int islands = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    bfs(grid, i, j, visited);
                    islands++;
                }
            }
        }
        return islands;
    }

    private void bfs(char[][] grid, int row, int col, boolean[][] visited) {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {row, col});
        int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            if (visited[pos[0]][pos[1]]) continue;
            visited[pos[0]][pos[1]] = true;
            for (int[] dir : dirs) {
                int r = pos[0] + dir[0];
                int c = pos[1] + dir[1];
                if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) continue;
                if (grid[r][c] == '0' || visited[r][c]) continue;
                queue.offer(new int[] {r, c});
            }
        }
    }
}

參考

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

You May Also Like
Photo by Oladimeji Odunsi on Unsplash
Read More

72. Edit Distance

在解此題時,我們要先觀察 word1 如何變成 word2。以 Example1 為例,左下圖列出 “horse” 轉變成 “ros” 的 distance。表中,縱軸表示 “horse”,而橫軸表示 “ros”。
Read More
Photo by Diana Parkhouse on Unsplash
Read More

1048. Longest String Chain

此題中,wordA 是 wordB 的 predecessor 指只要插入一個 letter 到 wordA,那就會使得它和 wordB 一樣。然而,插入一個 letter 到一個地方,就要考慮 26 種字母。這使得整體的複雜度上升。
Read More
Photo by Bogdan Farca on Unsplash
Read More

39. Combination Sum

此題要我們列出所有可能的組合,所以我們可能用 backtracking 來找。但是,我們必須避免找到相同的組合。當兩個組合裡的數字和個數都依一樣,但順序不一樣時,他們依然是相同的組合。
Read More