代码随想录算法训练Day57|LeetCode200-岛屿数量、LeetCode695-岛屿的最大面积

岛屿数量

题目描述

力扣200-岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

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

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

示例 2：

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

图一

本题思路，是用遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。

那么如果把节点陆地所能遍历到的陆地都标记上呢，就可以使用 DFS，BFS或者并查集。

广度优先搜索 BFS

不少同学用广搜做这道题目的时候，超时了。 这里有一个广搜中很重要的细节：

根本原因是==只要 加入队列就代表 走过，就需要标记，而不是从队列拿出来的时候再去标记走过==。

很多同学可能感觉这有区别吗？

如果从队列拿出节点，再去标记这个节点走过，就会发生下图所示的结果，会导致很多节点重复加入队列。

图二

 `visited[x][y] = true;` 放在的地方，着去取决于我们对 代码中队列的定义，队列中的节点就表示已经走过的节点。 **所以只要加入队列，立即标记该节点走过**。

本题完整广搜代码：

class Solution {
    private static final int[][] dir = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } }; // 四个方向

    private void bfs(char[][] grid, boolean[][] visited, int x, int y) {//用于将当前陆地相连的陆地都进行标记
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] { x, y });
        visited[x][y] = true; // 只要加入队列，立刻标记
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curx = cur[0];// 取出当前节点(curx,cury)
            int cury = cur[1];
            // 遍历四个方向，如果相邻节点(nextx,nexty)在网格内切未被访问过，并且其是陆地（1），则将其加入到队列，并将其标记为已访问
            for (int[] d : dir) {
                int nextx = curx + d[0];
                int nexty = cury + d[1];
                if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length)
                    continue; // 越界了，直接跳过
                if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') {
                    queue.add(new int[] { nextx, nexty });
                    visited[nextx][nexty] = true; // 只要加入队列立刻标记
                }
            }
        } // 循环直到队列为空，即所有与起始点连通的陆地都被标记为已访问
    }

    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] visited = new boolean[n][m];// 二维布尔数组visited，用于标记网格中每个位置是否已被访问过

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == '1') {// 当前位置 未访问过的且是陆地，岛屿数量+1
                    result++; // 遇到没访问过的陆地，+1
                    bfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                }
            }
        }
        return result;
    }
}

深度优先搜索 DFS—模板

//DFS
class Solution {
    private int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向

    private void dfs(char[][] grid, boolean[][] visited, int x, int y) {
        for (int[] d : dir) {
            int nextx = x + d[0];
            int nexty = y + d[1];
            if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;  // 越界了，直接跳过
            if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { // 没有访问过的同时是陆地的
                visited[nextx][nexty] = true; 
                dfs(grid, visited, nextx, nexty);
            } 
        }
    }

    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] visited = new boolean[n][m];

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == '1') { 
                    visited[i][j] = true;
                    result++; // 遇到没访问过的陆地，+1
                    dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                }
            }
        }
        return result;
    }
}

下面的代码使用的是深度优先搜索 DFS 的做法。为了统计岛屿数量同时不重复记录，每当我们搜索到一个岛后，就将这个岛 “淹没” —— 将这个岛所占的地方从 “1” 改为 “0”，这样就不用担心后续会重复记录这个岛屿了。而 DFS 的过程就体现在 “淹没” 这一步中。详见代码：

public int numIslands(char[][] grid) {
    int res = 0; //记录找到的岛屿数量
    for(int i = 0;i < grid.length;i++){
        for(int j = 0;j < grid[0].length;j++){
        	//找到“1”，res加一，同时淹没这个岛
            if(grid[i][j] == '1'){
                res++;
                dfs(grid,i,j);
            }
        }
    }
    return res;
}
//使用DFS“淹没”岛屿
public void dfs(char[][] grid, int i, int j){
	//搜索边界：索引越界或遍历到了"0"
    if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
    //将这块土地标记为"0"
    grid[i][j] = '0';
    //根据"每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成"，对上下左右的相邻顶点进行dfs
    dfs(grid,i - 1,j);
    dfs(grid,i + 1,j);
    dfs(grid,i,j + 1);
    dfs(grid,i,j - 1);
}

岛屿的最大面积

题目描述

力扣695-岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

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

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1：

img

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

示例 2：

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

解题思路

这道题目也是 dfs bfs基础类题目，就是搜索每个岛屿上“1”的数量，然后取一个最大的。

本题思路上比较简单，难点其实都是 dfs 和 bfs的理论基础，关于理论基础我在这里都有详细讲解 ：

DFS理论基础(opens new window)

BFS理论基础

根据BFS模板

//BFS
class Solution {
    private int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 表示四个方向

    void bfs(char[][] grid, boolean[][] visited, int x, int y) {
        Queue<int[]> queue = new LinkedList<>(); // 定义队列
        queue.offer(new int[]{x, y}); // 起始节点加入队列
        visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
        while (!queue.isEmpty()) { // 开始遍历队列里的元素
            int[] cur = queue.poll(); // 从队列取元素
            int curx = cur[0];
            int cury = cur[1]; // 当前节点坐标
            for (int i = 0; i < 4; i++) { // 开始向当前节点的四个方向左右上下去遍历
                int nextx = curx + dir[i][0];
                int nexty = cury + dir[i][1]; // 获取周围四个方向的坐标
                if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;  // 坐标越界了，直接跳过
                if (!visited[nextx][nexty]) { // 如果节点没被访问过
                    queue.offer(new int[]{nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点
                    visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
                }
            }
        }
    }
}

BFS

//BFS
class Solution {
    int[][] dir = {
            { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 }
    };

    int count;
    boolean visited[][];

    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        visited = new boolean[grid.length][grid[0].length];

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (visited[i][j] == false && grid[i][j] == 1) {
                    count = 0;
                    bfs(grid, i, j);
                    res = Math.max(res, count);
                }
            }
        }
        return res;
    }

    private void bfs(int[][] grid, int x, int y) {
        Queue<int[]> queue = new LinkedList<>(); // 定义队列
        queue.offer(new int[] { x, y }); // 起始节点加入队列
        visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
        count++; // 将起始节点也算入岛屿面积中
        while (!queue.isEmpty()) { // 开始遍历队列里的元素
            int[] cur = queue.poll(); // 从队列取元素
            int curx = cur[0];
            int cury = cur[1]; // 当前节点坐标
            for (int i = 0; i < 4; i++) { // 开始向当前节点的四个方向左右上下去遍历
                int nextx = curx + dir[i][0];
                int nexty = cury + dir[i][1]; // 获取周围四个方向的坐标

                if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length)
                    continue;

                if (visited[nextx][nexty] == false && grid[nextx][nexty] == 1) {
                    queue.offer(new int[] { nextx, nexty }); // 队列添加该节点为下一轮要遍历的节点
                    visited[nextx][nexty] = true;
                    count++;
                }
            }
        }
    }

}

根据DFS模板

//DFS
class Solution {
    private int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向

    private void dfs(char[][] grid, boolean[][] visited, int x, int y) {
        for (int[] d : dir) {
            int nextx = x + d[0];
            int nexty = y + d[1];
            if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;  // 越界了，直接跳过
            if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { // 没有访问过的同时是陆地的
                visited[nextx][nexty] = true; 
                dfs(grid, visited, nextx, nexty);
            } 
        }
    }

    public int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] visited = new boolean[n][m];

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == '1') { 
                    visited[i][j] = true;
                    result++; // 遇到没访问过的陆地，+1
                    dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                }
            }
        }
        return result;
    }
}

DFS

//DFS
class Solution {
    private int count;
    private int[][] dir = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } }; // 四个方向

    private void dfs(int[][] grid, boolean[][] visited, int x, int y) {
        for (int[] d : dir) {
            int nextx = x + d[0];
            int nexty = y + d[1];
            if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length)
                continue; // 越界了，直接跳过
            if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 没有访问过的 同时 是陆地的
                visited[nextx][nexty] = true;
                count++;
                dfs(grid, visited, nextx, nexty);
            }
        }
    }

    public int maxAreaOfIsland(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] visited = new boolean[n][m];

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 1; // 因为dfs处理下一个节点，所以这里遇到陆地了就先计数，dfs处理接下来的相邻陆地
                    visited[i][j] = true;
                    dfs(grid, visited, i, j); // 将与其链接的陆地都标记上 true
                    result = Math.max(result, count);
                }
            }
        }
        return result;
    }
}

ps:部分图片和代码来自代码随想录和Leetcode官网

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/778890.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

设计模式之单例模式（Java）

设计模式之单例模式（Java）

单例模式实现方式&#xff1a;懒汉式、饿汉式、双重检查、枚举、静态内部类&#xff1b; 懒汉式&#xff1a; /*** 懒汉式单例模式* author: 小手WA凉* create: 2024-07-06*/ public class LazySingleton implements Serializable {private static LazySingleton lazySinglet…
阅读更多...
操作系统中的权限说明

操作系统中的权限说明

什么是权限 权限在操作系统中是一个重要的功能&#xff0c;它允许你控制谁可以读取、写入或执行某个文件。不同的操作系统和文件系统可能有不同的权限模型&#xff0c;但在类Unix系统&#xff08;如Linux和macOS&#xff09;中&#xff0c;文件权限通常由三部分组成&#xff1a…
阅读更多...
提升系统稳定性：熔断、降级和限流策略详解

提升系统稳定性：熔断、降级和限流策略详解

文章目录 前言一、熔断&#xff08;Circuit Breaker&#xff09;二、降级&#xff08;Degradation&#xff09;三、限流&#xff08;Rate Limiting&#xff09;四、应用案例五、小结推荐阅读 前言 随着互联网业务的快速发展&#xff0c;系统稳定性和高可用性成为现代分布式系统…
阅读更多...
Spring源码十三：非懒加载单例Bean

Spring源码十三：非懒加载单例Bean

上一篇Spring源码十二&#xff1a;事件发布源码跟踪中&#xff0c;我们介绍了Spring中是如何使用观察者设计模式的思想来实现事件驱动开发的&#xff1a;实际上就是将所有监听器注册到广播器中&#xff0c;并通过监听该事件的监听器来处理时间的。结合前面十二篇文章我们将Spri…
阅读更多...
电表读数检测数据集VOC+YOLO格式18156张12类别

电表读数检测数据集VOC+YOLO格式18156张12类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;18156 标注数量(xml文件个数)&#xff1a;18156 标注数量(txt文件个数)&#xff1a;18156 标…
阅读更多...
cs224n作业4

cs224n作业4

NMT结构图&#xff1a;&#xff08;具体结构图&#xff09; LSTM基础知识 nmt_model.py&#xff1a; 参考文章&#xff1a;LSTM输出结构描述 #!/usr/bin/env python3 # -*- coding: utf-8 -*-""" CS224N 2020-21: Homework 4 nmt_model.py: NMT Model Penchen…
阅读更多...
【0基础学爬虫】爬虫基础之scrapy的使用

【0基础学爬虫】爬虫基础之scrapy的使用

【0基础学爬虫】爬虫基础之scrapy的使用 大数据时代&#xff0c;各行各业对数据采集的需求日益增多&#xff0c;网络爬虫的运用也更为广泛&#xff0c;越来越多的人开始学习网络爬虫这项技术&#xff0c;K哥爬虫此前已经推出不少爬虫进阶、逆向相关文章&#xff0c;为实现从易到…
阅读更多...
九浅一深Jemalloc5.3.0 -- ④浅*配置

九浅一深Jemalloc5.3.0 -- ④浅*配置

目前市面上有不少分析Jemalloc老版本的博文&#xff0c;但最新版本5.3.0却少之又少。而且5.3.0的架构与5之前的版本有较大不同&#xff0c;本着“与时俱进”、“由浅入深”的宗旨&#xff0c;我将逐步分析最新release版本Jemalloc5.3.0的实现。 另外&#xff0c;单讲实现代码是…
阅读更多...
多功能工具网站

多功能工具网站

江下科技在线应用-免费PDF转换成Word-word转pdf-无需下载安装 (onlinedo.cn)https://www.onlinedo.cn/
阅读更多...
荞面打造的甜蜜魔法：甜甜圈

荞面打造的甜蜜魔法：甜甜圈

食家巷荞面甜甜圈是一款具有特色的美食。它以荞面为主要原料&#xff0c;相较于普通面粉&#xff0c;荞面具有更高的营养价值&#xff0c;富含膳食纤维、维生素和矿物质。荞面甜甜圈的口感可能会更加扎实和有嚼劲&#xff0c;同时带着荞面特有的谷物香气。在制作过程中&#xf…
阅读更多...
vue侦听器watch（）

vue侦听器watch（）

侦听器watch&#xff08;&#xff09; 侦听器侦听数据变化&#xff0c;我们可以使用watch 选项在每次响应式属性变化时触发一个函数。 <template><h3>侦听器watch</h3><hr> <p>{{nessage}}</p> <button click"exchage">…
阅读更多...
缓存-缓存的使用与基本详解

缓存-缓存的使用与基本详解

1.缓存使用 为了系统性能的提升&#xff0c;我们一般都会将部分数据放入缓存中&#xff0c;加速访问。而db承担数据落盘工作。 哪些数据适合放入缓存&#xff1f; 即时性、数据一致性要求不高的访问量大且更新频率不高的数据&#xff08;读多&#xff0c;写少&#xff09; …
阅读更多...
IDEA安装IDE Eval Reset插件，30天自动续期，无限激活

IDEA安装IDE Eval Reset插件，30天自动续期，无限激活

第一步&#xff1a; 下载idea 注意&#xff1a;版本要是2021.2.2以下 第二步&#xff1a;快捷键CtrlAlts打开设置 第三步&#xff1a;打开下图中蓝色按钮 第四步&#xff1a;点击弹窗的 “” &#xff0c;并输入 plugins.zhile.io 点击 “ok” 第五步&#xff1a;搜索IDE Ea…
阅读更多...
Android ViewPostImeInputStage输入事件处理

Android ViewPostImeInputStage输入事件处理

InputDispatcher向InputChannel使用socket写入输入事件&#xff0c;触发InputEventReceiver调用来接收输入事件。 ViewPostImeInputStage处理view控件的事件 frameworks/base/core/java/android/view/InputEventReceiver.java dispatchInputEvent frameworks/base/core/jav…
阅读更多...
对于老百姓而言VR到底能做什么？

对于老百姓而言VR到底能做什么？

VR技术自诞生以来不断发展&#xff0c;已经广泛应用于教育、医疗、工程、军事、航空、航海、影视、娱乐等方面&#xff0c;譬如&#xff0c;大型工程或军事活动VR预演可以大幅度减少人力物力投入&#xff1b;在航空领域&#xff0c;航天飞行员在训练舱中面对屏幕进行各种驾驶操…
阅读更多...
硅纪元应用评测 | 弱智吧大战GPT4o和Claude 3.5 Sonnet

硅纪元应用评测 | 弱智吧大战GPT4o和Claude 3.5 Sonnet

"硅纪元AI应用测评"栏目&#xff0c;深入解析和评测最新的人工智能应用&#xff0c;提供专业见解和实用建议。不论您是AI专家还是科技爱好者&#xff0c;都能找到权威、详尽的测评&#xff0c;帮助您在快速发展的AI领域中做出最佳选择。一起探索AI的真实潜力&#xf…
阅读更多...
《梦醒蝶飞：释放Excel函数与公式的力量》9.2 FV函数

《梦醒蝶飞：释放Excel函数与公式的力量》9.2 FV函数

9.2 FV函数 FV函数是Excel中用于计算投资或贷款在若干期后的未来值的函数。它是一个非常实用的财务函数&#xff0c;能够帮助我们快速计算投资的最终价值或贷款的期末余额。 9.2.1 函数简介 FV函数用于计算基于定期固定支付和固定利率的投资或贷款的未来值。未来值是指在一定…
阅读更多...
Banana Pi BPI-M4 Berry创建热点和设置静态IP

Banana Pi BPI-M4 Berry创建热点和设置静态IP

create_ap是一个帮助快速创建Linux上的WIFI热点的脚本&#xff0c;并且支持bridge和NAT模式&#xff0c;能够自动结合hostapd, dnsmasq和iptables完成WIFI热点的设置&#xff0c;避免了用户进行复杂的配置&#xff0c;github地址如下&#xff1a; https://github.com/oblique/…
阅读更多...
Django学习第六天

Django学习第六天

启动项目命令 python manage.py runserver 取消模态框功能 js实现列表数据删除 第二种实现思路 使用jquery修改模态框标题 编辑页面拿到数据库数据显示默认数据功能实现 想要去数据库中获取数据时&#xff1a;对象/字典 三种不同的数据类型 使用Ajax传入数据实现表单编辑&…
阅读更多...
【LVGL-SquareLine Studio】

【LVGL-SquareLine Studio】

LVGL-SquareLine Studio ■ SquareLine Studio-官网下载地址■ SquareLine Studio-参考博客■ SquareLine Studio-安装■ SquareLine Studio-汉化■ SquareLine Studio-■ SquareLine Studio-■ SquareLine Studio-■ SquareLine Studio-■ SquareLine Studio- ■ SquareLine S…
阅读更多...
最新文章

Copyright @ 2022~2023