[AIGC] 深度优先搜索(DFS)详解及其在LeetCode问题中的应用

深度优先搜索(Depth-First-Search,简称DFS)是一种用于遍历或搜索树或图的算法,其思想是从一个顶点 V0 开始,沿着一条路一直走到底,如果发现不能到达目标解,就退回到上一步的状态,转向另一条路径进行探索,直至找到目标解。


文章目录

      • 深度优先搜索的过程
      • DFS在LeetCode的应用

深度优先搜索的过程

深度优先搜索按照深度的方向进行搜索,先尽可能地沿着一条路走到底,走不通时再回溯到前一个节点,转向下一条路,继续探索,直到所有的节点都访问到,或者找到目标解。其搜索过程可以用一个堆栈来实现,通常用递归的方式来编写算法。

DFS在LeetCode的应用

让我们以LeetCode上的一个例题来展示深度优先搜索的应用:题目编号200,题目名称“岛屿数量”。

问题描述如下:
给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。(岛屿指的是由水围绕的陆地。)

这是一个标准的深度优先搜索题目,解题的思路是我们可以将二维网格看成一个无向图,竖直或水平相邻的 1 之间有边相连。

对于每一个土地格子,我们通过DFS算法寻找每片“岛屿”并将其标记剔除,然后统计可以寻找到的岛屿数量。

下面是该问题的Python代码实现:

class Solution:def numIslands(self, grid: List[List[str]]) -> int:if not grid:return 0count = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == '1':self.dfs(grid, i, j)count += 1return countdef dfs(self, grid, i, j):if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':returngrid[i][j] = '#'self.dfs(grid, i+1, j)self.dfs(grid, i-1, j)self.dfs(grid, i, j+1)self.dfs(grid, i, j-1)

在以上代码中,我们首先扫描整个二维网格。如果一个位置为 ‘1’,则将其加入岛屿计数并将其淹没。接下来,我们通过深度优先搜索淹没与之相连的所有陆地,这样我们可以确保每个岛屿只被计数一次。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/356719.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Django从入门到精通:First [Django版本.Python面向对象.Web基础.创建Django项目]

文章目录 Django初学者指南1 Django简介1.1 Django的历史1.2 使用Django的知名网站1.4 Django的主要特点1.5 Django的工作原理 2 Django 版本选择2.1 Django 支持的 Python 版本2.2 Django 版本 3 Django 开发 Web 程序3.1 Python知识点3.1.1 Python 函数3.1.2 Python 面向对象…

LabVIEW电机故障监测系统

电机作为工业生产中的关键设备&#xff0c;其故障会导致生产停滞和经济损失。因此&#xff0c;开发一个能实时监控电机状态并预测潜在故障的系统具有重要意义。通过高效的数据采集和分析技术&#xff0c;提升故障诊断的准确性和及时性。 系统组成 该系统由以下部分组成&#…

java:JWT的简单例子

【pom.xml】 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId><version>2.3.12.RELEASE</version> </dependency> <dependency><groupId>org.springf…

Map集合之HashMap细说

最近在看面试题&#xff0c;看到了hashmap相关的知识&#xff0c;面试中问的也挺多的&#xff0c;然后我这里记录下来&#xff0c;供大家学习。 Hashmap为什么线程不安全 jdk 1.7中&#xff0c;在扩容的时候因为使用头插法导致链表需要倒转&#xff0c;从而可能出现循环链表问…

JAVA大型医院绩效考核系统源码:​医院绩效考核实施的难点痛点

JAVA大型医院绩效考核系统源码&#xff1a;​医院绩效考核实施的难点痛点 绩效考核数字化综合管理系统是一个基于数字化技术的管理平台&#xff0c;用于帮助企业、机构等组织进行绩效考评的各个环节的管理和处理。它将绩效考评的各个环节集成到一个系统中&#xff0c;包括目标…

常见的宽基指数基金

指数基金投资指南 ❝ 这篇博客里面的内容主要来自于银行螺丝钉的《定投十年&#xff0c;财务自由》和《指数基金投资指南》这两本书中章“常见的宽基指数”&#xff0c;最近第三次读这本书&#xff0c;打算做一点笔记加深自己的印象。 博客中很多内容是从书中摘抄的&#xff0c…

【数据结构】顺序表实操——通讯录项目

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~~ &#x1f4a5;&#x1f4a5;个人主页&#xff1a;奋斗的小羊 &#x1f4a5;&#x1f4a5;所属专栏&#xff1a;C语言 &#x1f680;本系列文章为个人学习…

深入了解 AndroidX ConstraintLayout 中的 Barrier

androidx.constraintlayout.widget.Barrier&#xff08;简称Barrier&#xff09;是 ConstraintLayout 2.0 中引入的一个新特性&#xff0c;它可以极大地简化复杂布局的实现。本文将详细介绍Barrier 的概念、使用方法以及在实际开发中的应用场景。 什么是 Barrier&#xff1f; …

Hallo技术:革新电影、游戏与虚拟现实中的动态肖像动画

在数字娱乐的浪潮中&#xff0c;逼真的动态肖像动画成为了电影制作、游戏开发和虚拟现实等领域不可或缺的一部分。复旦大学研发的Hallo技术&#xff0c;以其独特的扩散模型和分层音频驱动视觉合成模块&#xff0c;为这一领域带来了革命性的突破。 技术概览 Hallo技术是一种基…

安卓开发使用proxyman监控真机

1、真机跟电脑连接到同个网络中 2、手机里面设置代理&#xff0c;代理地址为proxyman上面指示的地址。 3、一般情况下&#xff0c;电脑的对应的端口是没开放的。需要到防火墙里面新建规则。入站规则 选择端口输入上方端口号 这样就能监控到了

任务4.8.4 利用Spark SQL实现分组排行榜

文章目录 1. 任务说明2. 解决思路3. 准备成绩文件4. 采用交互式实现5. 采用Spark项目实战概述&#xff1a;使用Spark SQL实现分组排行榜任务背景任务目标技术选型实现步骤1. 准备数据2. 数据上传至HDFS3. 启动Spark Shell或创建Spark项目4. 读取数据5. 数据转换6. 创建临时视图…

React hydrateRoot如何实现

React 服务器渲染中&#xff0c;hydrateRoot 是核心&#xff0c;它将服务器段的渲染与客户端的交互绑定在一起&#xff0c;我们知道 React 中 Fiber Tree 是渲染的的核心&#xff0c;那么 React 是怎么实现 hydrateRoot 的呢&#xff1f;首先我们验证一下&#xff0c;hydrateRo…

考研计组chap4指令系统

目录 一、指令格式 155 13.操作码地址码 2.按照地址码数量 &#xff08;1&#xff09;零地址指令 &#xff08;2&#xff09;一地址指令 &#xff08;3&#xff09;二地址指令 &#xff08;4&#xff09;三地址指令 &#xff08;5&#xff09;四地址指令 3.指令长度 …

动态规划——买卖股票的最佳时机含冷冻期

1、题目链接 leetcode 309. 买卖股票的最佳时机含冷冻期 2、题目分析 该题有我们可以定义三种状态&#xff0c;买入状态&#xff0c;可交易状态 &#xff0c;冷冻期状态 我们可以建立一个n*3的二维数组来表示这三种状态&#xff1a; 根据这个图可以看出&#xff0c; 可以从…

探索Linux的奇妙世界:第二关---Linux的基本指令1

1. xshell与服务器的连接 想必大家在看过上一期视频时已经搭建好了Linux的环境了并且已经下好了终端---xshell了吧?让我来带大家看一看下好了是什么样子的: 第一次登陆会让你连接你的服务器,就是我们买的云服务器,买完之后需要把公网地址ip复制过来进行链接,需要用户名和密码连…

【从0实现React18】 (一) 项目初始化

Multi-repo 和 Mono-repo 由于需要同时管理多个包&#xff0c;如React、React-dom等&#xff0c;所以选择**Mono-repo** 选择使用pnpm-workspace搭建Mono-repo环境的原因 依赖安装快更规范 Pnpm初始化 npm install -g pnpm pnpm init配置pnpm-workspace.yml文件 pnpm-work…

【单片机毕业设计选题24020】-全自动鱼缸的设计与应用

系统功能: &#xff08;1&#xff09;检测并控制鱼缸水温&#xff0c;水温低于22℃后开启加热&#xff0c;高于28℃后关闭加热。 &#xff08;2&#xff09;定时喂食&#xff0c;每天12点和0点喂食一次&#xff0c;步进电机开启后再关闭模拟喂食。 &#xff08;3&#xff09…

1950 Springboot汽修技能点评系统idea开发mysql数据库APP应用java编程计算机网页源码maven项目

一、源码特点 springboot 汽修技能点评系统是一套完善的信息系统&#xff0c;结合springboot框架和bootstrap完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用springboot框架&#xff08;MVC模式开发&#xff09;&#xff0c;系统 具有完整的源代码和数据库&…

TOPGP-TIPTOP调用外部Webservice

功能要求&#xff1a;ERP作业调用外部系统的webserice更新数据。 演示环境&#xff1a;ERP作业cooi002&#xff08;员工档案&#xff09;录入后更新到外部系统员工档案表。 1、外部系统的WebSerice使用.net搭建 2、在Service.cs中写一个调用方法erp_other erp_other中两个参数…

【实战】Spring Cloud Stream 3.1+整合Kafka

文章目录 前言新版版本优势实战演示增加maven依赖增加applicaiton.yaml配置新增Kafka通道消费者新增发送消息的接口 实战测试postman发送一个正常的消息postman发送异常消息 前言 之前我们已经整合过Spring Cloud Stream 3.0版本与Kafka、RabbitMQ中间件&#xff0c;简直不要太…