《你也能看得懂的Python算法书》学习笔记(五)

2024-04-20 05:32

本文主要是介绍《你也能看得懂的Python算法书》学习笔记(五),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在学习笔记四中我们使用深度优先遍历算法解决了一道以二叉树作为数据结构的题目。笔记五我们继续讲解一道可以使用深度优先遍历算法来解决的问题。

题目描述:我们使用二维数组来表示一片海域,0表示水面,1表示岛屿。我们的任务是找到面积最大的岛屿。下面左图是岛屿的示意图,右图是最大岛屿示意图。

解题思路:

要寻找面积最大的岛屿,我们需要将海域中所有岛屿的面积都计算出来之后进行比较。在计算岛屿的面积之前,我们应该首先了解如何去发现陆地。因为陆地所对应坐标上的值都是1,因此我们可以进行网格式搜索,找到值为一的坐标所对应的地方就是岛屿。

代码如下:

    def maxAreaOfIsland(self, grid):self.maxArea = 0row = len(grid)col = len(grid[0])for i in range(row):for j in range(col):if grid[i][j] == 1:return self.maxArea

找到值为1的地方其实就相当于我们我们登上了岛屿,接下来我们需要测量这个岛屿的面积。由于岛屿是由上下左右这四个方向的陆地组成的,所以我们可以规定一种查找顺序,全部按照上下左右四个方向进行顺序查找。 现在就可以开始用深度优先遍历算法来测算岛屿的面积了,从登陆岛屿的第一个平方米开始就要按照规定的顺序不断地计算岛屿的平方米数,直到走到不能走为止才可以更换方向,为了不重复计算,我们就将修改走过的陆地所对应的值为2。

下面这个例子可以让大家更熟悉这个算法的流程:

首先我们向上寻找,发现已经超出了地图的边界,于是向下寻找发现陆地,便移动过去,这个时候要将数值改成2表示已经访问过。

接着我们在第二块陆地上继续寻找,发现向上没有未访问过的陆地,向下和向左都是海水,最后向右走发现是陆地,于是移动过去。之后继续使用上下左后的顺序进行寻找,发现上方是陆地,于是移动过去。

 

这个时候我们可以发现已经没有陆地了,于是我们退回到上一步的位置,继续换个方式寻找陆地。同样,上一步也没有了,我们就继续后退,直到回到最初点,真个搜索过程结束。这就是深度优先搜索的全部过程。

我们将定义一个函数来表示深度优先算法:

    def dfs(self, k, z, current, grid):grid[k][z] = 2if k > 0 and grid[k - 1][z] == 1:current = self.dfs(k - 1, z, current + 1, grid)if k < (len(grid) - 1) and grid[k + 1][z] == 1:current = self.dfs(k + 1, z, current + 1, grid)if z > 0 and grid[k][z - 1] == 1:current = self.dfs(k, z - 1, current + 1, grid)if z < (len(grid[0]) - 1) and grid[k][z + 1] == 1:current = self.dfs(k, z + 1, current + 1, grid)self.maxArea = max(self.maxArea, current)return current

 最后将网格搜索陆地和在陆地上进行深度优先搜素岛屿面积合并在一起,代码如下:

class solution:def maxAreaOfIsland(self, grid):self.maxArea = 0row = len(grid)col = len(grid[0])for i in range(row):for j in range(col):if grid[i][j] == 1:current = 1self.dfs(i, j, current, grid)return self.maxAreadef dfs(self, k, z, current, grid):grid[k][z] = 2if k > 0 and grid[k - 1][z] == 1:current = self.dfs(k - 1, z, current + 1, grid)if k < (len(grid) - 1) and grid[k + 1][z] == 1:current = self.dfs(k + 1, z, current + 1, grid)if z > 0 and grid[k][z - 1] == 1:current = self.dfs(k, z - 1, current + 1, grid)if z < (len(grid[0]) - 1) and grid[k][z + 1] == 1:current = self.dfs(k, z + 1, current + 1, grid)self.maxArea = max(self.maxArea, current)return current

这篇关于《你也能看得懂的Python算法书》学习笔记(五)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/919388

相关文章

Java学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

如何使用 Python 读取 Excel 数据

《如何使用Python读取Excel数据》:本文主要介绍使用Python读取Excel数据的详细教程,通过pandas和openpyxl,你可以轻松读取Excel文件,并进行各种数据处理操... 目录使用 python 读取 Excel 数据的详细教程1. 安装必要的依赖2. 读取 Excel 文件3. 读

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python ZIP文件操作技巧详解

《PythonZIP文件操作技巧详解》在数据处理和系统开发中,ZIP文件操作是开发者必须掌握的核心技能,Python标准库提供的zipfile模块以简洁的API和跨平台特性,成为处理ZIP文件的首选... 目录一、ZIP文件操作基础三板斧1.1 创建压缩包1.2 解压操作1.3 文件遍历与信息获取二、进阶技

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Python中的getopt模块用法小结

《Python中的getopt模块用法小结》getopt.getopt()函数是Python中用于解析命令行参数的标准库函数,该函数可以从命令行中提取选项和参数,并对它们进行处理,本文详细介绍了Pyt... 目录getopt模块介绍getopt.getopt函数的介绍getopt模块的常用用法getopt模