417. Pacific Atlantic Water Flow

huayeluoliuhen 發布于2019-08-14 17:25 / 1745人閱讀

摘要：題目鏈接思路是分別找到和能夠流到的地方，然后求兩個地方的交集。找和能流到的地方，就是這個的遍歷過程，可以用或者。復雜度沒什么差，寫起來簡單點。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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