专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
在近在网上看到一个视频，一HR在帮内地一家非常大的手机品牌在香港招聘的时候，要求年龄限制在35岁以下，引起该HR的痛批。至于是哪家手机品牌，视频中没有透露，我们也不要随便猜测。只是这个行为在内地已经司空见惯了，虽然批评的声音一直存在，但大家好像都已经习惯了。至于在香港应该还没有这方面的先例，有网友评论道：“过分了。内地大企业想把劣质招聘文化带到香港！必须拒绝！
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第417题：太平洋大西洋水流问题。
问题描述
来源：LeetCode第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]]
m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 10^5
问题分析
这题很绕，总结起来实际上就一句话： 哪些位置的水既能流到太平洋又能流到大西洋 。
直接计算比较麻烦，我们 先计算哪些位置的水可以流到太平洋，在计算哪些位置的水可以流到大西洋 ，最后在枚举所有的位置，判断哪些位置的水既能流到太平洋又能流到大西洋。
我们知道太平洋沿岸的水肯定是能流到太平洋的，水往低处流，这里我们 逆向思维 ，让水往高处流。从太平洋沿岸的位置开始遍历，如果下一个位置比当前位置高，说明下一个位置一定可以通过当前位置流到太平洋的，如下图所示。同理大西洋也一样。
JAVA：
public List
> pacificAtlantic( int[][] heights) { List > ans = new ArrayList<>(); int n = heights.length, m = heights[ 0].length; // 哪些位置可以到达太平洋 boolean[][] pacific = new boolean[n][m]; // 太平洋 // 哪些位置可以到达大西洋 boolean[][] atlantic = new boolean[n][m]; // 大西洋 Queue< int[]> pQueue = new LinkedList<>(); Queue< int[]> aQueue = new LinkedList<>(); // 四周边界 for ( int i = 0; i < n; i++) { pQueue.offer( new int[]{i, 0}); aQueue.offer( new int[]{i, m - 1}); pacific[i][ 0] = true; atlantic[i][m - 1] = true; } for ( int i = 0; i < m; i++) { pQueue.offer( new int[]{ 0, i}); aQueue.offer( new int[]{n - 1, i}); pacific[ 0][i] = true; atlantic[n - 1][i] = true; } bfs(heights, m, n, pQueue, pacific); // 先查找能够到达太平洋的坐标 bfs(heights, m, n, aQueue, atlantic); // 在查找能够达到大西洋的坐标 for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // 哪些位置既可以到达太平洋也可以达到大西洋 if (pacific[i][j] && atlantic[i][j]) ans.add(Arrays.asList(i, j)); } } return ans; } int[][] dir = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; private void bfs(int[][] heights, int m, int n, Queue
queue, boolean[][] visited) { while (!queue.isEmpty()) { int[] cur = queue.poll(); for ( int[] d : dir) { int x = cur[ 0] + d[ 0]; int y = cur[ 1] + d[ 1]; // 水如果从位置heights[x][y]流到位置[cur[0]][cur[1]]，那么 // heights[x][y]的高度必须要大于[cur[0]][cur[1]]。 if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y] || heights[x][y] < heights[cur[ 0]][cur[ 1]]) continue; visited[x][y] = true; // 标记可以到达 queue.offer( new int[]{x, y}); } } }
C++：
public: vector
> pacificAtlantic(vector
> &heights) { vector
> ans; int n = heights.size(), m = heights[0].size(); // 哪些位置可以到达太平洋 vector
> pacific(n, vector
(m, false)); // 哪些位置可以到达大西洋 vector
> atlantic(n, vector
(m, false)); queue int, int>> pQueue; queue int, int>> aQueue; // 四周边界 for ( int i = 0; i < n; i++) { pQueue.emplace(i, 0); aQueue.emplace(i, m - 1); pacific[i][ 0] = true; atlantic[i][m - 1] = true; } for ( int i = 0; i < m; i++) { pQueue.emplace( 0, i); aQueue.emplace(n - 1, i); pacific[ 0][i] = true; atlantic[n - 1][i] = true; } bfs(heights, m, n, pQueue, pacific); // 先查找能够到达太平洋的坐标 bfs(heights, m, n, aQueue, atlantic); // 在查找能够达到大西洋的坐标 for ( int i = 0; i < n; i++) { for ( int j = 0; j < m; j++) { // 哪些位置既可以到达太平洋也可以达到大西洋 if (pacific[i][j] && atlantic[i][j]) ans.push_back({i, j}); } } return ans; } int dir[ 4][ 2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; void bfs(vector
> &heights, int m, int n, queue int , int>> &q, vector
> &visited) { while (!q.empty()) { pair< int, int> cur = q.front(); q.pop(); for ( const auto d: dir) { int x = cur.first + d[ 0]; int y = cur.second + d[ 1]; // 水如果从位置heights[x][y]流到位置[cur[0]][cur[1]]，那么 // heights[x][y]的高度必须要大于[cur[0]][cur[1]]。 if (x < 0 || x >= n || y < 0 || y >= m || visited[x][y] || heights[x][y] < heights[cur.first][cur.second]) continue; visited[x][y] = true; // 标记可以到达 q.emplace(x, y); } } }
Python：
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: def bfs(q, visited): while q: cur = q.pop() for d in dirs: x = cur[0] + d[0] y = cur[1] + d[1] # 水如果从位置heights[x][y]流到位置[cur[0]][cur[1]]，那么heights[x][y] 的高度必须要大于[cur[0]][cur[1]]。 if x < 0 or x >= n or y < 0 or y >= m or visited[x][y] or heights[x][y] < heights[cur[0]][cur[1]]: continue visited[x][y] = True # 标记可以到达 q.append([x, y]) dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] ans = [] n, m = len(heights), len(heights[0]) # 哪些位置可以到达太平洋 pacific = [[False for _ in range(m)] for _ in range(n)] # 哪些位置可以到达大西洋 atlantic = [[False for _ in range(m)] for _ in range(n)] pQueue = [] aQueue = [] # 四周边界 for i in range(n): pQueue.append([i, 0]) aQueue.append([i, m - 1]) pacific[i][0] = True atlantic[i][m - 1] = True for i in range(m): pQueue.append([0, i]) aQueue.append([n - 1, i]) pacific[0][i] = True atlantic[n - 1][i] = True bfs(pQueue, pacific) # 先查找能够到达太平洋的坐标 bfs(aQueue, atlantic) # 在查找能够达到大西洋的坐标 for i in range(n): for j in range(m): # 哪些位置既可以到达太平洋也可以达到大西洋 if pacific[i][j] and atlantic[i][j]: ans.append([i, j]) return ans笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴