[TODO] 用dfs再写一下
三刷 07/2022
Version #1 BFS
稍微优化了一下时间，instead of doing BFS two times and do a full scan of the two visited matrix, we add the position index to the result on the second BFS if it finds that the cell was visited by the first BFS
但是空间好像变多了
之前是两个boolean的2D array，一个boolean takes 1 bit
现在用一个char的2Darray，一个char takes 2 bytes
可以继续优化一下依然用两个booelan 2D arrays
Time O(MN)
Space O(MN)
Runtime: 16 ms, faster than 36.56% of Java online submissions for Pacific Atlantic Water Flow.
Memory Usage: 54.6 MB, less than 69.74% of Java online submissions for Pacific Atlantic Water Flow.
class Solution {
public List<List<Integer>> pacificAtlantic(int[][] heights) {
char[][] map = new char[heights.length][heights[0].length];
List<List<Integer>> result = new ArrayList<>();
flowBFS(heights, map, true, null);
flowBFS(heights, map, false, result);
return result;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private void addAtlantic(int y, int x, char[][] map, Queue<int[]> que, List<List<Integer>> result) {
if (map[y][x] == 'p') {
result.add(Arrays.asList(new Integer[]{y, x}));
}
map[y][x] = 'q';
que.offer(new int[]{y, x});
}
private void addPacific(int y, int x, char[][] map, Queue<int[]> que) {
map[y][x] = 'p';
que.offer(new int[]{y, x});
}
private void flowBFS(int[][] heights, char[][] map, boolean isPacific, List<List<Integer>> result) {
int rows = heights.length;
int cols = heights[0].length;
Queue<int[]> que = new ArrayDeque<>();
int y = 0, x = 0;
if (isPacific) {
for (y = 0; y < rows; y++) {
addPacific(y, x, map, que);
}
y = 0;
for (x = 0; x < cols; x++) {
addPacific(y, x, map, que);
}
} else {
x = heights[0].length - 1;
for (y = 0; y < rows; y++) {
addAtlantic(y, x, map, que, result);
}
y = heights.length - 1;
for (x = 0; x < cols; x++) {
addAtlantic(y, x, map, que, result);
}
}
while (!que.isEmpty()) {
int[] curr = que.poll();
for (int i = 0; i < 4; i++) {
int ny = curr[0] + dy[i];
int nx = curr[1] + dx[i];
if (ny < 0 || nx < 0 || ny >= rows || nx >= cols) {
continue;
}
char visited = isPacific ? 'p' : 'q';
if (heights[ny][nx] < heights[curr[0]][curr[1]] || map[ny][nx] == visited) {
continue;
}
if (isPacific) {
addPacific(ny, nx, map, que);
} else {
addAtlantic(ny, nx, map, que, result);
}
}
}
}
}
Version #1 BFS
一刷
pacific和atlantic两个boolean matrix忘记初始化了。。。别的没啥54.73 %
public class Solution {
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> result = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return result;
int rows = matrix.length;
int cols = matrix[0].length;
boolean[][] atlantic = new boolean[rows][cols];
boolean[][] pacific = new boolean[rows][cols];
Queue<int[]> pacificQue = new LinkedList<>();
Queue<int[]> atlanticQue = new LinkedList<>();
for (int i = 0; i < rows; i++) {
pacific[i][0] = true;
pacificQue.add(new int[]{i, 0});
atlantic[i][cols - 1] = true;
atlanticQue.add(new int[]{i, cols - 1});
}
for (int j = 0; j < cols; j++) {
pacific[0][j] = true;
pacificQue.add(new int[]{0, j});
atlantic[rows - 1][j] = true;
atlanticQue.add(new int[]{rows - 1, j});
}
bfs(pacificQue, pacific, matrix);
bfs(atlanticQue, atlantic, matrix);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.add(new int[]{i, j});
}
}
}
return result;
}
private int[] dx = {1, 0, -1, 0};
private int[] dy = {0, 1, 0, -1};
private void bfs(Queue<int[]> que, boolean[][] visited, int[][] matrix) {
int[] curr;
int nx, ny;
while(!que.isEmpty()) {
curr = que.poll();
//neighbors
for(int i = 0; i < 4; i++) {
nx = curr[0] + dx[i];
ny = curr[1] + dy[i];
//inbound
if (nx >= 0 && nx < matrix.length && ny >= 0 && ny < matrix[0].length && !visited[nx][ny]) {
if(matrix[nx][ny] >= matrix[curr[0]][curr[1]]) {
visited[nx][ny] = true;
que.add(new int[]{nx, ny});
}
}
}
}
}
}
二刷
一开始写的时候没有看到height equal也可以流，以为不需要visited matrix，只需要一个matrix记录visited count, 出了bug
如果water can flow to the point with same height,就需要记录visited，因为有potential cycle
Time O(mn)
Space O(mn)
很慢的样子，看了答案感觉没什么问题，感觉其他更快的解法是用的dfs
Runtime: 9 ms, faster than 32.51% of Java online submissions for Pacific Atlantic Water Flow.
Memory Usage: 40 MB, less than 90.71% of Java online submissions for Pacific Atlantic Water Flow.
class Solution {
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return new ArrayList<>();
}
Queue<int[]> pQue = new LinkedList<>();
Queue<int[]> aQue = new LinkedList<>();
boolean[][] pVisited = new boolean[matrix.length][matrix[0].length];
boolean[][] aVisited = new boolean[matrix.length][matrix[0].length];
for (int y = 0; y < matrix.length; y++) {
for (int x = 0; x < matrix[0].length; x++) {
if (y == 0 || x == 0) {
pQue.offer(new int[]{y, x});
pVisited[y][x] = true;
}
if (y == matrix.length - 1 || x == matrix[0].length - 1) {
aQue.offer(new int[]{y, x});
aVisited[y][x] = true;
}
}
}
bfs(matrix, pVisited, pQue);
bfs(matrix, aVisited, aQue);
List<List<Integer>> res = new ArrayList<>();
for (int y = 0; y < matrix.length; y++) {
for (int x = 0; x < matrix[0].length; x++) {
if (pVisited[y][x] && aVisited[y][x]) {
res.add(Arrays.asList(new Integer[]{y, x}));
}
}
}
return res;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, 1, 0, -1};
private void bfs(int[][] matrix, boolean[][] visited, Queue<int[]> que) {
while (!que.isEmpty()) {
int[] curr = que.poll();
for (int i = 0; i < 4; i++) {
int x = curr[1] + dx[i];
int y = curr[0] + dy[i];
// we only add points that's higher than current point
if (x >= 0 && x < matrix[0].length && y >= 0 && y < matrix.length && matrix[y][x] >= matrix[curr[0]][curr[1]] && !visited[y][x]) {
visited[y][x] = true;
que.offer(new int[]{y, x});
}
}
}
}
}
No comments:
Post a Comment