欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode——200.岛屿数量

程序员文章站 2022-04-07 12:27:20
...

题目

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

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

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

深搜思路

一开始本来没什么思路,然后百度了一下,看看这种题型是如何解答的,就是搜到陆地的时候,以该节点为起点,把周围跟他相连接的陆地全部给置为1即可。又一次打败了心魔,本来以前自己看到这种题就觉得害怕,冲冲冲!

代码

class Solution {

    //方向数组,右下左上
    static int d_x[]={0,1,0,-1};
    static int d_y[]={1,0,-1,0};
    static int row;
    static int colomn;
    static int ans;


    public int numIslands(char[][] grid) {
        if (grid==null || grid.length==0 || grid[0].length==0)
            return 0;

        ans=0;//岛屿数目
        row=grid.length;
        colomn=grid[0].length;

        for (int i=0;i<row;++i)
            for (int j=0;j<colomn;++j)
                if (grid[i][j]=='1')
                {
                    ++ans;
                    dfs(i,j,grid);
                }
        return ans;
    }

    public static void dfs(int x,int y,char[][]grid)
    {
        grid[x][y]='0';//把搜索到的点置为0
        int temp_x=0;
        int temp_y=0;
        for (int i=0;i<=3;++i)
        {
            temp_x=x+d_x[i];
            temp_y=y+d_y[i];
            if (temp_x>=0 && temp_x<row && temp_y>=0 && temp_y<colomn && grid[temp_x][temp_y]=='1')//陆地
            {
                dfs(temp_x,temp_y,grid);
            }
        }
    }
}

结果

LeetCode——200.岛屿数量
ac了,这次相比于以往的搜索题,不用有标记数组,一开始以为还是得要,后来发现,标记数组没什么用,就不加了,偷懒,真香!!

广搜思路

进行搜索,搜到1的,就在当前位置进行广搜,把相连的为1的点都加到队列中即可。因为这里开了标记数组,会比较慢一点。

代码

import java.util.LinkedList;
import java.util.Queue;

class Point{
    int x;
    int y;
}

class Solution {

    //方向数组,右下左上
    static int d_x[]={0,1,0,-1};
    static int d_y[]={1,0,-1,0};
    static int row;
    static int colomn;
    static int ans;// 岛屿数量
    static int visited[][];//标记数组
    static Queue<Point> queue=new LinkedList();

    public int numIslands(char[][] grid) {
        if (grid==null || grid.length==0 || grid[0].length==0)
            return 0;

        ans=0;//岛屿数目
        row=grid.length;
        colomn=grid[0].length;
        queue.clear();
        visited=new int[row][colomn];
        for (int i=0;i<row;++i) {
            for (int j = 0; j < colomn; ++j)
            {
                visited[i][j]=0;//没有访问过
                if (grid[i][j] == '1')
                {
                    ++ans;
                    Point temp = new Point();
                    temp.x = i;
                    temp.y = j;
                    queue.offer(temp);
                    while (!queue.isEmpty())
                    {
                        int a = queue.peek().x; //队首的横坐标
                        int b = queue.peek().y; //队首的纵坐标
                        grid[a][b] = '0';//改为水
                        for (int k = 0; k <= 3; ++k)
                        {
                            //队首的四个方向的临时坐标
                            int temp_a = a + d_x[k];
                            int temp_b = b + d_y[k];
                            if (temp_a >= 0 && temp_a < row && temp_b >= 0 && temp_b < colomn && grid[temp_a][temp_b] == '1' && visited[temp_a][temp_b]==0)
                            {
                                Point h = new Point();
                                h.x = temp_a;
                                h.y = temp_b;
                                visited[temp_a][temp_b]=1;//访问了
                                queue.offer(h);
                            }
                        }
                        queue.poll();
                    }
                }
            }
        }
        return ans;
    }
}

结果

LeetCode——200.岛屿数量
虽然ac了,可是广搜的时间比深搜的时间还要慢,其实是不应该的。应该是开了标记数组的缘故,看了题解,它那种没有标记数组,挺好的。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    grid[r][c] = '0';
                    queue<pair<int, int>> neighbors;
                    neighbors.push({r, c});
                    while (!neighbors.empty()) {
                        auto rc = neighbors.front();
                        neighbors.pop();
                        int row = rc.first, col = rc.second;
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {
                            neighbors.push({row-1, col});
                            grid[row-1][col] = '0';
                        }
                        if (row + 1 < nr && grid[row+1][col] == '1') {
                            neighbors.push({row+1, col});
                            grid[row+1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {
                            neighbors.push({row, col-1});
                            grid[row][col-1] = '0';
                        }
                        if (col + 1 < nc && grid[row][col+1] == '1') {
                            neighbors.push({row, col+1});
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }

        return num_islands;
    }
};
相关标签: 模拟题