每日一练:LeeCode-200、岛屿数量【DFS递归+BFS队列】

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量

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

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

示例 1:

输入:grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]
输出:1

示例 2:

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

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0''1'

方法1:DFS(系统栈=递归)

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

思路:

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

在这里插入图片描述

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,岛屿的数量加1count++;//然后通过dfs把当前格子的上下左右4//个位置为1的都要置为0,因为他们是连着//一起的算一个岛屿,dfs(grid, i, j);}}//最后返回岛屿的数量return count;
}//这个方法会把当前格子以及他邻近的为1的格子都会置为0
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);//右
}

方法2:BFS(队列)

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

在这里插入图片描述
这题使用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,岛屿的数量加1count++;//然后通过bfs把当前格子的上下左右4//个位置为1的都要置为0,因为他们是连着//一起的算一个岛屿,bfs(grid, i, j);}}return count;
}private void bfs(char[][] grid, int x, int y) {//把当前格子先置为0grid[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);}}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MyBatis:查询与连接池

一、查询 1、多表查询 尽量避免使用多表查询&#xff0c;尤其是对性能要求较高的项目。因为多表查询必然会导致性能变低。 例如&#xff1a;select *from ta运行需要10ms&#xff0c;select *from tb 运行也需要10s。但是&#xff0c;select *from ta left join tb on ta.xx…

python初级第一次作业

一、 dayint(input("enter today day")) fdayint(input("enter num of day since today")) c((fday%7)day)%7 if c0:print("sunday") elif c1:print("monday") elif c2:print("tuesday") elif c3:print("wendnsday&quo…

Jmeter脚本优化——CSV数据驱动文件

使用 CSV 数据文件设置实现参数化注册 1&#xff09; 本地创建 csv 文件&#xff0c;并准备要使用的数据&#xff0c;这里要参数化的是注册的用户名和邮箱。所以在 csv 文件中输入多组用户名和邮箱。 2&#xff09; 通过测试计划或者线程组的右键添加->配置元件->CSV…

多线程合并练习题,线程安全(售票任务引入)--学习JavaEE的day30

day30 练习&#xff08;day29&#xff09; 注意代码注释&#xff0c;里面涉及代码实现遇到问题及解决方案&#xff0c;由于理解方便没有单独出来 1.计算任务 1.计算任务&#xff0c;一个包含了2万个整数的数组&#xff0c;分拆了多个线程来进行并行计算&#xff0c;最后汇总出…

FT232RL/FT232RNL替代GP232RNL USB转UART桥接控制器芯片低成本方案

关注过小编的朋友都知道&#xff0c;之前小编有推荐过FT232RL的替代产品GP232RL&#xff0c;软硬件直接兼容&#xff0c;无需做修改。随着产品的更新迭代&#xff0c;后面也出来了升级版GP232RNL&#xff0c;低成本方案&#xff0c;可直接替代FT232RL/FT232RNL&#xff0c;参数…

【数据结构】线性表的定义与基本操作

&#x1f388;个人主页&#xff1a;豌豆射手^ &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;数据结构 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进…

阿里二面:谈谈ThreadLocal的内存泄漏问题?问麻了。。。。

引言 ThreadLocal在Java多线程编程中扮演着重要的角色&#xff0c;它提供了一种线程局部存储机制&#xff0c;允许每个线程拥有独立的变量副本&#xff0c;从而有效地避免了线程间的数据共享冲突。ThreadLocal的主要用途在于&#xff0c;当需要为每个线程维护一个独立的上下文…

linux之sed编辑器指令练习

目录 一、sed编辑器 二、sed使用案例 1.1 s命令&#xff08;substitute替换&#xff09; 一、sed编辑器 sed编辑器比交互式编辑器快的多&#xff0c;可以简化数据处理任务,sed编辑器并不会修改文件&#xff0c;只会将修改后的数据&#xff0c;输出。 二、sed使用案例 首先…

RK3568平台 iperf3测试网络性能

一.iperf3简介 iperf是一款开源的网络性能测试工具&#xff0c;主要用于测量TCP和UDP带宽性能。它可以在不同的操作系统上运行&#xff0c;包括Windows、Linux、macOS等。iperf具有简单易用、功能强大、高度可配置等特点&#xff0c;广泛应用于网络性能测试、网络故障诊断和网…

【编译tingsboard】出现gradle-maven-plugin:1.0.11:invoke (default)

出现的错误&#xff1a; [ERROR] Failed to execute goal org.thingsboard:gradle-maven-plugin:1.0.11:invoke (default) on project http: Execution default of goal org.thingsboard:gradle-maven-plugin:1.0.11:invoke failed: Plugin org.thingsboard:gradle-maven-plugi…

mysql - 缓存

缓存 InnoDB存储引擎在处理客户端的请求时&#xff0c;当需要访问某个页的数据时&#xff0c;就会把完整的页的数据全部加载到内存中&#xff0c;也就是说即使我们只需要访问一个页的一条记录&#xff0c;那也需要先把整个页的数据加载到内存中。将整个页加载到内存中后就可以…

力扣hot100:207. 课程表

这是一道拓扑排序问题&#xff0c;也可以使用DFS判断图中是否存在环。详情请见&#xff1a;官方的BFS算法请忽略&#xff0c;BFS将问题的实际意义给模糊了&#xff0c;不如用普通拓扑排序思想。 数据结构&#xff1a;图的拓扑排序与关键路径 拓扑排序&#xff1a; class Sol…

交换机高级-端口安全

端口安全 1、一旦接口开启端口安全功能&#xff0c;那么接口所学到的动态MAC就会转换成安全MAC地址&#xff1b; 2、安全MAC地址默认情况下只能学习1个&#xff0c;可以通过命令手动修改学习数量&#xff1b; 3、安全MAC地址没有老化时间&#xff08;但是依然存在内存中&…

2核4g服务器能支持多少人访问?阿里云2核4g服务器在线人数

阿里云2核4G服务器多少钱一年&#xff1f;2核4G配置1个月多少钱&#xff1f;2核4G服务器30元3个月、轻量应用服务器2核4G4M带宽165元一年、企业用户2核4G5M带宽199元一年。可以在阿里云CLUB中心查看 aliyun.club 当前最新2核4G服务器精准报价、优惠券和活动信息。 阿里云官方2…

技术周刊 117 期:Visual Copilot、INP、Kimi 支持 200 万字上下文、Grok 开源、Figure 01、Open Sora 开源

美味值&#xff1a;&#x1f31f;&#x1f31f;&#x1f31f;&#x1f31f;&#x1f31f; 口味&#xff1a;金骏眉 大家好&#xff0c;我是童欧巴。老规矩&#xff0c;咱们先来看技术资讯。 技术资讯 前端 VitePress (早就应该) 1.0 发布MistCSS&#xff0c;只使用 CSS 来…

聚观早报 | 滴滴2023年Q4营收;微软推广Copilot

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 3月25日消息 滴滴2023年Q4营收 微软推广Copilot 极狐汽车将出口西班牙 华为公开智能驾驶新专利 华为P70系列发布…

Luminar Neo:重塑图像编辑新纪元,Mac与Win双平台畅享创意之旅

在数字时代的浪潮中&#xff0c;图像编辑软件已成为摄影师和设计师们不可或缺的创作工具。Luminar Neo&#xff0c;作为一款专为Mac与Windows双平台打造的图像编辑软件&#xff0c;正以其卓越的性能和创新的编辑功能&#xff0c;引领着图像编辑的新潮流。 Luminar Neo不仅继承…

基于nodejs+vue基于hive旅游数据的分析与应用python-flask-django-php

系统阐述的是使用基于hive旅游数据的分析与应用系统&#xff0c;对于nodejs结构、MySql进行了较为深入的学习与应用。主要针对系统的设计&#xff0c;描述&#xff0c;实现和分析与测试方面来表明开发的过程。开发中使用了express框架和MySql数据库技术搭建系统的整体架构。利用…

Kubernetes概念:服务、负载均衡和联网:2. Gateway API

Gateway API 官方文档&#xff1a;https://kubernetes.io/zh-cn/docs/concepts/services-networking/gateway/ Gateway API 通过使用可扩展的、角色导向的、 协议感知的配置机制来提供网络服务。它是一个附加组件&#xff0c; 包含可提供动态基础设施配置和高级流量路由的 API…

vscode添加gitee

1.创建仓库 2.Git 全局设置 3.初始化仓库 2.1 打开vscode打开需要上传到给git的代码文件 2.2.点击左边菜单第三个的源代码管理->初始化仓库 4.点击加号暂存所有更改 5.添加远程仓库 5.1 添加地址&#xff0c;回车 5.2 填写库名&#xff0c;回车 6.提交和推送 6.1 点击✔提交…