【LeetCode】岛屿（周长、数量、最大面积、封闭岛屿数）

た入场券 2023-01-06 01:57 99阅读 0赞

### 文章目录 ###

*   *   *  岛屿的周长★
         *  岛屿数量★★
         *  岛屿数量Ⅱ★★★
         *  岛屿的最大面积★★
         *  统计封闭岛屿的数目★★

--------------------

### 岛屿的周长★ ###

[LeetCode463. 岛屿的周长][LeetCode463.]

【**题目**】给定一个 row x col 的二维网格地图 grid ，其中：grid\[i\]\[j\] = 1 表示陆地， grid\[i\]\[j\] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

【**示例**】

![在这里插入图片描述][20210113194757997.png_pic_center]

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
    输出：16
    解释：它的周长是上面图片中的 16 个黄色的边

【**解题思路**】

方法一：`深度优先遍历DFS`

用`len`表示周长，顺序遍历二维矩阵，当遇到岛屿即`grid[r][c] == 1`时，执行递归

*  如果为岛屿，令`grid[r][c] == -1`，然后递归遍历四个方向
 *  遇到边界、或者陆地`grid[r][c] == 0`时`len+1`（这样只会算**最外围的周长**）

class Solution {
        
        private int len;
        public int islandPerimeter(int[][] grid) {
        
            for(int r = 0; r < grid.length; r++){
        
                for(int c = 0; c < grid[0].length; c++){
        
                    if(grid[r][c] == 1){
        
                        dfs(grid, r, c);
                        return len;
                    }
                }
            }
            return len;
        }
    
        public void dfs(int[][] grid, int r, int c){
        
            if(r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0){
        
                len++;
            }else if(grid[r][c] == 1){
        
                grid[r][c] = -1;
                dfs(grid, r - 1, c);
                dfs(grid, r + 1, c);
                dfs(grid, r, c - 1);
                dfs(grid, r, c + 1);
            }
        }
    }

方法二：数学思维（智力题）

顺序遍历，若为岛屿`len + 4`，且

*  若上面为岛屿，减去重合的两条边`len - 2`
 *  若左面为岛屿，减去重合的两条边`len - 2`

class Solution {
        
        public int islandPerimeter(int[][] grid) {
        
            int len = 0;
            int r = grid.length, c = grid[0].length;
            for(int i = 0; i < r; i++){
        
                for(int j = 0; j < c; j++){
        
                    if(grid[i][j] == 1){
        
                        len +=  4;
                        if(i > 0 && grid[i - 1][j] == 1) len -= 2;
                        if(j > 0 && grid[i][j - 1] == 1) len -= 2;
                    }
                }
            }
            return len;
        }
    }

--------------------

### 岛屿数量★★ ###

[LeetCode200. 岛屿数量][LeetCode200.]

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

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

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

【**示例**】

输入：grid = [
      ["1","1","0","0","0"],
      ["1","1","0","0","0"],
      ["0","0","1","0","0"],
      ["0","0","0","1","1"]
    ]
    输出：3

【解题方法】

顺序遍历，若为岛屿`grid[r][c] == 1`，则`count++`，然后将与此位置岛屿相连的陆地下沉，

下沉函数`sinkLand()`思路如下

*  若遇到边界或者水域，终止
 *  令陆地变为水域`grid[r][c] == 0`，然后递归遍历四个方向

class Solution {
        
        public int numIslands(char[][] grid) {
        
            int count = 0;
            for(int i = 0; i < grid.length; i++){
        
                for(int j = 0; j < grid[i].length; j++){
        
                    if(grid[i][j] == '1'){
        
                        sinkLand(grid, i, j);
                        count++;
                    }
                }
            }
            return count;
        }
    
        public void sinkLand(char[][] grid, int r, int c){
        
            if(r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == '0'){
        
                return;
            }
            grid[r][c] = '0';
            sinkLand(grid, r, c - 1);
            sinkLand(grid, r, c + 1);
            sinkLand(grid, r - 1, c);
            sinkLand(grid, r + 1, c);
        }
    }

--------------------

### 岛屿数量Ⅱ★★★ ###

嘿嘿，VIP题目只能在博客上查看相关描述了

（说明，题目包括图片和示例只是博客上拼接的，解法是套用力扣模板写的 \_）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

输入: m = 3, n = 3, 
    	positions = [[0,0], [0,1], [1,2], [2,1]]
    输出: [1,1,2,3]
    解析:
    起初，二维网格 grid 被全部注入「水」。（0 代表「水」，1 代表「陆地」）
    0 0 0
    0 0 0
    0 0 0
    
    操作 #1：addLand(0, 0) 将 grid[0][0] 的水变为陆地。
    1 0 0
    0 0 0   Number of islands = 1
    0 0 0
    
    操作 #2：addLand(0, 1) 将 grid[0][1] 的水变为陆地。
    1 1 0
    0 0 0   岛屿的数量为 1
    0 0 0
    
    操作 #3：addLand(1, 2) 将 grid[1][2] 的水变为陆地。
    1 1 0
    0 0 1   岛屿的数量为 2
    0 0 0
    
    操作 #4：addLand(2, 1) 将 grid[2][1] 的水变为陆地。
    1 1 0
    0 0 1   岛屿的数量为 3
    0 1 0
    
    拓展：
    你是否能在 O(k log mn) 的时间复杂度程度内完成每次的计算？
    （k 表示 positions 的长度）
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/number-of-islands-ii

【**解题思路**】

方法一：暴力法

每进行一次操作，全图遍历一次，调用**岛屿数量**的代码即可

class Solution {
        
        public int[] numIslands2(int m, int n, int[][] positions) {
        
            int[] res = new int[positions.length()];
            char[][] grid = new int[m][n];
            for(int i = 0; i < positions.length; i++) {
        
                int e = positions[i];
                grid[e[0]][e[1]] = '1';
                //此处调用岛屿数量1中函数
                res[i] = numIslands(grid);
            }
            return res;
        }
    }

方法二：并查集

已在本地编译并测试示例已通过

class Solution {
        
        public int[] numIslands2(int m, int n, int[][] positions) {
        
            int[] res = new int[positions.length];
            int[] parent = new int[m * n];  //将二维矩阵压缩为一维父链接数组
            int[] dirs = {
        0, -1, 0, 1, 0};  //将二维方向压缩为一维
            int num = 0;    //初始岛屿数为0
            char[][] grid = new char[m][n];
            
            for(int i = 0; i < positions.length; i++) {
        
                int[] e = positions[i];
                
                //初始化
                grid[e[0]][e[1]] = '1';
                int p = e[0] * n + e[1];
                parent[p] = p;
                num += 1;
                
                //遍历上下左右四个方向，若为岛屿则合并
                for(int k = 0; k < dirs.length - 1; k++) {
        
                	int x = e[0] + dirs[k];
                	int y = e[1] + dirs[k + 1];
                	if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
        
                		int q = x * n  + y;
                    	int qroot = find(parent, q);
                    	//合并
                    	parent[qroot] = p;
                    	//岛屿数量减一
                    	num -= 1;
                	}
                }
                
                res[i] = num;
            }
            return res;
        }
        
        
        private int find(int[] parent, int p) {
        
        	if(p == parent[p]) return p;
        	return parent[p];
        }
    }

--------------------

### 岛屿的最大面积★★ ###

[LeetCode695. 岛屿的最大面积][LeetCode695.]

【**题目**】给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

【**示例**】

输入：grid = [
      [1, 1, 0, 0, 0],
      [1, 1, 0, 0, 0],
      [0, 0, 1, 0, 0],
      [0, 0, 0, 1, 1]
    ]
    输出：4

【**解题思路**】

同上**岛屿数量**思路，在下沉岛屿时顺便计算其面积

class Solution {
        
        int res = 0;
        public int maxAreaOfIsland(int[][] grid) {
        
            for(int i = 0; i < grid.length; i++){
        
                for(int j = 0; j < grid[0].length; j++){
        
                    if(grid[i][j] == 1){
        
                        res = Math.max(res, dfs(grid, i, j));
                    }
                }
            }
            return res;
        }
        public int dfs(int[][] grid, int r, int c){
        
            if(r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == 0){
        
                return 0;
            }
            grid[r][c] = 0;
            return 1 + dfs(grid, r - 1, c) + dfs(grid, r, c - 1) + dfs(grid, r, c + 1) + dfs(grid, r + 1, c);
        }
    }

--------------------

### 统计封闭岛屿的数目★★ ###

[LeetCode1254. 统计封闭岛屿的数目][LeetCode1254.]

【**题目**】有一个二维矩阵 grid ，每个位置要么是`陆地（记号为 0 ）`要么是`水域（记号为 1 ）`。

我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「**岛屿**」。

如果一座岛屿 完全 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「**封闭岛屿**」。

请返回封闭岛屿的数目。

【**示例**】

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
    输出：2
    解释：灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。

【**解题思路**】

这题与**岛屿数量**相同，只是`边界上的岛屿不计入`而已，判断岛屿深度优先遍历的边界都为水域时计为封闭岛屿

class Solution {
        
        public int closedIsland(int[][] grid) {
        
            int count = 0;
            for(int i = 0; i < grid.length; i++) {
        
                for(int j = 0; j < grid[0].length; j++) {
        
                    if(grid[i][j] == 0) {
        
                        if(dfs(grid, i, j)) count += 1;
                    } 
                }
            }
            return count;
        }
    
        private boolean dfs(int[][] grid, int i, int j) {
        
            //陆地越过边界条件，则不是封闭岛屿，返回false
            if(i < 0 || i == grid.length || j < 0 || j == grid[0].length) {
         
                return false;
            }
            //陆地边界遇到水域，返回true
            if(grid[i][j] == 1) return true;
            grid[i][j] = 1;    //将已经遍历过的岛屿下沉为水域
            boolean top = dfs(grid, i, j - 1);
            boolean bottom = dfs(grid, i, j + 1);
            boolean left = dfs(grid, i - 1, j);
            boolean right = dfs(grid, i + 1, j);
            return top && bottom && left && right;
        }
    }

[LeetCode463.]: https://leetcode-cn.com/problems/island-perimeter/
[20210113194757997.png_pic_center]: /images/20221119/d34bb727b4154c70a294e58f571fd998.png
[LeetCode200.]: https://leetcode-cn.com/problems/number-of-islands/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/683a6e20a4084321adf4f759bce9f08b.png
[LeetCode695.]: https://leetcode-cn.com/problems/max-area-of-island/
[LeetCode1254.]: https://leetcode-cn.com/problems/number-of-closed-islands/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221119/8545cbadfa1c4eb7a66347c1f81c48d6.png