当前位置: 首页 > 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;而一个对象文件可以是任意大小。 是一种海量、安全、低成本、高可靠的云存储…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...

用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章

用 Rust 重写 Linux 内核模块实战&#xff1a;迈向安全内核的新篇章 ​​摘要&#xff1a;​​ 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言&#xff0c;受限于 C 语言本身的内存安全和并发安全问题&#xff0c;开发复杂模块极易引入难以…...

高抗扰度汽车光耦合器的特性

晶台光电推出的125℃光耦合器系列产品&#xff08;包括KL357NU、KL3H7U和KL817U&#xff09;&#xff0c;专为高温环境下的汽车应用设计&#xff0c;具备以下核心优势和技术特点&#xff1a; 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计&#xff0c;确保在…...