417. Pacific Atlantic Water Flow

huayeluoliuhen 发布于2019-08-14 17:25 / 1692人阅读

摘要：题目链接思路是分别找到和能够流到的地方，然后求两个地方的交集。找和能流到的地方，就是这个的遍历过程，可以用或者。复杂度没什么差，写起来简单点。

417. Pacific Atlantic Water Flow

题目链接：https://leetcode.com/problems...

思路是分别找到pacific和atlantic能够流到的地方，然后求两个地方的交集。找pacific和atlantic能流到的地方，就是这个matrix的遍历过程，可以用dfs或者bfs。复杂度没什么差，dfs写起来简单点。

public class Solution {
    public List pacificAtlantic(int[][] matrix) {
        List result = new ArrayList();
        if(matrix.length == 0 || matrix[0].length == 0) return result;
        
        m = matrix.length;
        n = matrix[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];
        // dfs, for each position
        for(int i = 0; i < m; i++) {
            dfs(matrix, i, 0, pacific);
            dfs(matrix, i, n- 1, atlantic);
        }
        for(int j = 0; j < n; j++) {
            dfs(matrix, 0, j, pacific);
            dfs(matrix, m - 1, j, atlantic);
        }
        // find the intersection
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(pacific[i][j] && atlantic[i][j]) result.add(new int[] {i, j});
            }
        }
        return result;
    }
    
    int m, n;
    int[][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
    private void dfs(int[][] matrix, int x, int y, boolean[][] visited) {
        if(visited[x][y]) return;
        visited[x][y] = true;
        for(int[] dir : dirs) {
            int nx = x + dir[0], ny = y + dir[1];
            if(nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[x][y] <= matrix[nx][ny]) {
                dfs(matrix, nx, ny, visited);
            }
        }
    }
}

云服务器 GPU云服务器 Atlantic Pacific water flow

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66623.html

leetcode417. Pacific Atlantic Water Flow

摘要：题目要求假设左上角的所有周围面积为太平洋，右下角的所有面积为大西洋。假定水只能从高出流向低处，要求找出所有既可以流向太平洋也可以流向大西洋的水域。但是反过来来看，任意一个可以到达大西洋的水流必然会抵达数组左边和上边的任意一点。题目要求 Given an m x n matrix of non-negative integers representing the height of e...

Lavender 2019-08-16 17:47 评论0 收藏0
容器最大盛水量

摘要：容器最大盛水量给定个非负整数，，，，其中每个表示坐标，处的点。找到两条线，它们与轴一起形成一个容器，使得容器含有最多的水。容器最大盛水量 Container With Most Water 给定n个非负整数a1，a2，...，an，其中每个表示坐标（i，ai）处的点。绘制n条垂直线，使得线i的两个端点在（i，ai）和（i，0）处。找到两条线，它们与x轴一起形成一个容器，使得容器...

luckyw 2019-07-25 12:04 评论0 收藏0
iKcamp｜基于Koa2搭建Node.js实战（含视频）☞ 解析JSON

视频地址：https://www.cctalk.com/v/15114923886141 showImg(https://segmentfault.com/img/remote/1460000012840997?w=1604&h=964); JSON 数据我颠倒了整个世界，只为摆正你的倒影。前面的文章中，我们已经完成了项目中常见的问题，比如路由请求、结构分层、视图渲染、静态资源等。那么，J...

mudiyouyou 2019-08-22 13:50 评论0 收藏0