写点什么

【LeetCode】最短的桥 Java 题解

作者:Albert
  • 2022-11-13
    北京
  • 本文字数:1939 字

    阅读完需:约 6 分钟

题目描述

给你一个大小为 n x n 的二元矩阵 grid ,其中 1 表示陆地,0 表示水域。


岛 是由四面相连的 1 形成的一个最大组,即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。


你可以将任意数量的 0 变为 1 ,以使两座岛连接起来,变成 一座岛 。


返回必须翻转的 0 的最小数目。


示例 1:
输入:grid = [[0,1],[1,0]]输出:1
示例 2:
输入:grid = [[0,1,0],[0,0,0],[0,0,1]]输出:2
示例 3:
输入:grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]输出:1
复制代码

思路分析

  • 今天的算法题目是数组类型题目。题目具体描述是岛屿问题,其中 1 表示岛屿,0 表示水。题目中指出,有 2 座岛屿,我们需要求解两个岛屿相连接的最小步数。

  • 解决岛屿问题,常见的方法有 DFS(深度优先遍历)和 BFS(广度优先遍历)。无论采用哪种方式,我们都需要避免一个节点访问多次,可以使用标记或者新建访问数组的方式,避免节点的重复访问。

  • 由于本题求解的是最少的步数,我们一般使用 BFS(广度优先遍历)。BFS 就是每次都尝试访问同一层的节点。 如果同一层都访问完了,再访问下一层。BFS 算法找到的路径是从起点开始的 最短 合法路径,也就可以求出最少的步数。

  • 在解题过程中,我们首先通过遍历的方式找到一个岛屿的节点,同时把这个位置标记为-1。接下来,采用 queue 实现队列,按照 dirs 方向向量,去寻找相应的岛屿节点。我们第一次的 BFS,就找到了第一个岛屿的所有节点。把岛屿节点放入 island。第二次 BFS,我们从岛屿节点开始,逐层遍历寻找下一个岛屿的节点,注意,这里采用先获取层所有的节点的长度,来保证每层的访问顺序。每到下一层,ans 增加一。找到之后,就是答案。

  • 具体实现代码如下,供参考。

通过代码

class Solution {    public int shortestBridge(int[][] grid) {        int n = grid.length;        int[][] dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};        List<int[]> island = new ArrayList<int[]>();        Queue<int[]> queue = new ArrayDeque<int[]>();
int ans = 0;
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { queue.offer(new int[]{i, j}); grid[i][j] = -1; while (!queue.isEmpty()) { int[] cell = queue.poll(); int x = cell[0], y = cell[1]; island.add(cell); for (int k = 0; k < 4; k++) { int nx = x + dirs[k][0]; int ny = y + dirs[k][1]; if (nx >= 0 && ny >= 0 && nx < n && ny < n && grid[nx][ny] == 1) { queue.offer(new int[]{nx, ny}); grid[nx][ny] = -1; } } } for (int[] cell : island) { queue.offer(cell); } while (!queue.isEmpty()) { int size = queue.size(); for (int k = 0; k < size; k++) { int[] cell = queue.poll(); int x = cell[0], y = cell[1]; for (int d = 0; d < 4; d++) { int nx = x + dirs[d][0]; int ny = y + dirs[d][1]; if (nx >= 0 && ny >= 0 && nx < n && ny < n) { if (grid[nx][ny] == 0) { queue.offer(new int[]{nx, ny}); grid[nx][ny] = -1; } else if (grid[nx][ny] == 1) { return ans; } } } } ans++; } } } } return ans; }}
复制代码

总结

  • 上述算法的时间复杂度是 O(n),空间复杂度是 O(n)

  • 解决岛屿问题,我们最常用的 BFS 解法一定要熟悉,理清具体的使用细节,才能更快的解决问题。

  • 坚持算法每日一题,加油!

发布于: 刚刚阅读数: 3
用户头像

Albert

关注

数据结构和算法爱好者 2019-09-29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】最短的桥Java题解_算法_Albert_InfoQ写作社区