当前位置: 首页 > news >正文

【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.

文章目录 一、问题描述二、先解决三、后原因&#xff08;了解&#xff09; 一、问题描述 就是在使用 IDEA 写代码时&#xff0c;IDEA 可能会弹一个窗&#xff0c;大概提示你目前使用的 IDEA 内存不足&#xff0c;其实就是提醒你 JVM 的内存不够了&#xff0c;需要重新分配。弹…...

python ai ReAct 代理(ReAct Agent)

ReAct 代理&#xff08;ReAct Agent&#xff09;是一种结合了推理&#xff08;Reasoning&#xff09;和行动&#xff08;Action&#xff09;的智能代理框架&#xff0c;旨在通过交互式的方式解决复杂任务。ReAct 的核心思想是让代理在完成任务时&#xff0c;能够动态地推理下一…...

HTML入门教程|| HTML 基本标签(2)

HTML 列表 HTML列表 HTML 无序列表 ul 元素表示无序列表。 ul 元素中的项目使用 li 元素表示。 元素没有在HTML5中定义任何属性&#xff0c;并且您使用CSS控制列表的显示。 HTML5中的 type 和 compact 属性已过时。 您可以在以下代码中查看正在使用的 ul 元素。 <!D…...

MySQL root用户密码忘记怎么办(Reset root account password)

在使用MySQL数据库的的过程中&#xff0c;不可避免的会出现忘记密码的现象。普通用户的密码如果忘记&#xff0c;可以用更高权限的用户&#xff08;例如root&#xff09;进行重置。但是如果root用户的密码忘记了&#xff0c;由于root用户本身就是最高权限&#xff0c;那这个方法…...

groovy:多线程 简单示例

在Groovy中&#xff0c;多线程编程与Java非常相似&#xff0c;因为Groovy运行在Java虚拟机&#xff08;JVM&#xff09;上&#xff0c;并且可以利用Java的所有并发工具。以下是一些在Groovy中实现多线程编程的方法&#xff1a; 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&#xff08;枚举&#xff09;5.4 Bitfield…...

三、GIT与Github推送(上传)和克隆(下载)

GIT与Github推送&#xff08;上传&#xff09;和克隆&#xff08;下载&#xff09; 一、配置好SSH二、在Github创建仓库三、git克隆&#xff08;下载&#xff09;文件四、git推送&#xff08;上传&#xff09;文件到远程仓库 一、配置好SSH Git与Github上传和下载时需要使用到…...

18.2、网络安全评测技术与攻击

目录 网络安全测评技术与工具网络安全测评质量管理和标准 网络安全测评技术与工具 漏洞扫描技术可以用于测评&#xff0c;测评你安不安全&#xff0c;也可以用来风险评估安不安全&#xff0c;风险大不大 漏洞扫描包含网络安全漏洞扫描、主机安全漏洞扫描&#xff0c;还有数据…...

在 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 基…...

移动端如何实现上拉加载

一、理解上拉加载的原理 上拉加载是一种在移动端很常见的交互方式&#xff0c;其原理是当用户在页面上向上滑动&#xff08;即滚动条接近底部&#xff09;时&#xff0c;触发一个加载更多数据的操作。这通常涉及到对滚动事件的监听以及判断滚动位置是否达到了触发加载的阈值。…...

【mysql】linux安装mysql客户端

参考文章&#xff1a; MySQL系列之如何在Linux只安装客户端 linux下安装mysql客户端client MySQL Community Downloads 查看linux版本方法&#xff1a; lsb_release -a cat /proc/version下载文件&#xff1a; rpm -ivh mysql-community-*可以删除错误的包&#xff1a; RP…...

YOLOv5部署到web端(flask+js简单易懂)

文章目录 前言最终实现效果图后端实现 主界面检测函数检测结果显示 前端实现 主界面(index.html&#xff09;显示图片界面 总结 前言 最近&#xff0c;老板让写一个程序把yolov5检测模型部署到web端&#xff0c;在网页直接进行目标检测。经过1个星期的努力&#xff0c;终于实…...

【机器学习】深度学习(DNN)

文章目录 1. 神经网络结构2. 训练步骤3. 反向传播4. 为什么深&#xff0c;而不是宽&#xff08;模块化&#xff09;5. 初始化参数能否全为0&#xff1f; 1. 神经网络结构 输入层隐藏层&#xff1a;用于特征转换输出层&#xff1a;用于分类技巧&#xff1a;将网络中的参数写成矩…...

12.30-1-5学习周报

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 文章链接摘要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&#xff0c;我们可以轻松地读取和写入Excel 文件&#xff0c;之前文章我们介绍了其他多种方法。 使用前确保已经安装pandas和 openpyxl库&#xff08;默认使用该库处理Excel文件&#xff09;。没有安装的可以使用pip命令安装&#xff1a; pip install pandas ope…...

开源轻量级文件分享服务Go File本地Docker部署与远程访问

???欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老…...

异步背后的奥秘:事件循环

异步背后的奥秘&#xff1a;事件循环 复习环节 JavaScript运行时 我们都知道&#xff0c;JavaScript本身是一个单线程的&#xff0c;那JavaScript是如何处理同时发生的多个任务的呢&#xff1f; 首先JavaScript引擎运行在一个容器中&#xff0c;这个容器可能是浏览器或者nod…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程

鸿蒙电脑版操作系统来了&#xff0c;很多小伙伴想体验鸿蒙电脑版操作系统&#xff0c;可惜&#xff0c;鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机&#xff0c;来体验大家心心念念的鸿蒙系统啦&#xff01;注意&#xff1a;虚拟…...