Leetcode热题100:图论

Leetcode 200. 岛屿数量

深度优先搜索法:

对于这道题来说,是一个非常经典的图的问题,我们可以先从宏观上面来看问题,也就是说在不想具体算法的前提下,简单的说出如何找到所有的岛屿呢?

如图中所示,首先非常显而易见的要素就是我们一定要遍历图中的每一个坐标,这是肯定的,然后呢对于岛屿的数量,一开始想的肯定就是每当我们访问了一个1的坐标时,我们就找到了一个岛屿,可是因为我们要遍历整个图,所以肯定不能每次遇到一个1就对岛屿的数量进行增加,因为题目说了,横纵连接着的坐标都是1的话都属于同一个岛屿,就像上图一样证明我们只有三个岛屿

那么我们是不是可以像一个办法,当我们找到了一个岛屿的坐标后,把属于这个坐标的岛屿的其他所有值为1的坐标都记录下来,这样以来,意思就是说在我们继续遍历的时候,我们检查每一个坐标时,如果发现这个坐标已经被标记过了,证明他并不是一个新的岛屿而是一个之前就发现过的岛屿的一部分那么就可以了

如何去实现这个标记的方法呢,就可以用到我们的深度优先搜索,从新发现的坐标开始一直找,直到找到了岛屿的边缘或者整个图的边缘之后返回,这样就能找到所有属于相同岛屿的坐标,那么我们可以把主代码写出来了已经

class Solution:def numIslands(self, grid: List[List[str]]) -> int:res = 0# iterate to check every box in the grid to see# if it is a start for a new lslandfor r in range(len(grid)):for c in range(len(grid[0])):# if so, run a dfs to mark all its fellow# box and add the 1 to the resultif grid[r][c] == '1':dfs(grid, r, c)res = res + 1return res

主体部分的代码非常简单,然后呢我们需要做的就是对于dfs的编写,正如在这个主体代码中写的,你会发现我这里还是用的如果box中存的元素是1,那就最终要增加岛屿数量,这难道不是错的吗?其实这里就隐喻了我们是如何完成对一个岛屿上所有的box进行标记的,与其新建一个空间例如集合然后把dfs中搜索到的box全都加入进去然后每一次循环遍历的时候去看当前的box是否在那个集合中,更好的方法其实就是直接原地更改我们的grid,将搜索到的box中的值从1修改到2,这样这个主体函数中的if 语句就不会被execute了

class Solution:def numIslands(self, grid: List[List[str]]) -> int:def dfs(grid, r, c):# base case, do nothing when we# reached the edge of entire grid or found waterif not (0 <= r < len(grid) and 0 <= c < len(grid[0])) or grid[r][c] != '1':return# mark the visited box as 2grid[r][c] = '2'# call the recursive case on each direction from current boxdfs(grid, r - 1, c)dfs(grid, r + 1, c)dfs(grid, r, c - 1)dfs(grid, r, c + 1)res = 0# iterate to check every box in the grid to see# if it is a start for a new lslandfor r in range(len(grid)):for c in range(len(grid[0])):# if so, run a dfs to mark all its fellow# box and add the 1 to the resultif grid[r][c] == '1':dfs(grid, r, c)res = res + 1return res

这样你就有了整个的代码,其实这种类型的深度优先搜索可以参考我们在二叉树的时候是怎么做的,无非也是一直遍历然后直到我们reach 到了leaf node然后发现新的node是空的时候就直接return,这里不过是多加了两个方向,在二叉树里的recursive case是对左右子节点继续call,这里是对上下左右四个横纵坐标的方向继续call,然后呢条件多加了一个,这里对应的不能超出边界就是二叉树中的if not root, 只是这里还要保证grid[r][c] == 1,不是1的话就不是我们要找的同一个岛屿上的点

时间复杂度 O(m*n):m和n就是grid的长和宽,因为我们要遍历每一个坐标

空间复杂度 O(m*n):在最坏的情况下,如果左上角的box就是陆地1,并且整张图都是1,                                       那么我们就要把每一个box都有一个recursive function,这样在就会用                                     到一个大小为m*n的栈


Leetcode 994. 腐烂的橘子

广度优先搜索法:

这道题的关键在于我们在一开始所给的grid里面存在多个橘子的可能,我们需要在把能弄腐烂的橘子全部弄完之后就返回结果,所以每一分钟里我们需要对所有当前的橘子进行扩散,这里运用深度优先的递归就很麻烦,因为我们每一次逻辑要处理多个搜索

这里我们就使用广度优先,利用队列来对腐烂橘子进行保存并且通过出队来进行遍历然后扩散后把新的腐烂的橘子继续加入队列

这样以来,每一次我们通过向四个方向的检查中发现新的好橘子之后就可以立马对其进行操作,具体分三步,第一步将其加入我们的队列代表下一轮遍历的时候,他会pop出来作为新的坐标然后向四周扩散,第二步将我们的好橘子的count做一个递减,第三步,将grid中其坐标位置的值从1变成2避免后序的遍历中反复visit这个坏橘子

class Solution:def orangesRotting(self, grid: List[List[int]]) -> int:# we are using a queue to do the bfsq = deque()fresh_count = 0res = 0# loop through the gird first to find # the amount of fresh and add the rotten to# the queuefor i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == 1:fresh_count = fresh_count + 1elif grid[i][j] == 2:q.append((i, j))# loop until we have no more rotten orangewhile q and fresh_count > 0:# every time we start pop out q again, we did another searchres = res + 1# for each rotten orango, pop them outfor _ in range(len(q)):box = q.popleft()r, c = box[0], box[1]# check topif r - 1 >= 0 and grid[r - 1][c] == 1:fresh_count = fresh_count - 1q.append((r - 1, c))grid[r - 1][c] = 2# check rightif c + 1 < len(grid[0]) and grid[r][c + 1] == 1:fresh_count = fresh_count - 1q.append((r, c + 1))grid[r][c + 1] = 2# check botif r + 1 < len(grid) and grid[r + 1][c] == 1:fresh_count = fresh_count - 1q.append((r + 1, c))      grid[r + 1][c] = 2# check leftif c - 1 >= 0 and grid[r][c - 1] == 1:fresh_count = fresh_count - 1q.append((r, c - 1))grid[r][c - 1] = 2# we did not get them all rottonif fresh_count > 0:return -1else:return res

时间复杂度 O(m*n):m和n就是grid的长和宽,因为我们要遍历每一个坐标

空间复杂度 O(m*n):在最坏的情况下,一开始所有的橘子都是坏橘子,我们使用的额外空间队列的长度最大就是m*n

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

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

相关文章

初识React(一)从井字棋游戏开始

写在前面&#xff1a; 磨磨唧唧了好久终于下定决心开始学react&#xff0c;刚刚接触感觉有点无从下脚...新的语法新的格式跟vue就像两种物种...倒是很好奇路由和store是怎么实现的了~v~&#xff0c;一点一点来吧&#xff01;&#xff01;&#xff01; (一)创建项目 使用vite…

FreeRtos学习笔记(12)systemView 分析任务调度情况

FreeRtos学习笔记&#xff08;12&#xff09;systemView 分析任务调度情况 使用stm32f429 freertosV10.5.1 systemView 3.5 keil AC5 systemView 移植 从官网下载 systemView 软件 将下面文件添加到工程中 freertos 修改 systemView 需要 FreeRTOSConfig.h 开启如下宏, …

Affinity Photo:像素大师,影像重塑者 mac/win版

在数字图像处理领域&#xff0c;Affinity Photo已经崭露头角&#xff0c;成为许多专业摄影师和图像设计师的首 选工具。这款软件不仅具备丰富的功能和强大的性能&#xff0c;还提供了直观易用的操作界面&#xff0c;让用户能够轻松实现高质量的图像处理。 Affinity Photo软件获…

如何在iOS系统抓取log

前言&#xff1a;因为作者目前工作领域和苹果智能家居有关&#xff0c;然后发现一些bug其实是apple sdk原生code的问题&#xff0c;所以需要给apple提radar单&#xff0c;就需要抓ios端Log充当证据给apple看&#xff0c;其实ios抓log非常简单&#xff0c;大家感兴趣可以学习下哦…

众邦科技CRMEB商城商业版任意文件写入getshell 0day

代码审计 接口&#xff1a;/adminapi/system/crud 处理的代码如下 public function save(SystemCrudDataService $service, $id 0){$data $this->request->postMore([[pid, 0],//上级菜单id[menuName, ],//菜单名[tableName, ],//表名[modelName, ],//模块名称[table…

NAT---网络地址转换技术

Network Address Translation 1、起源&#xff1a;ip地址不够用 2、作用&#xff1a;让私网地址映射成公网地址&#xff0c;进而访问网络。 3、私网Ip地址的范围&#xff1a; A类&#xff1a;10.0.0.0-10.255.255.255 B类&#xff1a;172.16.0.0-172.31.255.255 C类&…

论文精读 | 2024 [ICLR] TimeMixer: 可分解多尺度融合的时间序列预测

论文标题&#xff1a;TimeMixer: Decomposable Multiscale Mixing for Time Series Forecasting 作者&#xff1a;Shiyu Wang&#xff08;王世宇&#xff09;, Haixu Wu&#xff08;吴海旭&#xff09;, Xiaoming Shi, Tengge Hu, Huakun Luo, Lintao Ma, James Y. Zhang, and…

【进阶五】Python实现SDVRP(需求拆分)常见求解算法——禁忌搜索+模拟退火算法(TS+SA)

基于python语言&#xff0c;采用经典禁忌搜索&#xff08;TS&#xff09;模拟退火&#xff08;SA&#xff09;对 需求拆分车辆路径规划问题&#xff08;SDVRP&#xff09; 进行求解。 目录 往期优质资源1. 适用场景2. 代码调整3. 求解结果3.1 TS3.2 SA 4. 代码片段参考 往期优质…

MySQL索引(图文并茂)

目录 一、索引的概念 二、索引的作用 三、创建索引的原则依据 四、索引的分类和创建 1、索引的分类 2、索引的创建 2.1 普通索引 2.1.1 直接创建索引 2.1.2 修改表方式创建 2.1.3 创建表的时候指定索引 2.2 唯一索引 2.2.1 直接创建唯一索引 2.2.2 修改表方式创建 …

C 多维数组

C 语言支持多维数组。多维数组声明的一般形式如下&#xff1a; type name[size1][size2]...[sizeN];例如&#xff0c;下面的声明创建了一个三维 5 . 10 . 4 整型数组&#xff1a; int threedim[5][10][4];二维数组 多维数组最简单的形式是二维数组。一个二维数组&#xff0c…

每秒批量插入10000条数据到MySQL中,资源消耗(带宽、IOPS)有多少?

文章目录 &#x1f50a;博主介绍&#x1f964;本文内容起因代码资源情况改造 &#x1f4e2;文章总结&#x1f4e5;博主目标 &#x1f50a;博主介绍 &#x1f31f;我是廖志伟&#xff0c;一名Java开发工程师、Java领域优质创作者、CSDN博客专家、51CTO专家博主、阿里云专家博主、…

Redis入门到实战-第十二弹

Redis实战热身Bitfields篇 完整命令参考官网 官网地址 声明: 由于操作系统, 版本更新等原因, 文章所列内容不一定100%复现, 还要以官方信息为准 https://redis.io/Redis概述 Redis是一个开源的&#xff08;采用BSD许可证&#xff09;&#xff0c;用作数据库、缓存、消息代理…

Elasticsearch:使用在本地计算机上运行的 LLM 以及 Ollama 和 Langchain 构建 RAG 应用程序

无需 GPU 的隐私保护 LLM。在本博客中&#xff0c;我将演示使用不同的工具 Ollama 构建的 RAG 应用程序。 与本文相关的所有源代码均已发布在 github上。 请克隆存储库以跟随文章操作。我们可以通过如下的方式来克隆&#xff1a; git clone https://github.com/liu-xiao-guo/o…

Unity 学习笔记 5.控制飞机飞行

目录 1.摄像机跟随的方法 2.鼠标按键响应 3.键盘按键响应 4.导入素材 5.让飞机向前飞 6.摄像机跟随飞机移动 7.鼠标控制飞机倾斜 8.键盘控制飞机飞行 下载源码 UnityPackage 1.摄像机跟随的方法 2.鼠标按键响应 3.键盘按键响应 4.导入素材 下载素材 步骤&#xff1a; 将…

itextPdf生成pdf简单示例

文章环境 jdk1.8&#xff0c;springboot2.6.13 POM依赖 <dependency><groupId>com.itextpdf</groupId><artifactId>itextpdf</artifactId><version>5.5.13</version></dependency><dependency><groupId>com.ite…

3/21 work

自由发挥登录窗口的应用场景&#xff0c;实现一个登录窗口界面。&#xff08;不要使用课堂上的图片和代码&#xff0c;自己发挥&#xff0c;有利于后面项目的完成&#xff09; 要求&#xff1a; 1. 需要使用Ui界面文件进行界面设计 2. ui界面上的组件相关设置&#xff0c;通…

网络——套接字编程UDP

目录 端口号 源端口号和目的端口号 认识TCP协议和UDP协议 网络字节序 socket编程接口 socket常见接口 sockaddr结构 UDP socket bind recvfrom sendto 编写客户端 绑定INADDR_ANY 实现聊天功能 端口号 在这之前我们已经说过源IP地址和目的IP地址&#xff0c;还有…

【vue核心技术实战精讲】1.6 - 1.8 VUE 指令 (中)

文章目录 前言 本节内容1、v-on使用v-on好处效果 2、事件修饰符2.1、按键码 (<font color red>已废弃&#xff0c;不用研究)示例效果 3、v-for 列表渲染示例效果 前言 上节,我们学习了 Vue指令之v-text 、 v-html、v-if 、v-show、v-bind 点击进入上一节 本节内容 Vue…

敏捷开发——第二次作业JS/服务器的部署

部署 Web 服务器 1. 安装 Apache HTTP 服务器并部署静态网页应用 ⭐⭐ 默认情况下&#xff0c;Apache 在 /var/www/html 目录下寻找要提供服务的文件。可以将静态网页文件放置在这个目录下 2.安装 Nginx 并部署静态页面应用 3. 实践部分 1. 2. 3. 在 /var/www/html 目录下…

matlab 条件数的倒数

目录 一、概述1、算法概述2、主要函数3、参考文献二、条件设置错误的矩阵的敏感度三、求解单位矩阵的条件四、参考链接本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫。 一、概述 1、算法概述