JAVA学习 Redis Markdown Transformer reactjs mtu原理 angular material Font Awesome vue绑定点击事件 相亲网站源码 flink教程视频 oracle一键卸载工具 mysql数据库名称 oracle删除字段 cpm计算 hbase集群搭建 java清空数组 网络游戏server编程 mac脚本编辑器 office配置进度 plsql连接mysql数据库 python学习 python高级教程 python学习入门 python操作mysql python怎么下载安装 python中的map函数 python位操作 python创建文件 java抽象 java的接口 java字符串查找 java什么是多态 java原始数据类型 谷歌地球打不开 kmservice 电视免费软件 keytool下载 凤凰刷机 微信骰子表情包
当前位置: 首页 > 学习教程  > 编程语言

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

2021/1/13 19:58:11 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

【LeetCode】岛屿(周长、面积、数量) 岛屿的周长★ LeetCode463. 岛屿的周长 【题目】给定一个 row x col 的二维网格地图 grid ,其中:grid[i][j] 1 表示陆地, grid[i][j] 0 表示水域。 网格中的格子 水平和垂直…

【LeetCode】岛屿(周长、面积、数量)

岛屿的周长★

LeetCode463. 岛屿的周长

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

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

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

示例

在这里插入图片描述

输入: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] == 0len+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. 岛屿数量

题目】给你一个由 ‘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题目只能在博客上查看相关描述了

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

在这里插入图片描述

输入: 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

操作 #1addLand(0, 0) 将 grid[0][0] 的水变为陆地。
1 0 0
0 0 0   Number of islands = 1
0 0 0

操作 #2addLand(0, 1) 将 grid[0][1] 的水变为陆地。
1 1 0
0 0 0   岛屿的数量为 1
0 0 0

操作 #3addLand(1, 2) 将 grid[1][2] 的水变为陆地。
1 1 0
0 0 1   岛屿的数量为 2
0 0 0

操作 #4addLand(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. 岛屿的最大面积

题目】给定一个包含了一些 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. 统计封闭岛屿的数目

题目】有一个二维矩阵 grid ,每个位置要么是陆地(记号为 0 )要么是水域(记号为 1 )

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

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

请返回封闭岛屿的数目。

示例

在这里插入图片描述

输入: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;
    }
}

本文链接: http://www.dtmao.cc/news_show_600224.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?