IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 417. 太平洋大西洋水流问题(DFS + BFS + 方向数组) -> 正文阅读

[数据结构与算法]417. 太平洋大西洋水流问题(DFS + BFS + 方向数组)

Question

417. 太平洋大西洋水流问题

在这里插入图片描述

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/random-pick-index/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

Ideas

1、Answer( Java )

解法思路:DFS + 方向数组

?? 方向数组 dirs

//对应上下左右四个方向
static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

👍 逆向思维 反向搜索 对于一个点它能流动两边的大洋,那么反过来,两边大洋的水反着流就能达到这个点。

  1. 找出所有从太平洋出发的水所能达到的点 canReachP
  2. 找出所有从大西洋出发的水所能达到的点 canReachA
  3. 重合的点即是要找的点

Code①( DFS + 方向数组 )

/**
 * @author Listen 1024
 * @description 417. 太平洋大西洋水流问题(DFS +  BFS + 方向数组)
 * @date 2022-04-27 8:18
 */
class Solution {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//the direction array
    int m, n;
    int[][] heights;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        m = heights.length;
        n = heights[0].length;
        this.heights = heights;
        boolean[][] canReachP = new boolean[m][n], canReachA = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(canReachP, i, 0);//begin with left boundary
            dfs(canReachA, i, n - 1);//begin with right boundary

        }
        for (int i = 0; i < n; i++) {
            dfs(canReachA, m - 1, i);
            dfs(canReachP, 0, i);

        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (canReachA[i][j] && canReachP[i][j]) {
                    res.add(Arrays.asList(i, j));
                }
            }

        }
        return res;
    }

    private void dfs(boolean[][] canReach, int row, int col) {
        if (canReach[row][col]) {
            return;
        }
        canReach[row][col] = true;
        for (int[] dir : dirs) {
            int newRow = row + dir[0], newCol = col + dir[1];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col]) {
                dfs(canReach, newRow, newCol);
            }
        }
    }
}

Code②( DFS ( 方向数组思想 ))

/**
 * @author Listen 1024
 * @description 417. 太平洋大西洋水流问题(DFS +  BFS + 方向数组)
 * @date 2022-04-27 8:18
 */
class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        int m = heights.length, n = heights[0].length;
        boolean[][] canReachP = new boolean[m][n], canReachA = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            dfs(heights, canReachP, i, 0);//begin with left boundary
            dfs(heights, canReachA, i, n - 1);//begin with right boundary

        }
        for (int i = 0; i < n; i++) {
            dfs(heights, canReachA, m - 1, i);
            dfs(heights, canReachP, 0, i);

        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (canReachA[i][j] && canReachP[i][j]) {
                    res.add(Arrays.asList(i, j));
                }
            }

        }
        return res;
    }

    private void dfs(int[][] heights, boolean[][] canReach, int i, int j) {
        //return when the zone was reached
        if (canReach[i][j]) {
            return;
        }
        //set the current zone true
        canReach[i][j] = true;
        //Up
        if (i - 1 >= 0 && heights[i - 1][j] >= heights[i][j]) {
            dfs(heights, canReach, i - 1, j);
        }
        //Down
        if (i + 1 < heights.length && heights[i + 1][j] >= heights[i][j]) {
            dfs(heights, canReach, i + 1, j);
        }
        //Left
        if (j - 1 >= 0 && heights[i][j - 1] >= heights[i][j]) {
            dfs(heights, canReach, i, j - 1);
        }
        //Right
        if (j + 1 < heights[0].length && heights[i][j + 1] >= heights[i][j]) {
            dfs(heights, canReach, i, j + 1);
        }
    }
}

2、Answer( Java )

解法思路:BFS + 方向数组

Code(BFS + 方向数组 )

/**
 * @author Listen 1024
 * @description 417. 太平洋大西洋水流问题(DFS +  BFS + 方向数组)
 * @date 2022-04-27 8:18
 */
 class Solution {
    static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//the direction array
    int m, n;
    int[][] heights;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        m = heights.length;
        n = heights[0].length;
        this.heights = heights;
        boolean[][] canReachP = new boolean[m][n], canReachA = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            bfs(canReachP, i, 0);//begin with left boundary
            bfs(canReachA, i, n - 1);//begin with right boundary

        }
        for (int i = 0; i < n; i++) {
            bfs(canReachA, m - 1, i);
            bfs(canReachP, 0, i);

        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (canReachA[i][j] && canReachP[i][j]) {
                    res.add(Arrays.asList(i, j));
                }
            }

        }
        return res;
    }

    private void bfs(boolean[][] canReach, int row, int col) {
        if (canReach[row][col]) {
            return;
        }
        canReach[row][col] = true;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{row, col});
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] dir : dirs) {
                int newRow = cell[0] + dir[0], newCol = cell[1] + dir[1];
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[cell[0]][cell[1]] && !canReach[newRow][newCol]) {
                    canReach[newRow][newCol] = true;
                    queue.offer(new int[]{newRow, newCol});
                }
            }

        }

    }
}
//题解参考链接(如侵删)
https://leetcode.cn/problems/pacific-atlantic-water-flow/solution/tai-ping-yang-da-xi-yang-shui-liu-wen-ti-sjk3/
https://leetcode.cn/problems/pacific-atlantic-water-flow/solution/shui-wang-gao-chu-liu-by-xiaohu9527-xxsx/
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-04-28 12:04:59  更:2022-04-28 12:05:23 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 6:29:52-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码