面试热题(岛屿数量)
给你一个由
'1'(陆地)和'0'(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。
输入:grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"] ] 输出:1
这种题型一般都是按照dfs进行遍历查找,因为一个位置上有8种选择

所以我们应该提前的声明两个数组,一个数组中放x坐标,一个数组放y坐标
//设置方向 上右下左int[] xnum={-1,0,1,0};int[] ynum={0,1,0,-1};

我觉得这东西和扫雷是一个性质

将雷区看做是水域,数字区看成是我们的陆地,以当前节点为中心,往周围漫射(一条路走到底),但是如果

如果我们从A点到B点,如果不加限制的话,我们同样也能从B点到A点,这样就有可能能造成死循环,或者使得最后的效率变慢,所以我们可以采用两种方式
第一种方式:额外的维护一个visited数组,对访问过的地域进行标记
visited=new boolean[row][column];
第二种方式:将访问过的陆地给填充成海域,不需要其他额外的操作
grid[i][j]='0';
如果还不理解题,还可以这样想,假如题目数组中1组成的是由纯净水的组成的管道,我们每次遍历一个地点就是相当于给这些管道中滴了一滴红墨水,红墨水随着水的流动性,不一会这条管道中的纯净水都会变成红颜色的水
//相当于滴红墨水,需要知道该地点的坐标
private void dfs(char[][] grid, int x, int y) {}
//如果是碰到水域,则停止遍历if(grid[x][y]=='0'){return;}//是陆地且没有被访问过,进行访问,并以该地点为中心,漫射if(grid[x][y]=='1'&&!visited[x][y]){visited[x][y]=true;//对于漫射的8种选择for (int i = 0; i <4; i++) {int newx=x+xnum[i];int newy=y+ ynum[i];//越界情况直接继续,不需要执行if(newx<0||newx>=row||newy<0||newy>=column||visited[newx][newy]){continue;}dfs(grid,newx,newy);}
在判断是否是一个新的岛屿,肯定需要满足两个条件:1.是陆地 2.没有被访问过
//开始连接的岛屿,第一个if(!visited[i][j]&&grid[i][j]=='1'){count++;}
碰到新的陆地后,再进行重复的操作
dfs(grid,i,j);
好了,这道题的原理已经讲完,希望对大家能对这道题有一个比较深刻的印象
源码如下:
//设置方向 上右下左int[] xnum={-1,0,1,0};int[] ynum={0,1,0,-1};boolean[][] visited;int row;int column;public int numIslands(char[][] grid) {//对入参进行判断if(grid==null||grid.length==0||grid[0].length==0){return 0;}int count=0;//从每一个点都开始进行遍历row=grid.length;column=grid[0].length;visited=new boolean[row][column];for (int i = 0; i <row; i++) {for (int j = 0; j <column; j++) {//开始连接的岛屿,第一个if(!visited[i][j]&&grid[i][j]=='1'){count++;dfs(grid,i,j);}}}return count;}private void dfs(char[][] grid, int x, int y) {//如果是碰到水域,则停止遍历if(grid[x][y]=='0'){return;}if(grid[x][y]=='1'&&!visited[x][y]){visited[x][y]=true;for (int i = 0; i <4; i++) {int newx=x+xnum[i];int newy=y+ ynum[i];if(newx<0||newx>=row||newy<0||newy>=column||visited[newx][newy]){continue;}dfs(grid,newx,newy);}}}
相关文章:
面试热题(岛屿数量)
给你一个由 1(陆地)和 0(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均…...
【WebRTC---源码篇】(二十四)GCC获取码率后的分配
RtpTransportControllerSend::PostUpdates 配置码率 GoogCcNetworkController::GetPacingRates pacing_factor_默认2.5。也就是说pacer发送报文的码率是探测码率的2.5倍。 PacerConfig GoogCcNetworkController::GetPacingRates(Timestamp at_time) const {// Pacing rate …...
数据可视化工具LightningChart .NET正式发布v10.5.1——拥有全新的3D新功能
LightningChart.NET完全由GPU加速,并且性能经过优化,可用于实时显示海量数据-超过10亿个数据点。 LightningChart包括广泛的2D,高级3D,Polar,Smith,3D饼/甜甜圈,地理地图和GIS图表以及适用于科学…...
AWS认证SAA-C03每日一题
本题库由云计算狂魔微信公众号分享。 【SAA-C03助理级解决方案架构师认证】A company has a multi-tier application that runs six front-end web servers in an Amazon EC2 Auto Scaling group in a single Availability Zone behind an Application Load Balancer(ALB).A …...
ASP.NET Core MVC -- 将视图添加到 ASP.NET Core MVC 应用
Index页 右键单击“视图”文件夹,然后单击“添加”>>“新文件夹”,并将文件夹命名为“HelloWorld”。 右键单击“Views/HelloWorld”文件夹,然后单击“添加”>“新项”。 在“添加新项 - MvcMovie”对话框中: 在右上…...
基于R做宏基因组结果的PCoA分析
写在前面 因为公司给的PCA结果效果不佳,决定从中重新挑选部分样本进行再分析 步骤 表格结果预处理 在属水平genus参考原本结果已有的PCA图,尽可能挑选距离较远且聚团的样本 选取不同样本属水平的丰度数据,整理成逗号分隔的csv文件 代码…...
8.10 算法刷题【1道题】
8.10 算法刷题 22. 链表中环的入口结点(快慢指针) 22. 链表中环的入口结点(快慢指针) 原题链接 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x…...
Apache Maven:从构建到部署,一站式解决方案
目录 一、Maven介绍 1. Maven是什么? 2.Maven的作用? 二、Maven仓库介绍 2.1 库的分类 三、Maven安装与配置 3.1 Maven安装 3.2 Maven环境配置 3.3 仓库配置 四、Eclipse与Maven配置 五、Maven项目测试 5.1 新建Maven项目步骤及注意事项 5.…...
文章四:版本控制策略 - 穿越时光机:Git版本控制进阶技巧
开始本篇文章之前先推荐一个好用的学习工具,AIRIght,借助于AI助手工具,学习事半功倍。欢迎访问:http://airight.fun 概述 版本控制是Git的核心功能,它使得开发者可以记录代码的历史变更,并能够在不同版本…...
爬虫如何应对网站的反爬机制?如何查找user-agent对应的值
import requestsurl https://movie.douban.com/top250 response requests.get(url) # 查看结果 print(response)在requests使用一文中我们有讲到,当状态码不是200时表示爬虫不可用,也就是说我们获取不到网页源代码。但是我们还是可以挣扎一下ÿ…...
一个概率论例题引发的思考
浙江大学版《概率论与梳理统计》一书中的,第13章第1节例2如下: 这个解释和模型比较简单易懂。接下来,第2节的例2是一个关于此模型的题目: 在我自己的理解中,此题的解法跟上一个题目一样,第二级传输后&…...
司徒理财:8.11黄金最新走势分析早盘1914现价多
黄金昨日再次破位新低,但是下跌力度出现衰竭迹象,意味着本次下跌暂时告一段落,行情将会开启一波反弹,早盘1914现价直接多,先看反弹上涨!黄金从走势上看,日线上已经跌至前低附近,也是…...
请写一个非对称加密工具 示例包括完整的通信流程
非对称加密工具通常用于保护数据的机密性和身份验证。下面是一个简化的示例,展示了完整的通信流程,包括密钥生成、加密、解密和数字签名验证: import java.security.KeyPair; import java.security.KeyPairGenerator; import java.security.…...
近地面无人机植被定量遥感与生理参数反演技术
遥感(RS-Remote Sensing)——不接触物体本身,用传感器收集目标物的电磁波信息,经处理、分析后,识别目标物,揭示其几何、物理性质和相互关系及其变化规律的现代科学技术。 换言之,即是“遥远的感…...
卡巴斯基为基于Linux的嵌入式设备推出专用解决方案
导读卡巴斯基在其卡巴斯基嵌入式系统安全产品中引入了对 Linux 的支持。这种适应性强的多层解决方案现在为基于Linux的嵌入式系统、设备和场景提供优化的安全,合通常适用于这些系统的严格监管标准。 卡巴斯基在其卡巴斯基嵌入式系统安全产品中引入了对 Linux 的支持…...
Word转PDF工具哪家安全?推荐好用的文件格式转换工具
Word文档是我们最常见也是最常用的办公软件,想必大家都知道了Word操作起来十分的简单,而且功能也是比较齐全的。随着科技的不断进步,如今也是有越来越多类型的办公文档,PDF就是其中之一,那么word转pdf怎么转?Word转PD…...
dma_mmap_coherent函数的使用
dma_mmap_coherent函数可以将dma地址映射到用户态,通过应用程序直接操作dma地址。 实现应该分配一段dma地址,例如: buf_addr dmam_alloc_coherent(&pdev->dev, size, &dma_addr, GFP_KERNEL);buf_addr 是内核态的虚拟地址&…...
MySQL_DQL语句(查询语句以及常用函数)
基础查询 不带条件的查询查询多个字段 语法: #查询指定字段的数据 SELECT 字段1, 字段2, 字段3 ... FROM 表名 ; #查询表中全部字段的数据 SELECT * FROM 表名 ;案例:查询表中所有信息数据 SELECT * FROM employee;案例:查询表中姓名和性别…...
一步步教你实现JWT认证和授权
一步步教你实现JWT认证和授权 前言一、引入二、Token认证与JWT认证的关系三、什么是JWT认证?四、JWT的组成1、头部(Header)2、载荷(Payload)3、签名(Signature) 五、JWT认证的工作流程六、代码举…...
【python 深度学习】解决遇到的问题
目录 一、RuntimeError: module compiled against API version 0xc but this version of numpy is 0xb 二、AttributeError: module ‘tensorflow’ has no attribute ‘flags’ 三、conda 更新 Please update conda by running 四、to search for alternate channels that…...
避坑指南:在实现LL(1)语法分析器时,SELECT集合计算的那些‘坑’与调试技巧
LL(1)语法分析器实战:SELECT集合计算的七大陷阱与可视化调试方法论 当你按照教科书实现了一个LL(1)语法分析器,却发现它错误地将已知的LL(1)文法判定为非LL(1)文法时,问题往往出在SELECT集合的计算逻辑上。本文将揭示开发者常踩的七个关键陷阱…...
基恩士KV8000系列程序与电芯上料机的精密控制:EtherCAT总线技术、多轴定位与智能管理功能
基恩士KV8000程序 ~ 基恩士KV8000系列程序,KV8000KV-C64XKV-C64T等输入输出模块,KV-XH16EC定位控制模块 电芯上料机 松下A6系列总线控制伺服电机,采用EtherCAT总线控制,绝对定位、相对定位,整台设备13个轴,…...
快速了解智能体
1.了解智能体 这个时代,AI开始已经深入到我们生活中了,智能体的概念也慢慢出现在我们的视野中了。这两个概念并不完全一样。AI 是模拟人类智能的技术领域与能力集合,智能体是依托 AI 实现自主感知、决策、 行动的目标驱动实体,后者…...
OpenCV傅里叶变换实战:图像频域分析与C++实现
1. 傅里叶变换:从数学公式到图像处理 第一次接触傅里叶变换时,我完全被那些复杂的数学公式吓到了。直到后来在实际项目中用它解决了图像去噪问题,才真正理解这个"数学魔法"的威力。简单来说,傅里叶变换就像给图像做X光检…...
汽车电子电气架构演进与关键技术解析
1. 从分布式到域控制:汽车电子电气架构的演进之路 上世纪70年代的汽车电子系统简单得令人难以置信——只有启动装置、车灯和点火系统等基础功能。我拆解过一辆1982年的老式轿车,整个电子系统仅由3个继电器和若干保险丝组成。而如今,一辆高端智…...
Shell应用手册(一) 4.常见Shell版本(bash、zsh、sh,运维主流bash详解)
在Linux/Unix系统中,Shell是用户与内核交互的桥梁,是执行命令、编写脚本的核心工具。对于运维工程师而言,熟练掌握Shell版本的特性与使用方法,是提升工作效率、实现自动化运维的基础。本文将先梳理最常见的3种Shell版本࿰…...
YOLO+SAM工业缺陷检测:从理论到落地的完整方案
YOLOSAM工业缺陷检测:从理论到落地的完整方案一、痛点 PCB质检中,人工标注缺陷边界8分钟/张。YOLO框不准,SAM对工业缺陷水土不服。 二、解决方案 LoRA微调SAM:只改2%参数,速度3倍提升,显存24GB→8GB。 Dice…...
算法岗正在分化:谁在做模型谁在做应用
你这个问题,我先给个结论,一个可能会让你有点意外但绝对是现实的结论:你遇到的情况,不是特例,而是正在迅速成为行业的主流和新常态。你实习干的活,很有可能就是未来几年大多数“AI工程师”或者“算法工程师…...
MIKEURBAN几种错误解决方法
今天小编给大家总结关于MIKEURBAN计算中常见的几种错误吧!错误一MIKE URBAN出现以上的错误时候,我们按照错误提示找出错误点的编号,此时的错误点是由于没有和汇水区做链接导致,重新手动做链接即可解决。错误二MIKE URBAN出现以上的…...
告别重复搬砖!OpenClaw从零搭建可操作系统级AI智能体,自动化提效10倍实战指南
做开发、运维、办公的同学,是不是每天都在被重复的系统操作折磨?每天上班先开固定的5个软件、批量重命名上百个项目文件、服务器日常巡检查日志、Excel数据处理生成周报、重复的键鼠操作填OA表单,这些机械重复的工作,占了每天60%以…...
