代码随想录算法训练Day58|LeetCode417-太平洋大西洋水流问题、LeetCode827-最大人工岛

🕗 发布于 2024-07-07 10:47 算法深度优先

太平洋大西洋水流问题

力扣417-太平洋大西洋水流问题

有一个 m × n 的矩形岛屿，与太平洋和大西洋相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r] [c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度小于或等于当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动既可流向太平洋也可流向大西洋。

示例 1：

输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

示例 2：

输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]

解题思路

DFS 通过递归或栈来实现，沿着一个路径尽可能深地搜索，直到到达最远的节点，然后回溯并探索其他路径。在这个问题中，从每个起始点开始，DFS 沿着四个方向探索，直到无法继续前进或达到边界。

class Solution {
    private final int[][] dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 保存四个方向

    // 从低向高遍历，注意这里 visited 是引用，即可以改变传入的 pacific 和 atlantic 的值
    private void dfs(int[][] heights, boolean[][] visited, int x, int y) {
        if (visited[x][y]) return;//如果当前坐标 (x, y) 已经被访问过，则直接返回，不再进行后续操作。
        visited[x][y] = true;//只要加入，立刻标记为访问过的节点
        for (int[] d : dir) { // 向四个方向遍历 8-17
            int nextx = x + d[0];
            int nexty = y + d[1];
            // 超过边界
            if (nextx < 0 || nextx >= heights.length || nexty < 0 || nexty >= heights[0].length) continue;
            // 高度不合适，注意这里是从低向高判断
            if (heights[x][y] > heights[nextx][nexty]) continue;

            dfs(heights, visited, nextx, nexty);
        }
    }

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> result = new ArrayList<>();
        int n = heights.length;
        int m = heights[0].length; // 这里不用担心空指针，题目要求说了长宽都大于1

        // 记录从太平洋边出发，可以遍历的节点
        boolean[][] pacific = new boolean[n][m];

        // 记录从大西洋出发，可以遍历的节点
        boolean[][] atlantic = new boolean[n][m];

        // 从最上最下行的节点出发，向高处遍历
        for (int i = 0; i < n; i++) {
            dfs(heights, pacific, i, 0); // 遍历最左列，接触太平洋 
            dfs(heights, atlantic, i, m - 1); // 遍历最右列，接触大西洋 
        }

        // 从最左最右列的节点出发，向高处遍历
        for (int j = 0; j < m; j++) {
            dfs(heights, pacific, 0, j); // 遍历最上行，接触太平洋
            dfs(heights, atlantic, n - 1, j); // 遍历最下行，接触大西洋
        }

        // 找到同时被太平洋和大西洋访问的节点
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (pacific[i][j] && atlantic[i][j]) result.add(List.of(i, j));
            }
        }
        return result;
    }
}

result.add(List.of(i, j)

List.of()
List.of方法允许我们创建一个不可变的List集合，其中包含指定的元素。
List immutableList = List.of(“apple”, “banana”, “orange”);

Map.of()
Map.of方法允许我们创建一个不可变的Map集合，其中包含指定的键值对。
Map<String, Integer> immutableMap = Map.of(“apple”, 1, “banana”, 2, “orange”, 3);

Set.of()
Set.of方法允许我们创建一个不可变的Set集合，其中包含指定的元素。
Set immutableSet = Set.of(“apple”, “banana”, “orange”);

最大人工岛

题目描述

力扣827-最大人工岛

给你一个大小为 n x n 二进制矩阵 grid 。最多只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿由一组上、下、左、右四个方向相连的 1 形成。

示例 1:

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

示例 2:

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。

示例 3:

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。

解题思路

其实每次深搜遍历计算最大岛屿面积，我们都做了很多重复的工作。

只要用一次深搜把每个岛屿的面积记录下来就好。

第一步：一次遍历地图，得出各个岛屿的面积，并做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积第二步：在遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出选一个0变成1 之后的最大面积。

拿如下地图的岛屿情况来举例：（1为陆地）

第一步，则遍历题目，并将岛屿到编号和面积上的统计，过程如图所示：

本过程代码如下：

    private int[][] dir = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; // 四个方向

    private void dfs(int[][] grid, boolean[][] visited, int x, int y, int mark) {
        if (visited[x][y] || grid[x][y] == 0) return; // 终止条件：访问过的节点 或者 遇到海水
        visited[x][y] = true; // 标记访问过
        grid[x][y] = mark; // 给陆地标记新标签
        count++;
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length) continue;  // 越界了，直接跳过
            dfs(grid, visited, nextx, nexty, mark);
        }
    }

    public int largestIsland(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        boolean[][] visited = new boolean[n][m]; // 标记访问过的点
        Map<Integer, Integer> gridNum = new HashMap<>();
        int mark = 2; // 记录每个岛屿的编号
        boolean isAllGrid = true; // 标记是否整个地图都是陆地
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) isAllGrid = false;
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 0;
                    dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 true
                    gridNum.put(mark, count); // 记录每一个岛屿的面积
                    mark++; // 记录下一个岛屿编号
                }
            }
        }
    }

这个过程时间复杂度 n * n 。可能有录友想：分明是两个for循环下面套这一个dfs，时间复杂度怎么回事 n * n呢？

其实大家可以仔细看一下代码，n * n这个方格地图中，每个节点我们就遍历一次，并不会重复遍历。

第二步过程如图所示：

也就是遍历每一个0的方格，并统计其相邻岛屿面积，最后取一个最大值。

这个过程的时间复杂度也为 n * n。

所以整个解法的时间复杂度，为 n * n + n * n 也就是 n^2。

当然这里还有一个优化的点，就是可以不用 visited数组，因为有mark来标记，所以遍历过的grid[i] [j]是不等于1的。

不过为了让各个变量各司其事，代码清晰一些，完整代码还是使用visited数组来标记。

最后，整体代码如下：

class Solution {
    private int count;
    private int[][] dir = { { 0, 1 }, { 1, 0 }, { -1, 0 }, { 0, -1 } }; // 四个方向

    private void dfs(int[][] grid, boolean[][] visited, int x, int y, int mark) {
        if (visited[x][y] || grid[x][y] == 0)
            return; // 终止条件：访问过的节点 或者 遇到海水
        visited[x][y] = true; // 标记访问过
        grid[x][y] = mark; // 给陆地标记新标签
        count++;
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= grid.length || nexty < 0 || nexty >= grid[0].length)
                continue; // 越界了，直接跳过
            dfs(grid, visited, nextx, nexty, mark);
        }
    }

    public int largestIsland(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        boolean[][] visited = new boolean[n][m]; // 标记访问过的点
        Map<Integer, Integer> gridNum = new HashMap<>();
        int mark = 2; // 记录每个岛屿的编号
        boolean isAllGrid = true; // 标记是否整个地图都是陆地
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0)
                    isAllGrid = false;
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 0;
                    dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 true
                    gridNum.put(mark, count); // 记录每一个岛屿的面积
                    mark++; // 记录下一个岛屿编号
                }
            }
        }
        if (isAllGrid)
            return n * m; // 如果都是陆地，返回全面积

        // 以下逻辑是根据添加陆地的位置，计算周边岛屿面积之和
        int result = 0; // 记录最后结果
        Set<Integer> visitedGrid = new HashSet<>(); // 标记访问过的岛屿
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int currentCount = 1; // 记录连接之后的岛屿数量
                visitedGrid.clear(); // 每次使用时，清空
                if (grid[i][j] == 0) {
                    for (int k = 0; k < 4; k++) {
                        int neari = i + dir[k][0]; // 计算相邻坐标
                        int nearj = j + dir[k][1];
                        if (neari < 0 || neari >= grid.length || nearj < 0 || nearj >= grid[0].length)
                            continue;
                        if (visitedGrid.contains(grid[neari][nearj]))
                            continue; // 添加过的岛屿不要重复添加
                        // 把相邻四面的岛屿数量加起来
                        if (grid[neari][nearj] > 1) {
                            currentCount += gridNum.get(grid[neari][nearj]);
                            visitedGrid.add(grid[neari][nearj]); // 标记该岛屿已经添加过
                        }
                    }
                }
                result = Math.max(result, currentCount);
            }
        }
        return result;
    }
}

原文地址：https://blog.csdn.net/m0_75002567/article/details/140235807

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：IPython 魔法重现：使用 %store -r 命令恢复变量全攻略
下一篇：[AIGC] ClickHouse的表引擎介绍

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

代码随想录算法训练Day58|LeetCode417-太平洋大西洋水流问题、LeetCode827-最大人工岛

太平洋大西洋水流问题

解题思路

最大人工岛

题目描述

解题思路

相关文章