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

力扣200. 岛屿数量(java DFS解法)

Problem: 200. 岛屿数量

文章目录

  • 题目描述
  • 思路
  • 解题方法
  • 复杂度
  • Code

题目描述

在这里插入图片描述在这里插入图片描述

思路

该问题可以归纳为一类遍历二维矩阵的题目,此类中的一部分题目可以利用DFS来解决,具体到本题目:

1.我们首先要针对于二维数组上的每一个点,尝试展开DFS
2.我们定义一个和给定矩阵一样大的布尔类型的矩阵visited,用于辅助判断是否开展DFS,若是符合的合法点,则设置为true
3.我们在DFS的具体实现中,以每一个点为基础,从该点的上下左右四个方位开始尝试是否DFS

解题方法

1.定义二维辅助数组visited初始化大小为给定数组grid的大小(若在后续操作中标记某一点为true则表示该位置是已经遍历过的合法位置),定义记录岛屿数量的变量count
2.在主函数(numIslands)中我们遍历二维数组中每一个点,当满足visited[i][j] != true && grid[i][j] == '1’时,则代表此处最少存在一个岛屿count加一,再调用DFS函数
3.DFS函数的具体处理:

3.1 每次先将当前合法位置设置为true(visited中),定义一个二维数组**int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};用于记录当前某一位置的点的四个方位(上下左右)
3.2 for循环(范围1~4),循环中每次执行
int newI = i + directions[k][0];int newJ = j + directions[k][1];**用于记录当前位置的新的位置,并判断当前新位置是否合法,若合法则DFS递归调用(在新的位置的基础上)

复杂度

时间复杂度:

O ( m n ) O(mn) O(mn)

空间复杂度:

O ( m n ) O(mn) O(mn)

Code

class Solution {private boolean[][] visited;private int row;private int col;/*** Get all the island counts** @param grid Given a two-dimensional array* @return int*/public int numIslands(char[][] grid) {row = grid.length;col = grid[0].length;visited = new boolean[row][col];//The count of islandint count = 0;for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {if (visited[i][j] != true && grid[i][j] == '1') {count++;dfs(grid, i, j);}}}return count;}/*** Try dfs or not from each point in a two-dimensional array** @param grid Given a two-dimensional array* @param i    Abscissa* @param j    Ordinate*/private void dfs(char[][] grid, int i, int j) {//Record four bearingsint[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//The current legal location is set to truevisited[i][j] = true;for (int k = 0; k < 4; ++k) {int newI = i + directions[k][0];int newJ = j + directions[k][1];if (newI >= 0 && newI < row && newJ >= 0 && newJ < col&& visited[newI][newJ] == false && grid[newI][newJ] == '1') {dfs(grid, newI, newJ);}}}
}

相关文章:

力扣200. 岛屿数量(java DFS解法)

Problem: 200. 岛屿数量 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路 该问题可以归纳为一类遍历二维矩阵的题目&#xff0c;此类中的一部分题目可以利用DFS来解决&#xff0c;具体到本题目&#xff1a; 1.我们首先要针对于二维数组上的每一个点&#xff0c;尝试展…...

解决el-table组件中,分页后数据的勾选、回显问题?

问题描述&#xff1a; 1、记录一个弹窗点击确定按钮后&#xff0c;table列表所有勾选的数据信息2、再次打开弹窗&#xff0c;回显勾选所有保存的数据信息3、遇到的bug&#xff1a;切换分页&#xff0c;其他页面勾选的数据丢失&#xff1b;点击确认只保存当前页的数据&#xff1…...

web网络安全

web安全 一&#xff0c;xss 跨站脚本攻击(全称Cross Site Scripting,为和CSS&#xff08;层叠样式表&#xff09;区分&#xff0c;简称为XSS)是指恶意攻击者在Web页面中插入恶意javascript代码&#xff08;也可能包含html代码&#xff09;&#xff0c;当用户浏览网页之时&…...

若依 ruoyi-vue3 集成aj-captcha实现滑块、文字点选验证码

目录 0. 前言0.1 说明 1. 后端部分1.1 添加依赖1.2. 修改 application.yml1.3. 新增 CaptchaRedisService 类1.4. 添加必须文件1.5. 移除不需要的类1.6. 修改登录方法1.7. 新增验证码开关获取接口1.8. 允许匿名访问 2. 前端部分&#xff08;Vue3&#xff09;2.1. 新增依赖 cryp…...

安卓10 flutter webview 回退会闪退

现象 在安卓10设备上&#xff0c;访问了webview页面后&#xff0c;回退到其他页面后&#xff0c;大概率会闪退&#xff0c;请查看issuses https://github.com/flutter/flutter/issues/78405 解决思路&#xff1a;在回退前&#xff0c;先把webview销毁掉&#xff0c;重新生成一个…...

【Unity入门】物体5种移动方法

目录 一、通过修改位置来实现移动二、通过物理系统实现位移三、通过CharacterController组件四、通过输入控制物体移动 一、通过修改位置来实现移动 利用修改Transform组件的position的两种常用方法。 使用Translate&#xff08;&#xff09;函数 /*物体将向x方向移动1.5单位…...

Elasticsearch的 8.x常用api汇总

ES的查询语法比较复杂,对于初学者需要在不断练习中才会逐渐掌握,本文汇总了ES各种查询语法以及常用api,可以作为新手的实用笔记 首先,安装 Kibana! 下载Elasticsearch,官方下载页面;Elasticsearch 参考,官方文档;<...

k8syaml提供的几个有意思的功能,Kubernetes在线工具网站

k8syaml.cn 提供的几个有意思的功能。 一、yaml资源快速生成 之前编写operator的helm的时候就需要自己写deployment、service、configmap这些资源&#xff0c;那么多字段也记不清&#xff0c;都是先找个模版&#xff0c;然后copy改改&#xff0c;再看官方文档&#xff0c;添加…...

【图像分类】【深度学习】【Pytorch版本】 ResNeXt模型算法详解

【图像分类】【深度学习】【Pytorch版本】 ResNeXt模型算法详解 文章目录 【图像分类】【深度学习】【Pytorch版本】 ResNeXt模型算法详解前言ResNeXt讲解分组卷积(Group Converlution)分割-变换-合并策略(split-transform-merge)ResNeXt模型结构 ResNeXt Pytorch代码完整代码总…...

Android 14 应用适配指南

Android 14 应用适配指南&#xff1a;https://dev.mi.com/distribute/doc/details?pId1718 Android 14 功能和变更列表 | Android 开发者 | Android Developers 1.获取Android 14 1.1 谷歌发布时间表 https://developer.android.com/about/versions/14/overview#timeli…...

【AI美图提示词】第07期效果图,AI人工智能自动绘画,精选绝美版美图欣赏

AI诗配画 山水画中景如画&#xff0c;云雾缭绕峰峦间。桥畔流水潺潺响&#xff0c;诗意盎然山水间。上面的诗句和图片全部来自AI自动化完成&#xff0c;这就是技术的力量&#xff0c;接下来我们进行模型生成学习&#xff1a; 先上原始底图&#xff1a; 下面是模型生成效果图&a…...

前端知识(十三)——JavaScript监听按键,禁止F12,禁止右键,禁止保存网页【Ctrl+s】等操作

禁止右键 document.oncontextmenu new Function("event.returnValuefalse;") //禁用右键禁止按键 // 监听按键 document.onkeydown function () {// f12if (window.event && window.event.keyCode 123) {alert("F12被禁用");event.keyCode 0…...

面向对象设计与分析(28)单例模式的奇异递归模板CRTP实现

前面我们介绍了单例模式的两种实现&#xff1a;懒汉模式和饿汉模式&#xff0c;今天我们以新的方式来实现可复用的单例模式。 奇异递归模板是指父类是个模板类&#xff0c;模板类型是子类类型&#xff0c;即父类通过模板参数可以知道子类的类型。 // brief: a singleton base…...

微信小程序 - 龙骨图集拆分

微信小程序 - 龙骨图集拆分 注意目录结构演示动画废话一下业务逻辑注意点龙骨JSON图集结构 源码分享dragonbones-split.jsdragonbones-split.jsondragonbones-split.wxmldragonbones-split.wxssimgUtil.js 参考资料 注意 只支持了JSON版本 目录结构 演示动画 Spine播放器1.5.…...

使用React 18和WebSocket构建实时通信功能

1. 引言 WebSocket是一种在Web应用中实现双向通信的协议。它允许服务器主动向客户端推送数据&#xff0c;而不需要客户端发起请求。在现代的实时应用中&#xff0c;WebSocket经常用于实时数据传输、聊天功能、实时通知和多人协作等场景。在本篇博客中&#xff0c;我们将探索如…...

vue3使用vue-router嵌套路由(多级路由)

文章目录 1、Vue3 嵌套路由2、项目结构3、编写相关页面代码3.1、编写route文件下 index.ts文件3.2、main.ts文件代码&#xff1a;3.3、App.vue文件代码&#xff1a;3.4、views文件夹下的Home文件夹下的index.vue文件代码&#xff1a;3.5、views文件夹下的Home文件夹下的Tigerhh…...

openGauss学习笔记-164 openGauss 数据库运维-备份与恢复-导入数据-使用COPY FROM STDIN导入数据-处理错误表

文章目录 openGauss学习笔记-164 openGauss 数据库运维-备份与恢复-导入数据-使用COPY FROM STDIN导入数据-处理错误表164.1 操作场景164.2 查询错误信息164.3 处理数据导入错误 openGauss学习笔记-164 openGauss 数据库运维-备份与恢复-导入数据-使用COPY FROM STDIN导入数据-…...

QT Widget - 随便画个圆

简介 实现在界面中画一个圆, 其实目的是想画一个LED效果的圆。代码 #include <QApplication> #include <QWidget> #include <QPainter> #include <QColor> #include <QPen>class LEDWidget : public QWidget { public:LEDWidget(QWidget *pare…...

js输入框部分内容不可编辑,其余正常输入,el-input和el-select输入框和多个下拉框联动后的内容不可修改

<tr>//格式// required自定义指令<e-td :required"!read" label><span>地区&#xff1a;</span></e-td><td>//v-if"!read && this.data.nationCode 148"显示逻辑<divclass"table-cell-flex"sty…...

分布式文件存储系统minio了解下

什么是minio minio 是一个基于 Apache License v2.0 开源协议的对象存储服务。非常适合于存储大容量非结构化的数据&#xff0c;例如图片、视频、日志文件、备份数据和容器/虚拟机镜像等&#xff0c;而一个对象文件可以是任意大小。 是一种海量、安全、低成本、高可靠的云存储…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...