【LeetCode】最短的桥 Java 题解
题目描述
给你一个大小为 n x n 的二元矩阵 grid ,其中 1 表示陆地,0 表示水域。
岛 是由四面相连的 1 形成的一个最大组,即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。
你可以将任意数量的 0 变为 1 ,以使两座岛连接起来,变成 一座岛 。
返回必须翻转的 0 的最小数目。
思路分析
今天的算法题目是数组类型题目。题目具体描述是岛屿问题,其中 1 表示岛屿,0 表示水。题目中指出,有 2 座岛屿,我们需要求解两个岛屿相连接的最小步数。
解决岛屿问题,常见的方法有 DFS(深度优先遍历)和 BFS(广度优先遍历)。无论采用哪种方式,我们都需要避免一个节点访问多次,可以使用标记或者新建访问数组的方式,避免节点的重复访问。
由于本题求解的是最少的步数,我们一般使用 BFS(广度优先遍历)。BFS 就是每次都尝试访问同一层的节点。 如果同一层都访问完了,再访问下一层。BFS 算法找到的路径是从起点开始的 最短 合法路径,也就可以求出最少的步数。
在解题过程中,我们首先通过遍历的方式找到一个岛屿的节点,同时把这个位置标记为-1。接下来,采用 queue 实现队列,按照 dirs 方向向量,去寻找相应的岛屿节点。我们第一次的 BFS,就找到了第一个岛屿的所有节点。把岛屿节点放入 island。第二次 BFS,我们从岛屿节点开始,逐层遍历寻找下一个岛屿的节点,注意,这里采用先获取层所有的节点的长度,来保证每层的访问顺序。每到下一层,ans 增加一。找到之后,就是答案。
具体实现代码如下,供参考。
通过代码
总结
上述算法的时间复杂度是 O(n),空间复杂度是 O(n)
解决岛屿问题,我们最常用的 BFS 解法一定要熟悉,理清具体的使用细节,才能更快的解决问题。
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【Albert】的原创文章。
原文链接:【http://xie.infoq.cn/article/41782c833c175ab039e3fe2aa】。文章转载请联系作者。
评论