力扣200. 岛屿数量(java DFS解法)

发布时间:2023年12月18日

Problem: 200. 岛屿数量

题目描述

在这里插入图片描述在这里插入图片描述

思路

该问题可以归纳为一类遍历二维矩阵的题目,此类中的一部分题目可以利用DFS来解决,具体到本题目:

1.我们首先要针对于二维数组上的每一个点,尝试展开DFS
2.我们定义一个和给定矩阵一样大的布尔类型的矩阵visited,用于辅助判断是否开展DFS,若是符合的合法点,则设置为true
3.我们在DFS的具体实现中,以每一个点为基础,从该点的上下左右四个方位开始尝试是否DFS

解题方法

1.定义二维辅助数组visited初始化大小为给定数组grid的大小(若在后续操作中标记某一点为true则表示该位置是已经遍历过的合法位置),定义记录岛屿数量的变量count
2.在主函数(numIslands)中我们遍历二维数组中每一个点,当满足visited[i][j] != true && grid[i][j] == '1’时,则代表此处最少存在一个岛屿count加一,再调用DFS函数
3.DFS函数的具体处理:

3.1 每次先将当前合法位置设置为true(visited中),定义一个二维数组**int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};用于记录当前某一位置的点的四个方位(上下左右)
3.2 for循环(范围1~4),循环中每次执行
int newI = i + directions[k][0];int newJ = j + directions[k][1];**用于记录当前位置的新的位置,并判断当前新位置是否合法,若合法则DFS递归调用(在新的位置的基础上)

复杂度

时间复杂度:

O ( m n ) O(mn) O(mn)

空间复杂度:

O ( m n ) O(mn) O(mn)

Code

class Solution {
    private boolean[][] visited;
    private int row;
    private int col;

    /**
     * Get all the island counts
     *
     * @param grid Given a two-dimensional array
     * @return int
     */
    public int numIslands(char[][] grid) {
        row = grid.length;
        col = grid[0].length;
        visited = new boolean[row][col];
        //The count of island
        int count = 0;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (visited[i][j] != true && grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }

    /**
     * Try dfs or not from each point in a two-dimensional array
     *
     * @param grid Given a two-dimensional array
     * @param i    Abscissa
     * @param j    Ordinate
     */
    private void dfs(char[][] grid, int i, int j) {
        //Record four bearings
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        //The current legal location is set to true
        visited[i][j] = true;
        for (int k = 0; k < 4; ++k) {
            int newI = i + directions[k][0];
            int newJ = j + directions[k][1];
            if (newI >= 0 && newI < row && newJ >= 0 && newJ < col
                    && visited[newI][newJ] == false && grid[newI][newJ] == '1') {
                dfs(grid, newI, newJ);
            }
        }
    }
}
文章来源:https://blog.csdn.net/LNsupermali/article/details/135052606
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。