java数据结构与算法刷题-----LeetCode417. 太平洋大西洋水流问题

本文主要是介绍java数据结构与算法刷题-----LeetCode417. 太平洋大西洋水流问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

java数据结构与算法刷题目录（剑指Offer、LeetCode、ACM）-----主目录-----持续更新(进不去说明我没写完)：https://blog.csdn.net/grd_java/article/details/123063846

深度优先遍历

解题思路：时间复杂度O($m\ast n$)，空间复杂度O($$)

1. 从地图中找高点，然后推出是否能流入两个海洋显然不明智
2. 我们很清楚，两座海洋的水都是从相邻的岸边流入的。与其找当前地点的水流到哪，不如逆向思维。
3. 将题目变为，两座海洋的水从哪来?
4. 因此我们遍历陆地的上下左右边界，找到这水从哪流过来的。只要相邻地点比当前位置高，那么水就从高地点流过来的。
5. 我们可以创建两个数组，分别记录太平洋的水从哪来（标志为true），大西洋的水从哪里来（标志为true）
6. 最后两个数组同时为true的位置，就是既可以流向太平洋又可以流向大西洋的位置。

代码

class Solution {int[][] heights;int n,m;public List<List<Integer>> pacificAtlantic(int[][] heights) {this.heights = heights;this.n = heights.length;this.m = heights[0].length;ArrayList<List<Integer>> ans = new ArrayList<>();//保存最终答案boolean pacificOcean[][] = new boolean[n][m];//太平洋boolean atlanticOcean[][] = new boolean[n][m];//大西洋for(int j = 0;j<m;j++) dfs(0,j,pacificOcean);//上边界的太平洋进行广度优先for(int i = 0;i<n;i++) dfs(i,0,pacificOcean);//左边界的太平洋进行广度优先for(int j = 0;j<m;j++) dfs(n-1,j,atlanticOcean);//下边界的大西洋for(int i = 0;i<n;i++) dfs(i,m-1,atlanticOcean);//右边界的大西洋for(int i = 0;i<n;i++){//遍历整个数组for(int j = 0;j<m;j++){//如果太平洋和大西洋的水流都可以到达某个地点if(pacificOcean[i][j] && atlanticOcean[i][j]) {//这个地点就是一个答案，因为题目要求我们找到同时可以到达两个海洋的地点ArrayList<Integer> list = new ArrayList<Integer>();list.add(i);list.add(j);ans.add(list);}}}return ans;}//深度优先int [][] directions = new int[][]{{-1,0},{0,-1},{1,0},{0,1}};//上左下右方向public void dfs(int i,int j,boolean[][] ocean){ocean[i][j] = true;for(int[] direction : directions){int nextI = i+direction[0];int nextJ = j+direction[1];//如果下一个方向合理，并且没有访问过if(nextI < 0 || nextJ < 0 || nextI >= n || nextJ >= m || ocean[nextI][nextJ]) continue;//如果下一个地点比当前地点高，就说明当前水流可以从下一个地点流过来if(heights[i][j]<=heights[nextI][nextJ]) dfs(nextI,nextJ,ocean);}}
}

这篇关于java数据结构与算法刷题-----LeetCode417. 太平洋大西洋水流问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---