【LeetCode】200、岛屿数量
【LeetCode】200、岛屿数量
文章目录
- 一、并查集
- 1.1 并查集
- 1.2 多语言解法
- 二、洪水填充 DFS
- 2.1 洪水填充 DFS
一、并查集
1.1 并查集
// go
var sets int
var father [90000]intfunc numIslands(grid [][]byte) int {n, m := len(grid), len(grid[0])build(grid, n, m)for i := range n {for j := range m {if grid[i][j] == '1' {if i > 0 && grid[i-1][j] == '1' { // 因为第一行 i == 0, 所以只有 i > 0 时 grid[i-1][j] 才不越界union(idx(m,i,j), idx(m,i-1,j))}if j > 0 && grid[i][j-1] == '1' {union(idx(m,i,j), idx(m,i,j-1))}}}}return sets
}// 编码: 二维变一维, 表示 并查集的 集合编号
// cols 为列的数量
func idx(cols, i, j int) int {return i*cols+j
}// 把1, 新建并查集, 有几个1就有几个集合
func build(grid [][]byte, n, m int) {// 清零全局变量sets = 0for i := range father {father[i] = 0}for i := range n {for j := range m {if grid[i][j] == '1' {idx := idx(m,i,j)father[idx] = idxsets++}}}
}func find(i int) int {if father[i] != i {father[i] = find(father[i])}return father[i]
}func union(a, b int) {fa, fb := find(a), find(b)if fa != fb {father[fa] = fbsets--}
}func isSameSet(a, b int) bool {return find(a) == find(b)
}
参考 左神 并查集
1.2 多语言解法
C p p / G o / P y t h o n / R u s t / J s / T s Cpp/Go/Python/Rust/Js/Ts Cpp/Go/Python/Rust/Js/Ts
// cpp
// go 同上
# python
// rust
// js
// ts
二、洪水填充 DFS
2.1 洪水填充 DFS
若遇到未访问过的陆地则数量++, 并延展此块陆地的最大边界
遇到1则发现岛屿, 通过dfs尽量探索到岛屿的边界, 复杂度O(m*n)
func numIslands(grid [][]byte) (ans int) {m, n := len(grid), len(grid[0])var dfs func(r, c int) dfs = func(r, c int) { // 延展此块陆地的最大边界if r < 0 || r >= m || c < 0 || c >= n {return} // 递归终止条件:越界(无效的网格),则返回if grid[r][c] != '1' {return} // [非 未访问过的陆地](水or已访问过的陆地),则返回grid[r][c] = '2' // 标记已访问过的陆地:防止无限循环无法退出dfs(r-1, c); dfs(r+1, c); dfs(r, c-1); dfs(r, c+1)}for r := 0; r < m; r++ {for c := 0; c < n; c++ {if grid[r][c] == '1' { // 若遇到一个 [未访问过的陆地],则结果+1,并则将其周围四个相连的陆地变为非陆地ans++dfs(r, c)}}}return
}
参考
参考
相关文章:
【LeetCode】200、岛屿数量
【LeetCode】200、岛屿数量 文章目录 一、并查集1.1 并查集1.2 多语言解法 二、洪水填充 DFS2.1 洪水填充 DFS 一、并查集 1.1 并查集 // go var sets int var father [90000]intfunc numIslands(grid [][]byte) int {n, m : len(grid), len(grid[0])build(grid, n, m)for i …...
idea报错:There is not enough memory to perform the requested operation.
文章目录 一、问题描述二、先解决三、后原因(了解) 一、问题描述 就是在使用 IDEA 写代码时,IDEA 可能会弹一个窗,大概提示你目前使用的 IDEA 内存不足,其实就是提醒你 JVM 的内存不够了,需要重新分配。弹…...
python ai ReAct 代理(ReAct Agent)
ReAct 代理(ReAct Agent)是一种结合了推理(Reasoning)和行动(Action)的智能代理框架,旨在通过交互式的方式解决复杂任务。ReAct 的核心思想是让代理在完成任务时,能够动态地推理下一…...
HTML入门教程|| HTML 基本标签(2)
HTML 列表 HTML列表 HTML 无序列表 ul 元素表示无序列表。 ul 元素中的项目使用 li 元素表示。 元素没有在HTML5中定义任何属性,并且您使用CSS控制列表的显示。 HTML5中的 type 和 compact 属性已过时。 您可以在以下代码中查看正在使用的 ul 元素。 <!D…...
MySQL root用户密码忘记怎么办(Reset root account password)
在使用MySQL数据库的的过程中,不可避免的会出现忘记密码的现象。普通用户的密码如果忘记,可以用更高权限的用户(例如root)进行重置。但是如果root用户的密码忘记了,由于root用户本身就是最高权限,那这个方法…...
groovy:多线程 简单示例
在Groovy中,多线程编程与Java非常相似,因为Groovy运行在Java虚拟机(JVM)上,并且可以利用Java的所有并发工具。以下是一些在Groovy中实现多线程编程的方法: class MyThread extends Thread {Overridevoid…...
SOME/IP 协议详解——序列化
文章目录 0. 概述1.基本数据序列化2.字符串序列化2.1 字符串通用规则2.2 固定长度字符串规则2.3 动态长度字符串规则 3.结构体序列化4. 带有标识符和可选成员的结构化数据类型5. 数组5.1 固定长度数组5.2 动态长度数组5.3 Enumeration(枚举)5.4 Bitfield…...
三、GIT与Github推送(上传)和克隆(下载)
GIT与Github推送(上传)和克隆(下载) 一、配置好SSH二、在Github创建仓库三、git克隆(下载)文件四、git推送(上传)文件到远程仓库 一、配置好SSH Git与Github上传和下载时需要使用到…...
18.2、网络安全评测技术与攻击
目录 网络安全测评技术与工具网络安全测评质量管理和标准 网络安全测评技术与工具 漏洞扫描技术可以用于测评,测评你安不安全,也可以用来风险评估安不安全,风险大不大 漏洞扫描包含网络安全漏洞扫描、主机安全漏洞扫描,还有数据…...
在 ArcGIS Pro/GeoScene Pro 中设计专题地图的符号系统
原始 按颜色对面进行符号化 打开符号系统 选择主符号系统 选择字段及其计算方式 更改临界值</...
CSS2笔记
一、CSS基础 1.CSS简介 2.CSS的编写位置 2.1 行内样式 2.2 内部样式 2.3 外部样式 3.样式表的优先级 4.CSS语法规范 5.CSS代码风格 二、CSS选择器 1.CSS基本选择器 通配选择器元素选择器类选择器id选择器 1.1 通配选择器 1.2 元素选择器 1.3 类选择器 1.4 ID选择器 1.5 基…...
移动端如何实现上拉加载
一、理解上拉加载的原理 上拉加载是一种在移动端很常见的交互方式,其原理是当用户在页面上向上滑动(即滚动条接近底部)时,触发一个加载更多数据的操作。这通常涉及到对滚动事件的监听以及判断滚动位置是否达到了触发加载的阈值。…...
【mysql】linux安装mysql客户端
参考文章: MySQL系列之如何在Linux只安装客户端 linux下安装mysql客户端client MySQL Community Downloads 查看linux版本方法: lsb_release -a cat /proc/version下载文件: rpm -ivh mysql-community-*可以删除错误的包: RP…...
YOLOv5部署到web端(flask+js简单易懂)
文章目录 前言最终实现效果图后端实现 主界面检测函数检测结果显示 前端实现 主界面(index.html)显示图片界面 总结 前言 最近,老板让写一个程序把yolov5检测模型部署到web端,在网页直接进行目标检测。经过1个星期的努力,终于实…...
【机器学习】深度学习(DNN)
文章目录 1. 神经网络结构2. 训练步骤3. 反向传播4. 为什么深,而不是宽(模块化)5. 初始化参数能否全为0? 1. 神经网络结构 输入层隐藏层:用于特征转换输出层:用于分类技巧:将网络中的参数写成矩…...
12.30-1-5学习周报
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 文章链接摘要Abstract一、方法介绍1.HAT-CIR2.Horde3.DWGRNet 二、实验总结 文章链接 https://arxiv.org/pdf/2405.04101 摘要 本博客介绍了论文《Continual lea…...
【MySQL】数据操作
数据操作 一、INSERT1、介绍2、语法3、语法介绍4、注意事项5、示例 二、插入否则更新1、介绍2、语法3、语法介绍4、示例 三、ROW_COUNT1、介绍2、示例 四、REPLACE1、介绍2、语法3、示例 五、UPDATE1、介绍2、语法3、示例 六、DELETE1、介绍2、语法3、语法介绍 七、TRUNCATE1、…...
python数据分析:使用pandas库读取和编辑Excel表
使用 Pandas,我们可以轻松地读取和写入Excel 文件,之前文章我们介绍了其他多种方法。 使用前确保已经安装pandas和 openpyxl库(默认使用该库处理Excel文件)。没有安装的可以使用pip命令安装: pip install pandas ope…...
开源轻量级文件分享服务Go File本地Docker部署与远程访问
???欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老…...
异步背后的奥秘:事件循环
异步背后的奥秘:事件循环 复习环节 JavaScript运行时 我们都知道,JavaScript本身是一个单线程的,那JavaScript是如何处理同时发生的多个任务的呢? 首先JavaScript引擎运行在一个容器中,这个容器可能是浏览器或者nod…...
教师评估软件市场迎增长机遇:未来六年CAGR锁定6.7%,教育数字化转型添动能
据恒州诚思调研统计,2025年全球教师评估软件市场规模约30.58亿元,预计未来将持续平稳增长,到2032年市场规模将接近47.92亿元,未来六年复合年增长率(CAGR)为6.7%。在教育行业数字化转型加速的背景下…...
python协同过滤算法的基于python二手物品交易网站系统
目录同行可拿货,招校园代理 ,本人源头供货商协同过滤算法在二手物品交易网站中的应用用户行为数据收集基于用户的协同过滤基于物品的协同过滤混合推荐策略冷启动问题处理实时推荐更新推荐结果评估代码实现示例系统功能整合性能优化项目技术支持源码获取详细视频演示 ࿱…...
AI 视频生成美女跳舞测评 | 顶级 Prompt实测版(Grok Imagine、Kling AI 3.0、Veo 3.1)
兄弟们,AI 视频生成已经卷到飞起了!之前写小黄文靠grok,现在生成“美女舞蹈”视频也得靠它。 今天上手实测截至今天热门的3款视频生成工具,专攻“美女跳舞”这个高难度场景:动作流畅度、人物一致性、性感画面感、提示…...
数据仓库核心建模:星型模型与雪花模型全面对比与实战选择
数据仓库核心建模:星型模型与雪花模型全面对比与实战选择一、引言二、定义:什么是星型模型?什么是雪花模型?2.1 星型模型:定义2.2 雪花模型:定义三、结构流程图:直观对比两种模型3.1 星型模型流…...
酒精测试仪
简 介: 本文介绍了一款酒精测试仪的使用方法。测试仪开机后需等待15秒预热(数字倒计时),预热结束后对着吹气口吹气3秒即可显示测量结果。实验表明,该仪器灵敏度较高:直接吹气显示11左右,不吹气显…...
3步实现AI智能背景移除:开源工具让透明GIF制作变得如此简单
3步实现AI智能背景移除:开源工具让透明GIF制作变得如此简单 【免费下载链接】backgroundremover Background Remover lets you Remove Background from images and video using AI with a simple command line interface that is free and open source. 项目地址:…...
Win10+VS2019环境下vcpkg安装全攻略:从Git克隆到环境变量配置
Win10VS2019环境下vcpkg高效配置指南:从零搭建C开发环境 在Windows平台进行C开发时,第三方库的管理一直是令人头疼的问题。传统的手动下载、配置包含路径和链接库的方式不仅效率低下,还容易引发版本冲突。而vcpkg作为微软推出的跨平台C库管理…...
高效安全的网页资源提取方案:猫抓开源工具的技术实现与专业应用
高效安全的网页资源提取方案:猫抓开源工具的技术实现与专业应用 【免费下载链接】cat-catch 猫抓 浏览器资源嗅探扩展 / cat-catch Browser Resource Sniffing Extension 项目地址: https://gitcode.com/GitHub_Trending/ca/cat-catch 在数字化时代ÿ…...
STM32F4读写SD卡:填一填ST官方HAL库的坑
使用STM32读写SD卡在低功耗存储中的应用是比较常见的,但是网上大多数资料都是基于标准库或者基于寄存器的开发。随着嵌入式设备越来越复杂,使用HAL库能够大大降低开发者的学习成本,从而提高开发效率。近年来,ST官方主推以STM32Cub…...
Windows环境下ODBC连接MySQL保姆级教程(含性能优化配置)
Windows环境下ODBC连接MySQL全流程实战指南 1. 环境准备与驱动安装 在Windows平台使用ODBC连接MySQL数据库,首先需要确保开发环境配置正确。与JDBC不同,ODBC作为跨语言的数据库连接标准,其驱动安装过程需要特别注意版本兼容性问题。以下是环境…...
