- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章DFS 算法秒杀五道岛屿问题由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
岛屿问题是经典的面试高频题,虽然基本的岛屿问题并不难,但是岛屿问题有一些有意思的扩展,比如求子岛屿数量,求形状不同的岛屿数量等等,本文就来把这些问题一网打尽.
岛屿系列问题的核心考点就是用 DFS/BFS 算法遍历二维数组.
本文主要来讲解如何用 DFS 算法来秒杀岛屿系列问题,不过用 BFS 算法的核心思路是完全一样的,无非就是把 DFS 改写成 BFS 而已.
那么如何在二维矩阵中使用 DFS 搜索呢?如果你把二维矩阵中的每一个位置看做一个节点,这个节点的上下左右四个位置就是相邻节点,那么整个矩阵就可以抽象成一幅网状的「图」结构.
根据 学习数据结构和算法的框架思维,完全可以根据二叉树的遍历框架改写出二维矩阵的 DFS 代码框架:
因为二维矩阵本质上是一幅「图」,所以遍历的过程中需要一个visited布尔数组防止走回头路,如果你能理解上面这段代码,那么搞定所有岛屿问题都很简单.
这里额外说一个处理二维数组的常用小技巧,你有时会看到使用「方向数组」来处理上下左右的遍历,和前文 图遍历框架 的代码很类似:
这种写法无非就是用 for 循环处理上下左右的遍历罢了,你可以按照个人喜好选择写法.
这是力扣第 200 题「岛屿数量」,最简单也是最经典的一道岛屿问题,题目会输入一个二维数组grid,其中只包含0或者1,0代表海水,1代表陆地,且假设该矩阵四周都是被海水包围着的.
我们说连成片的陆地形成岛屿,那么请你写一个算法,计算这个矩阵grid中岛屿的个数,函数签名如下:
比如说题目给你输入下面这个grid有四片岛屿,算法应该返回 4:
思路很简单,关键在于如何寻找并标记「岛屿」,这就要 DFS 算法发挥作用了,我们直接看解法代码:
为什么每次遇到岛屿,都要用 DFS 算法把岛屿「淹了」呢?主要是为了省事,避免维护visited数组.
因为dfs函数遍历到值为0的位置会直接返回,所以只要把经过的位置都设置为0,就可以起到不走回头路的作用.
PS:这类 DFS 算法还有个别名叫做 FloodFill 算法,现在有没有觉得 FloodFill 这个名字还挺贴切的~ 。
这个最最基本的岛屿问题就说到这,我们来看看后面的题目有什么花样.
上一题说二维矩阵四周可以认为也是被海水包围的,所以靠边的陆地也算作岛屿.
力扣第 1254 题「统计封闭岛屿的数目」和上一题有两点不同:
1、用0表示陆地,用1表示海水.
2、让你计算「封闭岛屿」的数目。所谓「封闭岛屿」就是上下左右全部被1包围的0,也就是说靠边的陆地不算作「封闭岛屿」.
函数签名如下:
比如题目给你输入如下这个二维矩阵:
算法返回 2,只有图中灰色部分的0是四周全都被海水包围着的「封闭岛屿」.
那么如何判断「封闭岛屿」呢?其实很简单,把上一题中那些靠边的岛屿排除掉,剩下的不就是「封闭岛屿」了吗?
有了这个思路,就可以直接看代码了,注意这题规定0表示陆地,用1表示海水:
只要提前把靠边的陆地都淹掉,然后算出来的就是封闭岛屿了.
PS:处理这类岛屿问题除了 DFS/BFS 算法之外,Union Find 并查集算法也是一种可选的方法,前文 Union Find 算法运用 就用 Union Find 算法解决了一道类似的问题.
这道岛屿题目的解法稍微改改就可以解决力扣第 1020 题「飞地的数量」,这题不让你求封闭岛屿的数量,而是求封闭岛屿的面积总和.
其实思路都是一样的,先把靠边的陆地淹掉,然后去数剩下的陆地数量就行了,注意第 1020 题中1代表陆地,0代表海水:
篇幅所限,具体代码我就不写了,我们继续看其他的岛屿问题.
这是力扣第 695 题「岛屿的最大面积」,0表示海水,1表示陆地,现在不让你计算岛屿的个数了,而是让你计算最大的那个岛屿的面积,函数签名如下:
比如题目给你输入如下一个二维矩阵:
其中面积最大的是橘红色的岛屿,算法返回它的面积 6.
这题的大体思路和之前完全一样,只不过dfs函数淹没岛屿的同时,还应该想办法记录这个岛屿的面积.
我们可以给dfs函数设置返回值,记录每次淹没的陆地的个数,直接看解法吧:
解法和之前相比差不多,我也不多说了,接下来的两道岛屿问题是比较有技巧性的,我们重点来看一下.
如果说前面的题目都是模板题,那么力扣第 1905 题「统计子岛屿」可能得动动脑子了:
这道题的关键在于,如何快速判断子岛屿?肯定可以借助 Union Find 并查集算法 来判断,不过本文重点在 DFS 算法,就不展开并查集算法了.
什么情况下grid2中的一个岛屿B是grid1中的一个岛屿A的子岛?
当岛屿B中所有陆地在岛屿A中也是陆地的时候,岛屿B是岛屿A的子岛.
反过来说,如果岛屿B中存在一片陆地,在岛屿A的对应位置是海水,那么岛屿B就不是岛屿A的子岛.
那么,我们只要遍历grid2中的所有岛屿,把那些不可能是子岛的岛屿排除掉,剩下的就是子岛.
依据这个思路,可以直接写出下面的代码:
这道题的思路和计算「封闭岛屿」数量的思路有些类似,只不过后者排除那些靠边的岛屿,前者排除那些不可能是子岛的岛屿.
这是本文的最后一道岛屿题目,作为压轴题,当然是最有意思的.
力扣第 694 题「不同的岛屿数量」,题目还是输入一个二维矩阵,0表示海水,1表示陆地,这次让你计算 不同的 (distinct) 岛屿数量,函数签名如下:
比如题目输入下面这个二维矩阵:
其中有四个岛屿,但是左下角和右上角的岛屿形状相同,所以不同的岛屿共有三个,算法返回 3.
很显然我们得想办法把二维矩阵中的「岛屿」进行转化,变成比如字符串这样的类型,然后利用 HashSet 这样的数据结构去重,最终得到不同的岛屿的个数.
如果想把岛屿转化成字符串,说白了就是序列化,序列化说白了遍历嘛,前文 二叉树的序列化和反序列化 讲了二叉树和字符串互转,这里也是类似的.
首先,对于形状相同的岛屿,如果从同一起点出发,dfs函数遍历的顺序肯定是一样的.
因为遍历顺序是写死在你的递归函数里面的,不会动态改变:
所以,遍历顺序从某种意义上说就可以用来描述岛屿的形状,比如下图这两个岛屿:
假设它们的遍历顺序是:
下,右,上,撤销上,撤销右,撤销下 。
如果我用分别用1, 2, 3, 4代表上下左右,用-1, -2, -3, -4代表上下左右的撤销,那么可以这样表示它们的遍历顺序:
2, 4, 1, -1, -4, -2 。
你看,这就相当于是岛屿序列化的结果,只要每次使用dfs遍历岛屿的时候生成这串数字进行比较,就可以计算到底有多少个不同的岛屿了.
要想生成这段数字,需要稍微改造dfs函数,添加一些函数参数以便记录遍历顺序:
dir记录方向,dfs函数递归结束后,sb记录着整个遍历顺序,其实这就是前文 回溯算法核心套路 说到的回溯算法框架,你看到头来这些算法都是相通的.
有了这个dfs函数就好办了,我们可以直接写出最后的解法代码:
这样,这道题就解决了,至于为什么初始调用dfs函数时的dir参数可以随意写,这里涉及 DFS 和回溯算法的一个细微差别,前文 图算法基础 有写,这里就不展开了.
以上就是全部岛屿系列问题的解题思路,也许前面的题目大部分人会做,但是最后两题还是比较巧妙的,希望本文对你有帮助.
原文链接:https://mp.weixin.qq.com/s/IZQkb-M27dt-AZ1VICThOw 。
最后此篇关于DFS 算法秒杀五道岛屿问题的文章就讲到这里了,如果你想了解更多关于DFS 算法秒杀五道岛屿问题的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
关闭。这个问题是off-topic .它目前不接受答案。 想要改进这个问题? Update the question所以它是on-topic用于堆栈溢出。 关闭 12 年前。 Improve thi
我有一个动态网格,其中的数据功能需要正常工作,这样我才能逐步复制网格中的数据。假设在第 5 行中,我输入 10,则从第 6 行开始的后续行应从 11 开始读取,依此类推。 如果我转到空白的第一行并输入
我有一个关于我的按钮消失的问题 我已经把一个图像作为我的按钮 用这个函数动画 function example_animate(px) { $('#cont
我有一个具有 Facebook 连接和经典用户名/密码登录的网站。目前,如果用户单击 facebook_connect 按钮,系统即可运行。但是,我想将现有帐户链接到 facebook,因为用户可以选
我有一个正在为 iOS 开发的应用程序,该应用程序执行以下操作 加载和设置注释并启动核心定位和缩放到位置。 map 上有很多注释,从数据加载不会花很长时间,但将它们实际渲染到 map 上需要一段时间。
我被推荐使用 Heroku for Ruby on Rails 托管,到目前为止,我认为我真的会喜欢它。只是想知道是否有人可以帮助我找出问题所在。 我按照那里的说明在该网站上创建应用程序,创建并提交
我看过很多关于 SSL 错误的帖子和信息,我自己也偶然发现了一个。 我正在尝试使用 GlobalSign CA BE 证书通过 Android WebView 访问网页,但出现了不可信错误。 对于大多
我想开始使用 OpenGL 3+ 和 4,但我在使用 Glew 时遇到了问题。我试图将 glew32.lib 包含在附加依赖项中,并且我已将库和 .dll 移动到主文件夹中,因此不应该有任何路径问题。
我已经盯着这两个下载页面的源代码看了一段时间,但我似乎找不到问题。 我有两个下载页面,一个 javascript 可以工作,一个没有。 工作:http://justupload.it/v/lfd7不是
我一直在使用 jQuery,只是尝试在单击链接时替换文本字段以及隐藏/显示内容项。它似乎在 IE 中工作得很好,但我似乎无法让它在 FF 中工作。 我的 jQuery: $(function() {
我正在尝试为 NDK 编译套接字库,但出现以下两个错误: error: 'close' was not declared in this scope 和 error: 'min' is not a m
我正在使用 Selenium 浏览器自动化框架测试网站。在测试过程中,我切换到特定的框架,我们将其称为“frame_1”。后来,我在 Select 类中使用了 deselectAll() 方法。不久之
我正在尝试通过 Python 创建到 Heroku PostgreSQL 数据库的连接。我将 Windows10 与 Python 3.6.8 和 PostgreSQL 9.6 一起使用。 我从“ht
我有一个包含 2 列的数据框,我想根据两列之间的比较创建第三列。 所以逻辑是:第 1 列 val = 3,第 2 列 val = 4,因此新列值什么都没有 第 1 列 val = 3,第 2 列 va
我想知道如何调试 iphone 5 中的 css 问题。 我尝试使用 firelite 插件。但是从纵向旋转到横向时,火石占据了整个屏幕。 有没有其他方法可以调试 iphone 5 中的 css 问题
所以我有点难以理解为什么这不起作用。我正在尝试替换我正在处理的示例站点上的类别复选框。我试图让它做以下事情:未选中时以一种方式出现,悬停时以另一种方式出现(选中或未选中)选中时以第三种方式出现(而不是
Javascript CSS 问题: 我正在使用一个文本框来写入一个 div。我使用以下 javascript 获取文本框来执行此操作: function process_input(){
你好,我很难理解 P、NP 和多项式时间缩减的主题。我试过在网上搜索它并问过我的一些 friend ,但我没有得到任何好的答案。 我想问一个关于这个话题的一般性问题: 设 A,B 为 P 中的语言(或
你好,我一直在研究 https://leetcode.com/problems/2-keys-keyboard/并想到了这个动态规划问题。 您从空白页上的“A”开始,完成后得到一个数字 n,页面上应该
我正在使用 Cocoapods 和 KIF 在 Xcode 服务器上运行持续集成。我已经成功地为一个项目设置了它来报告每次提交。我现在正在使用第二个项目并收到错误: Bot Issue: warnin
我是一名优秀的程序员,十分优秀!