JAVA练习319- 岛屿数量

题目概览给你一个由1陆地和0水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。示例 1输入grid [ [1,1,1,1,0], [1,1,0,1,0], [1,1,0,0,0], [0,0,0,0,0] ]输出1示例 2输入grid [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ]输出3提示m grid.lengthn grid[i].length1 m, n 300grid[i][j]的值为0或1来源200. 岛屿数量 - 力扣LeetCode解题分析方法深度优先搜索当一个元素为 1 时与它相邻的 1 组成一个岛屿因此我们可以对这个元素进行上下左右的遍历先记录一个岛屿然后将元素为 1 时值修改为 0这样就可以避免下一次遍历到重复岛屿。时间复杂度O(mn)空间复杂度O(mn)class Solution { public int numIslands(char[][] grid) { int m grid.length, n grid[0].length; int num 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { arrive(grid, i, j); num; } } } return num; } private void arrive(char[][] grid, int i, int j) { if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0) { return; } grid[i][j] 0; arrive(grid, i 1, j); arrive(grid, i - 1, j); arrive(grid, i, j 1); arrive(grid, i, j - 1); } }