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}};
👍 逆向思维 反向搜索 对于一个点它能流动两边的大洋,那么反过来,两边大洋的水反着流就能达到这个点。
- 找出所有从太平洋出发的水所能达到的点
canReachP - 找出所有从大西洋出发的水所能达到的点
canReachA - 重合的点即是要找的点
Code①( DFS + 方向数组 )
class Solution {
static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
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);
dfs(canReachA, i, n - 1);
}
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 ( 方向数组思想 ))
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);
dfs(heights, canReachA, i, n - 1);
}
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) {
if (canReach[i][j]) {
return;
}
canReach[i][j] = true;
if (i - 1 >= 0 && heights[i - 1][j] >= heights[i][j]) {
dfs(heights, canReach, i - 1, j);
}
if (i + 1 < heights.length && heights[i + 1][j] >= heights[i][j]) {
dfs(heights, canReach, i + 1, j);
}
if (j - 1 >= 0 && heights[i][j - 1] >= heights[i][j]) {
dfs(heights, canReach, i, j - 1);
}
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 + 方向数组 )
class Solution {
static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
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);
bfs(canReachA, i, n - 1);
}
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/
|