四刷 07/2022
Version #1 Multi Start BFS
优化了一下之前的写法，因为每次的next position都是curr position的distance + 1，所以其实不需要level order traversal
只需要一般的BFS就可以了
Time O(MN)
Space O(MN)
Runtime: 13 ms, faster than 51.91% of Java online submissions for Walls and Gates.
Memory Usage: 58.2 MB, less than 17.48% of Java online submissions for Walls and Gates.
class Solution {
private static int WALL = -1;
private static int GATE = 0;
private static int EMPTY = Integer.MAX_VALUE;
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
public void wallsAndGates(int[][] rooms) {
Queue<int[]> que = new ArrayDeque<>();
int rows = rooms.length, cols = rooms[0].length;
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (rooms[y][x] == GATE) {
que.offer(new int[]{y, x});
}
}
}
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 || rooms[ny][nx] != EMPTY) {
continue;
}
rooms[ny][nx] = rooms[curr[0]][curr[1]] + 1;
que.offer(new int[]{ny, nx});
}
}
}
}
Multi End BFS
class Solution {
private int[] dx = {1, 0, -1, 0};
private int[] dy = {0, -1, 0, 1};
public void wallsAndGates(int[][] rooms) {
if (rooms == null || rooms.length == 0 || rooms[0] == null || rooms[0].length == 0) return;
Queue<int[]> que = new LinkedList<>();
for (int i = 0; i < rooms.length; i++) {
for (int j = 0; j < rooms[0].length; j++) {
if (rooms[i][j] == 0) {
que.offer(new int[]{i, j});
}
}
}
int level = 0;
int[] curr = null;
int width = rooms.length;
int length = rooms[0].length;
while (!que.isEmpty()) {
level++;
int size = que.size();
while (size-- > 0) {
curr = que.poll();
for (int i = 0; i < 4; i++) {
int x = curr[0] + dx[i];
int y = curr[1] + dy[i];
if (x >= 0 && x < width && y >= 0 && y < length) {
if (rooms[x][y] == Integer.MAX_VALUE) {
rooms[x][y] = level;
que.offer(new int[]{x, y});
}
}
}
}
}
}
}
一刷
都在注释里了
Method里面的field不能加access modifier
62.70 %
public class Solution {
private int[] dx = {1, 0, -1, 0};
private int[] dy = {0, 1, 0, -1};
private final int WALL = -1;
private final int GATE = 0;
private final int EMPTY = Integer.MAX_VALUE;
public void wallsAndGates(int[][] rooms) {
if (rooms == null || rooms.length == 0 || rooms[0] == null || rooms[0].length == 0) return;
//start walking from all gate and keep track of distance
//Once we reach a EMPTY room, set its value to the distance from the gates
int rows = rooms.length;
int cols = rooms[0].length;
Queue<int[]> que = new LinkedList<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
//Add all gates to the queue
if (rooms[i][j] == GATE) {
que.add(new int[]{i, j});
}
}
}
int dist = 1;
int[] curr;
//neighbor's position
int nx, ny;
while (!que.isEmpty()) {
int size = que.size();
while (size-- > 0) {
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 < rows && ny >= 0 && ny < cols) {
if (rooms[nx][ny] == EMPTY) {
rooms[nx][ny] = dist;
que.add(new int[]{nx, ny});
}
}
}
}
//distance increaced by 1 for the next layer
dist++;
}
return;
}
}
三刷
Runtime: 5 ms, faster than 90.21% of Java online submissions for Walls and Gates.
Memory Usage: 42.4 MB, less than 80.57% of Java online submissions for Walls and Gates.
class Solution {
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, 1, 0, -1};
public void wallsAndGates(int[][] rooms) {
int m = rooms.length;
int n = rooms[0].length;
Queue<int[]> que = new LinkedList<>();
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
if (rooms[x][y] == 0) {
que.offer(new int[]{x, y});
}
}
}
int step = 0;
while (!que.isEmpty()) {
step++;
int size = que.size();
while (size-- > 0) {
int[] curr = que.poll();
for (int i = 0; i < 4; i++) {
int x = dx[i] + curr[0];
int y = dy[i] + curr[1];
if (x >= 0 && x < m && y >= 0 && y < n && rooms[x][y] == Integer.MAX_VALUE) {
rooms[x][y] = step;
que.offer(new int[]{x, y});
}
}
}
}
}
}
No comments:
Post a Comment