当前位置：网站首页>『牛客|每日一题』岛屿数量

『牛客|每日一题』岛屿数量

2022-08-10 18:39:00 【starry陆离】

活动地址：CSDN21天学习挑战赛

作者简介：一位喜欢写作，计科专业大二菜鸟
个人主页：starry陆离
首发日期：2022年8月10日星期三
每日推荐：牛客网-面试神器

『牛客|每日一题』岛屿数量
1.每日一题
2.解题思路：DFS
2.1思路分析
2.2核心代码
3.解题思路：BFS
3.1思路分析
3.2核心代码

如果文章有帮到你的话记得点赞+收藏支持一下哦

在这里插入图片描述

1.每日一题

2.解题思路：DFS

深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。

2.1思路分析

整体思路就是找到一堆1就意味着找到一个岛屿，然后把他们变成0，再找下一堆1再把这堆1变成0，直到没有1为止。

微观上的处理就是：当我们遇到矩阵的某个元素为1时，首先将其置为了0，然后查看与它相邻的上下左右四个方向，如果这四个方向任意相邻元素为1，则进入该元素，进入该元素之后我们发现又回到了刚刚的子问题，又是把这一片相邻区域的1全部置为0，因此可以用递归实现。

step 1：首先还是要做特例检查，矩阵不能为空*且长度不能为0
step 2：然后找到一个1作为起始点，把与这个1相连的所有1置为0（这一步使用递归来实现）
step 3：找到一个1后，遍历它的四周看看还有没有1，如果有则进入更深层次的递归去找到这个1周围的1，统统把它们变为0，如此递归下去直到这片区域没有1这次递归才结束
step 4：然后重新找一个起始点，重复第step 3步，直到双层for循环遍历完整个矩阵再也找不到1了

2.2核心代码

import java.util.*;
public class Solution {
    
    /** * 判断岛屿数量 * @param grid char字符型二维数组 * @return int整型 */
    //记录岛屿数量
    private int ans;
    //搜索的方向数组
    private int xx[]={
    -1,1,0,0};
    private int yy[]={
    0,0,-1,1};
    public int solve (char[][] grid) {
    
        //数组为空检查
        if(grid==null||grid.length==0){
    
            return 0;
        }
        //初始化岛屿数量为0
        ans=0;
        //数组的行
        int r=grid.length;
        //数组的宽
        int c=grid[0].length;
        //遍历数组矩阵找到初始点(1)
        for(int i=0;i<r;++i){
    
            for(int j=0;j<c;++j){
    
                if(grid[i][j]=='1'){
    
                    //岛屿数量++
                    ans++;
                    //深搜将与这个(1)相连的所有1置为0
                    dfs(i,j,grid);
                }
            }
        }
        return ans;
    }
    
    public void dfs(int x,int y,char [][]grid){
    
        //搜索的结束条件,数组越界或者此点不是1(陆地)就结束
        if(!check(x,y,grid)){
    
           return;
        }
        //此点被搜索过,将1置为0
        grid[x][y]=0;
        //扩展向上下左右四个方向搜索
        for(int i=0;i<4;++i){
    
            int dx=x+xx[i];
            int dy=y+yy[i];
            //剪枝操作：越界检查以及检查此点是不是陆地
            if(check(dx,dy,grid)){
    
                dfs(dx,dy,grid);
            }
        }
    }
    //剪枝操作
    public boolean check(int x,int y,char [][]grid){
    
       if(x>=0&&x<grid.length&&y>=0&&y<grid[0].length&&grid[x][y]=='1'){
    
            return true;
        }
        return false;
    }
}

3.解题思路：BFS

广度优先搜索与深度优先搜索不同，它是将与某个节点直接相连的其它所有节点依次访问一次之后，再往更深处，进入与其他节点直接相连的节点。

bfs的时候我们常常会借助队列的先进先出，因为从某个节点出发，我们将与它直接相连的节点都加入队列，它们优先进入，则会优先弹出，在它们弹出的时候再将与它们直接相连的节点加入，由此就可以依次按层访问。

用bfs解此题整体思路还是一样的，统计岛屿的方法可以和dfs同样遍历解决，为了去重我们还是要将所有相邻的1一起改成0，这时候同样遍历连通的广度优先搜索（bfs）可以代替dfs。

3.1思路分析

step 1：首先还是要做特例检查，矩阵不能为空*且长度不能为0
step 2：从上到下从左到右遍历矩阵每一个位置的元素，如果该元素值为1，统计岛屿数量。
step 3：使用bfs将遍历矩阵遇到的1以及相邻的1全部置为0：利用一个队列来实现，每次队列把搜索到的第一个1加入队列中，然后然后向此点的上下左右四个方向扩展搜索
step 4：把搜索到的每一个为1的点都标记为0，目的是去重，防止重复搜索
step 5：直至队列为空时，说明此区域的1全被搜索完（都被置为0了）一次广搜结束，代表找到一个岛屿
step 6：回到solution的双重for循环重复step 2,3,4,5步直至矩阵中所有的点都被遍历

3.2核心代码

import java.util.*;

class Node{
    
    int x,y;
    public Node(int x,int y){
    
        this.x=x;
        this.y=y;
    }
}
public class Solution {
    
    /** * 判断岛屿数量 * @param grid char字符型二维数组 * @return int整型 */
    private int ans;
    private int[][]vis;
    private int[] xx={
    -1,1,0,0};
    private int[] yy={
    0,0,-1,1};
    public int solve (char[][] grid) {
    
        // write code here
        int n=grid.length;
        int m=grid[0].length;
        
        vis=new int[n][n];
        for(int i=0;i<n;++i){
    
            for(int j=0;j<m;++j){
    
                if(grid[i][j]=='1'){
    
                    ans++;
                    grid[i][j]='0';
                    bfs(new Node(i,j),grid,n,m);
                }
            }
        }
        return ans;
    }
    void bfs(Node node,char[][] grid,int n,int m){
    
        Queue<Node>q=new LinkedList<Node>();
        q.add(node);
        while(!q.isEmpty()){
    
            Node now=q.poll();
            if(now.x<0&&now.y<0&&now.x>=n&&now.y>=m){
    
                break;
            }
            for(int t=0;t<4;++t){
    
                int dx=now.x+xx[t];
                int dy=now.y+yy[t];
                if(dx>=0&&dy>=0&&dx<n&&dy<m&&grid[dx][dy]=='1'){
    
                    grid[dx][dy]='0';
                    q.add(new Node(dx,dy));
                }
            }
        }
    }
}