讨论/《队列 & 栈》 - 岛屿数量/
《队列 & 栈》 - 岛屿数量
共 11 个回复

1,DFS解决

这题让求的是岛屿的面积,二维数组中值是1的都是岛屿,如果多个1是连着的,那么他们只能算一个岛屿

最简单的一种方式就是遍历数组中的每一个值,如果是1就说明是岛屿,然后把它置为0或者其他的字符都可以,只要不是1就行,然后再遍历他的上下左右4个位置。如果是1,说明这两个岛屿是连着的,只能算是一个岛屿,我们还要把它置为0,然后再以它为中心遍历他的上下左右4个位置……。

如果是0,就说明不是岛屿,就不在往他的上下左右4个位置遍历了。这里就以示例1为例来看一下
image.png
每个位置只要是1,先要把它置为0,然后沿着他的上下左右4个方向继续遍历,执行同样的操作,要注意边界条件的判断。代码比较简单,来看下

public int numIslands(char[][] grid) {
    //边界条件判断
    if (grid == null || grid.length == 0)
        return 0;
    //统计岛屿的个数
    int count = 0;
    //两个for循环遍历每一个格子
    for (int i = 0; i < grid.length; i++)
        for (int j = 0; j < grid[0].length; j++) {
            //只有当前格子是1才开始计算
            if (grid[i][j] == '1') {
                //如果当前格子是1,岛屿的数量加1
                count++;
                //然后通过dfs把当前格子的上下左右4
                //个位置为1的都要置为0,因为他们是连着
                //一起的算一个岛屿,
                dfs(grid, i, j);
            }
        }
    //最后返回岛屿的数量
    return count;
}

//这个方法会把当前格子以及他邻近的为1的格子都会置为1
public void dfs(char[][] grid, int i, int j) {
    //边界条件判断,不能越界
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0')
        return;
    //把当前格子置为0,然后再从他的上下左右4个方向继续遍历
    grid[i][j] = '0';
    dfs(grid, i - 1, j);//上
    dfs(grid, i + 1, j);//下
    dfs(grid, i, j + 1);//左
    dfs(grid, i, j - 1);//右
}

看一下运行结果
image.png


2,BFS解决

DFS就是沿着一条路径一直走下去,当遇到终止条件的时候才会返回,而BFS就是先把当前位置附近的访问一遍,就像下面这样先访问圈内的,然后再把圈放大继续访问,就像下面这样

image.png

这题使用BFS和DFS都能解决,如果遇到位置为1的格子,只要能把他们挨着的为1的全部置为0,然后挨着的挨着的为1的位置也置为0,然后……一直这样循环下去,看下代码

public int numIslands(char[][] grid) {
    //边界条件判断
    if (grid == null || grid.length == 0)
        return 0;
    //统计岛屿的个数
    int count = 0;
    //两个for循环遍历每一个格子
    for (int i = 0; i < grid.length; i++)
        for (int j = 0; j < grid[0].length; j++) {
            //只有当前格子是1才开始计算
            if (grid[i][j] == '1') {
                //如果当前格子是1,岛屿的数量加1
                count++;
                //然后通过bfs把当前格子的上下左右4
                //个位置为1的都要置为0,因为他们是连着
                //一起的算一个岛屿,
                bfs(grid, i, j);
            }
        }
    return count;
}

private void bfs(char[][] grid, int x, int y) {
    //把当前格子先置为0
    grid[x][y] = '0';
    int n = grid.length;
    int m = grid[0].length;
    //使用队列,存储的是格子坐标转化的值
    Queue<Integer> queue = new LinkedList<>();
    //我们知道平面坐标是两位数字,但队列中存储的是一位数字,
    //所以这里是把两位数字转化为一位数字
    int code = x * m + y;
    //坐标转化的值存放到队列中
    queue.add(code);
    while (!queue.isEmpty()) {
        //出队
        code = queue.poll();
        //在反转成坐标值(i,j)
        int i = code / m;
        int j = code % m;
        if (i > 0 && grid[i - 1][j] == '1') {//上
            //如果上边格子为1,把它置为0,然后加入到队列中
            //下面同理
            grid[i - 1][j] = '0';
            queue.add((i - 1) * m + j);
        }
        if (i < n - 1 && grid[i + 1][j] == '1') {//下
            grid[i + 1][j] = '0';
            queue.add((i + 1) * m + j);
        }
        if (j > 0 && grid[i][j - 1] == '1') { //左
            grid[i][j - 1] = '0';
            queue.add(i * m + j - 1);
        }
        if (j < m - 1 && grid[i][j + 1] == '1') {//右
            grid[i][j + 1] = '0';
            queue.add(i * m + j + 1);
        }
    }
}


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

9

BFS

class Solution {
    private int[] dx = {-1, 1, 0, 0};
    private int[] dy = {0, 0, -1, 1};

    public int numIslands(char[][] grid) {
        int cnt = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j);
                    cnt++;
                }
            }
        }
        return cnt;
    }

    private void bfs(char[][] grid, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            i = cur[0];
            j = cur[1];
            if (0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {
                grid[i][j] = '0';
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    queue.offer(new int[]{x, y});
                }
            }
        }
    }
}
1

DFS

class Solution {
    private int[] dx = {-1, 1, 0, 0};
    private int[] dy = {0, 0, -1, 1};

    public int numIslands(char[][] grid) {
        int cnt = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    cnt++;
                }
            }
        }
        return cnt;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {
            grid[i][j] = '0';
            for (int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                dfs(grid, x, y);
            }
        }
    }
}
1

js dfs

 const direction = [[0, 1], [0, -1], [-1, 0], [1, 0]];
 function DFS (grid, pos) {
    let x = pos[0];
    let y = pos[1];
    if(x < 0 || x > grid.length-1 || y < 0 || y > grid[0].length-1 || grid[x][y] == '0')
        return;
    grid[x][y] = '0';
    for(item of direction) {
        let nx, ny;
        nx = x  + item[0];
        ny = y  + item[1];
        DFS(grid, [nx, ny]);
    }
 }
var numIslands = function(grid) {
    let count = 0;
    for(let x = 0; x < grid.length; x++) {
        for(let y = 0; y < grid[0].length; y++) {
            if(grid[x][y] == '1') {
                count ++;
                DFS(grid, [x,y]);
            }
        }
    }
    return count;
};

//bfs解法

class Solution {
    public int numIslands(char[][] grid) {

        int row = grid.length;
        int col = grid[0].length;
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    bfs (grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public void bfs(char[][] grid, int x, int y) {
        int row = grid.length;
        int col = grid[0].length;
        Queue<Integer> q = new LinkedList<>();
        int[] dx = new int[]{-1, 1, 0 ,0};
        int[] dy = new int[]{0, 0, -1, 1};

        q.add (x * col + y);
        while (!q.isEmpty ()) {
            int sz = q.size ();
            for (int i = 0; i < sz; i++) {
                int num = q.poll ();
                int a = num / col;
                int b = num % col;
                
                grid[a][b] = '0';
                for (int j = 0; j < 4; j++) {
                    int m = a + dx[j];
                    int n = b + dy[j];
                    if (m >= 0 && m < row && n >= 0 && n < col && grid[m][n] == '1') {
                        bfs (grid, m, n);
                    }
                }
            }
        }
    }
}

dfs

class Solution {
public:
    void dfs(vector<vector<char>>& grid,int x,int y){
        //将搜过的陆地块置为0
        int m = grid.size();
        int n =grid[0].size();
        //终止条件
        if(x<0||y<0||x>m-1||y>n-1||grid[x][y]=='0') return;
        grid[x][y]='0';
        dfs(grid,x+1,y);
        dfs(grid,x,y+1);
        dfs(grid,x-1,y);
        dfs(grid,x,y-1);

    }
    int numIslands(vector<vector<char>>& grid) {
        int ans = 0;
        int m = grid.size();
        int n =grid[0].size();
        //初始化种子点
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                //初始化
                if(grid[i][j] == '1'){
                    ans++;//计算种子点个数
                    dfs(grid,i,j);
                }
            }
        return ans;
    }
};
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int ans = 0;
        int m = grid.size();
        int n =grid[0].size();
        queue<pair<int,int>> q;//存要走的点
        vector<pair<int,int>> dirs{{1,0},{0,1},{-1,0},{0,-1}};//可能要走的四个方向
        //初始化种子点
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                //初始化
                if(grid[i][j] != '0'){
                    q.push({i,j});
                    grid[i][j]='0';
                    ans++;//计算种子点个数
                }
                while(!q.empty()){
                    int size=q.size();
                        auto cur=q.front();
                        for(auto dir:dirs){
                            int x = cur.first + dir.first;
                            int y= cur.second + dir.second;
                            if(x<0||y<0||x>m-1||y>n-1||grid[x][y] == '0') continue;
                            q.push({x,y});
                            grid[x][y]='0';
                        }
                        q.pop();
                }
            }
        return ans;
    }
};

这道题理解以后,稍微改那么一步两步就能用于后面的求陆地数量的题了。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int res = 0;
        for(int i = 0; i< grid.size(); ++i){
            for(int j = 0; j < grid[0].size(); ++j){
                if(grid[i][j] == '1'){ //如果所在位置是岛屿,就可以++了,因为走过的岛屿已经被变为海水了
                    ++res;
                    dfs(grid, i, j);
                }
            }
        }
        return res;
    }

    void dfs(vector<vector<char>>& grid, int i, int j){
        //递归中止条件(要么超出边界,要么所到位置为‘0’)
        //i == row, j == col;
        if(i < 0 || j < 0 || i == grid.size() || j == grid[0].size() || grid[i][j] == '0')
            return;

        grid[i][j] = '0';//探索过的陆地将他变为海水
        int dir_i[4] = {-1,1,0,0}, dir_j[4] = {0,0,-1,1};//上下左右四个方向
        for(int idx = 0; idx < 4; ++idx)
            dfs(grid, i+dir_i[idx], j+dir_j[idx]);//控制四个方向的递归
        return;
    }
};

执行用时:12 ms, 在所有 C++ 提交中击败了98.37%的用户
内存消耗:9.2 MB, 在所有 C++ 提交中击败了75.76%的用户

class Solution
{
public:
    int numIslands(vector<vector<char>> &grid)
    {
        int count = 0;
        for(int i = 0; i < grid.size();i++)
        {
            for(int k = 0; k < grid[0].size();k++)
            {
                if(grid[i][k] == '1')
                {
                    count++;
                    dfs(grid,i,k);
                }
            }
        }
        return count;
    }
    void dfs(vector<vector<char>> &grid, int m, int n)
    {
        int y = grid[0].size();
        int x = grid.size();
        if (m < x - 1 && grid[m + 1][n] == '1')
        {
            grid[m + 1][n] = '0';
            dfs(grid, m + 1, n);
        }
        if (m > 0 && grid[m - 1][n] == '1')
        {
            grid[m -1][n] = '0';
            dfs(grid, m - 1, n);
        }
        if (n < y - 1 && grid[m][n + 1] == '1')
        {
            grid[m][n + 1] = '0';
            dfs(grid, m , n + 1);
        }
        if (n > 0 && grid[m][n - 1] == '1')
        {
            grid[m][n-1] = '0';
            dfs(grid, m , n -1 );
        }
    }
};

<Python3>: DFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or len(grid) == 0:
            return 0
        m, n = len(grid), len(grid[0])
        count = 0

        def dfs(grid, i, j):
            if i<0 or i>m-1 or j<0 or j>n-1 or grid[i][j]=='0':
                return False
            grid[i][j] = '0'
            dfs(grid, i-1, j)
            dfs(grid, i+1, j)
            dfs(grid, i, j-1)
            dfs(grid, i, j+1)

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    dfs(grid, i, j)
        return count