LeetCode 200：島嶼數量 Number of Islands

題目：

給定一個由

'1'

（陸地）和

'0'

（水）組成的的二維網格，計算島嶼的數量。一個島被水包圍，并且它是通過水準方向或垂直方向上相鄰的陸地連接配接而成的。你可以假設網格的四個邊均被水包圍。

Given a 2d grid map of

'1'

s (land) and

'0'

s (water), count 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.

示例 1:

示例 2:

解題思路：

首先明白島嶼的定義：一塊 1 周圍全是 0，即為一個島嶼。（注意：grid 數組内的 1、0 均為char型字元，非整型）

示例1 中所有 1 都可以連接配接到一起，即所有 1 組成一個島嶼。示例2 中的三個島嶼：左上角四個1、中間一個1、右下角一個一，分别組成三個島嶼。

Flood fill算法是從一個區域中提取若幹個連通的點與其他相鄰區域區分開（或分别染成不同顔色）的經典算法。因為其思路類似洪水從一個區域擴散到所有能到達的區域而得名。在 GNU Go 和掃雷中，Flood Fill算法被用來計算需要被清除的區域。由上述定義可看出該題是典型的Flood fill算法類型例題，将島嶼與水分開，并染成特定顔色，以記錄已累加過該島嶼。

每塊島嶼可以看成相連的一個個節點，隻需把所有相連節點周遊殆盡并标上特殊值以記錄該節點已通路過，則周遊殆盡時證明一塊島嶼已找到。

三種解題方法：

DFS（深度優先搜尋）：從一個為1的根節點開始通路，從每個相鄰1節點向下通路到頂點（周圍全是水），依次通路其他相鄰1節點到頂點
BFS（廣度優先搜尋）：從一個為1的根節點開始通路，每次向下通路一個節點，直到通路到最後一個頂點
并查集：也被稱為聯合查找資料結構，因為它主要由聯合、查找兩個過程實作：
- Find：确定元素屬于哪一個子集。它可以被用來确定兩個元素是否屬于同一子集。
- Union：将兩個子集合并成同一個集合。
針對該題即先以一個根節點1作為初始節點，判斷周圍節點是否為1，如果是則建立一個集合并把該節點作為父節點。之後周遊下一個節點，如果是1則查找該節點的父節點（即第一個節點），并把該節點周圍為1的節點的父節點全部指向該節點的父節點，以此類推，直到把該塊島嶼所有1 節點加入同一個集合。最後集合個數（父節點的個數）即為島嶼數量

DFS:

時間複雜度 : O(M×N)，其中 M 和 N 分别為行數和列數。

空間複雜度 : 最壞情況下為 O(M×N)，此時整個網格均為陸地，深度優先搜尋的深度達到 M×N。

Java：

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int row = grid.length, columns = grid[0].length, count = 0;
        for (int i = 0; i < row; i++) {//周遊所有點
            for (int j = 0; j < columns; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j, row, columns);//dfs周遊所有連接配接的點
                    count++;//記錄島嶼數量
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int i, int j, int row, int columns) {
        if (i < 0 || j < 0 || i >= row || j >= columns || grid[i][j] == '0') return;//基線條件
        grid[i][j] = '0';//周遊過的點置 0
        dfs(grid, i + 1, j, row, columns);
        dfs(grid, i, j + 1, row, columns);
        dfs(grid, i - 1, j, row, columns);
        dfs(grid, i, j - 1, row, columns);
    }
}

Python：

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or len(grid) == 'o': return 0
        row, columns = len(grid), len(grid[0])
        count = 0
        for i in range(row):
            for j in range(columns):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j, row, columns)
                    count += 1
        return count

    def dfs(self, grid: List[List[str]], i: int, j: int, row: int, columns: int):
        if i >= row or i < 0 or j >= columns or j < 0 or grid[i][j] == '0': return
        grid[i][j] = '0'
        self.dfs(grid, i - 1, j, row, columns)
        self.dfs(grid, i, j - 1, row, columns)
        self.dfs(grid, i + 1, j, row, columns)
        self.dfs(grid, i, j + 1, row, columns)

BFS：

空間複雜度 : O( min(M,N) )，在最壞的情況下（全部為陸地），隊列的大小可以達到 min(M，N)。

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int row = grid.length, columns = grid[0].length, count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < columns; j++) {//周遊所有節點
                if (grid[i][j] == '1') {
                    bfs(grid, i, j, row, columns);
                    count++;//記錄島嶼數量
                }
            }
        }
        return count;
    }

    private void bfs(char[][] grid, int i, int j, int row, int columns) {
        Queue<Integer> loc = new LinkedList<>();//隊列暫存值為 1 的點
        loc.add(i * columns + j);//暫存該點位置，也可以用一個[i,j]數組表示，不過占用空間也會大一倍
        while (!loc.isEmpty()) {
            int id = loc.remove();//取出位置
            int r = id / columns, c = id % columns;//分解位置得到索引
            if (r - 1 >= 0 && grid[r - 1][c] == '1') {
                loc.add((r - 1) * columns + c);
                grid[r - 1][c] = '0';
            }
            if (r + 1 < row && grid[r + 1][c] == '1') {
                loc.add((r + 1) * columns + c);
                grid[r + 1][c] = '0';
            }
            if (c - 1 >= 0 && grid[r][c - 1] == '1') {
                loc.add(r * columns + c - 1);
                grid[r][c - 1] = '0';
            }
            if (c + 1 < columns && grid[r][c + 1] == '1') {
                loc.add(r * columns + c + 1);
                grid[r][c + 1] = '0';
            }
        }
    }
}

Python3：

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or len(grid) == 'o': return 0
        row, columns = len(grid), len(grid[0])
        count = 0
        for i in range(row):
            for j in range(columns):
                if grid[i][j] == '1':
                    self.bfs(grid, i, j, row, columns)
                    count += 1
        return count

    def bfs(self, grid: List[List[str]], i: int, j: int, row: int, columns: int):
        queue = collections.deque()
        queue.append((i, j))  # 位置以元組存入隊列
        while queue:
            r, c = queue.popleft()
            if r + 1 < row and grid[r + 1][c] == '1':
                queue.append((r + 1, c))
                grid[r + 1][c] = '0'
            if r - 1 >= 0 and grid[r - 1][c] == '1':
                queue.append((r - 1, c))
                grid[r - 1][c] = '0'
            if c + 1 < columns and grid[r][c + 1] == '1':
                queue.append((r, c + 1))
                grid[r][c + 1] = '0'
            if c - 1 >= 0 and grid[r][c - 1] == '1':
                queue.append((r, c - 1))
                grid[r][c - 1] = '0'

并查集：

并查集這種解法冗雜且雞肋，效率很低，以下java代碼參考自LeetCode。簡單了解其思想擴充一下思路即可：

class Solution {
    class UnionFind {
        int count; //計數
        int[] parent;
        int[] rank;

        public UnionFind(char[][] grid) {
            count = 0;
            int m = grid.length, n = grid[0].length;
            parent = new int[m * n];
            rank = new int[m * n];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '1') {
                        parent[i * n + j] = i * n + j;
                        ++count;
                    }
                    rank[i * n + j] = 0;
                }
            }
        }
        public int find(int i) {
            if (parent[i] != i) parent[i] = find(parent[i]);
            return parent[i];
        }
        public void union(int x, int y) {
            int rootx = find(x);
            int rooty = find(y);
            if (rootx != rooty) {
                if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx;
                } else if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty;
                } else {
                    parent[rooty] = rootx;
                    rank[rootx] += 1;
                }
                --count;
            }
        }
        public int getCount() {
            return count;
        }
    }
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int row = grid.length, columns = grid[0].length;
        UnionFind uf = new UnionFind(grid);
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < columns; ++j) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    if (i - 1 >= 0 && grid[i - 1][j] == '1') uf.union(i * columns + j, (i - 1) * columns + j);
                    if (i + 1 < row && grid[i + 1][j] == '1') uf.union(i * columns + j, (i + 1) * columns + j);
                    if (j - 1 >= 0 && grid[i][j - 1] == '1') uf.union(i * columns + j, i * columns + j - 1);
                    if (j + 1 < columns && grid[i][j + 1] == '1') uf.union(i * columns + j, i * columns + j + 1);
                }
            }
        }
        return uf.getCount();
    }
}

歡迎關注微.信公.衆号一起加油吖：愛寫Bug

LeetCode 200：島嶼數量 Number of Islands

題目：

解題思路：

DFS:

BFS：

并查集：

繼續閱讀

結構體：typedef與struct的差別

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希