島嶼數(shù)量

• 給你一個(gè)由 ‘1’（陸地）和 ‘0’（水）組成的的二維網(wǎng)格，請(qǐng)你計(jì)算網(wǎng)格中島嶼的數(shù)量。

島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。

此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。

示例 1：

輸入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
輸出：1

解題思路

• 1、使用深度優(yōu)先搜索DFS來(lái)遍歷二維網(wǎng)格，找到所有島嶼。(PS: 深度優(yōu)先搜索（DFS）一般是使用遞歸來(lái)實(shí)現(xiàn))
• 2、對(duì)于每個(gè)遍歷到的陸地（‘1’），開始進(jìn)行搜索，將其與相鄰的陸地標(biāo)記為已訪問(wèn)過(guò)，直到將整個(gè)島嶼搜索完成。
• 3、統(tǒng)計(jì)搜索過(guò)程中遇到的島嶼數(shù)量。

Java實(shí)現(xiàn)

public class NumberOfIslands {public int numIslands(char[][] grid) {if (grid == null || grid.length == 0 || grid[0].length == 0) {return 0;}int m = grid.length;int n = grid[0].length;int count = 0;
//        {'1', '1', '0', '0', '0'},
//        {'1', '1', '0', '0', '0'},
//        {'0', '0', '1', '0', '0'},
//        {'0', '0', '0', '1', '1'}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {// 當(dāng)前位置為陸地，開始進(jìn)行深度優(yōu)先搜索// 直到grid[i][j]周邊沒(méi)有相連的陸地dfs(grid, i, j);// 每開始一次搜索，島嶼數(shù)量加一count++;}}}return count;}/*** 深度優(yōu)先搜索函數(shù)* @param grid* @param i* @param j*/private void dfs(char[][] grid, int i, int j) {int m = grid.length;int n = grid[0].length;// 邊界條件和遞歸終止條件if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {return;}grid[i][j] = '0'; //將當(dāng)前單元格標(biāo)記為已訪問(wèn)//繼續(xù)搜索當(dāng)前位置的上、下、左、右四個(gè)方向,探索相鄰的單元格//直到?jīng)]有相鄰的島嶼（grid[i][j] == '0'）dfs(grid, i + 1, j);dfs(grid, i - 1, j);dfs(grid, i, j + 1);dfs(grid, i, j - 1);}public static void main(String[] args) {NumberOfIslands islands = new NumberOfIslands();char[][] grid = {{'1', '1', '0', '0', '0'},{'1', '1', '0', '0', '0'},{'0', '0', '1', '0', '0'},{'0', '0', '0', '1', '1'}};System.out.println("Number of islands: " + islands.numIslands(grid));}
}

時(shí)間空間復(fù)雜度

• 時(shí)間復(fù)雜度：O(m * n)，其中 m 和 n 分別是二維網(wǎng)格的行數(shù)和列數(shù)，因?yàn)樾枰闅v整個(gè)二維網(wǎng)格。

• 空間復(fù)雜度：O(m * n)，深度優(yōu)先搜索的遞歸調(diào)用可能達(dá)到 O(m * n) 的深度，其中 m 和 n 分別是二維網(wǎng)格的行數(shù)和列數(shù)。