leetcode【每日一题】岛屿数量 Java

题干

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入:
11110
11010
11000
00000
输出: 1
           

示例 2:

输入:

11000

11000

00100

00011

输出: 3

解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

想法

记录岛屿的数量，如果岛屿是一个单独的‘1’那么就+1

如果他和之前连接在一起那么这个‘1’就不算

于是遍历矩阵，碰到‘1’就将数量++；然后以这个‘1’为原点将和它相邻的‘1’全部变为‘0’

其实说白了就是将那些连在一起的岛屿全部换成一个唯一的‘1’

然后记录‘1’的数量就可以了

直接看代码

Java代码

package daily;

public class NumIslands {

    private void dfs(char[][] grid,int x,int y){
        //边界条件或者为'0'，注意是'0'不是整数
            if(x<0||y<0||x>=grid.length||y>=grid[0].length||grid[x][y]=='0'){
                return;
            }
            //否则就是1 ，将它置为'0'
            grid[x][y]='0';
            //四个方向
            dfs(grid,x+1,y);
            dfs(grid,x-1,y);
            dfs(grid,x,y+1);
            dfs(grid,x,y-1);

        }
        public int numIslands(char[][] grid) {
        //count用来计数
            int count=0;
            for(int i=0;i<grid.length;i++){
                for(int j=0;j<grid[0].length;j++){
                    //每一个1，++，然后递归变0
                    if(grid[i][j]=='1'){
                        count++;
                        dfs(grid,i,j);
                    }
                }
            }
            return  count;

    }

    public static  void main(String [] args){
        NumIslands numIslands=new NumIslands();
        char [][]grid={{'1','1','1','1','0'},
                       {'1','1','0','1','0'},
                       {'1','1','0','0','0'},
                       {'0','0','0','0','0'}};

        System.out.println(numIslands.numIslands(grid));
    }
}
           

我的leetcode代码都已经上传到我的git