三刷 06/2022
看了答案还有DP解法，复杂度是一样的，感觉dp解法在这里并没有优势，因为可以向4个方向explore，没有单调有序性
Version #1 BFS
写了一个bug，就是在塞进queue之前visited或者类似于visited的数值一定要set，防止被后面的邻居重复加进queue里面
Time O(MN)
Space O(MN)
Runtime: 13 ms, faster than 75.52% of Java online submissions for 01 Matrix.
Memory Usage: 47.3 MB, less than 82.11% of Java online submissions for 01 Matrix.
class Solution {
private static int DEFAULT = Integer.MAX_VALUE;
private static int[] dx = new int[]{1, 0, -1, 0};
private static int[] dy = new int[]{0, -1, 0, 1};
public int[][] updateMatrix(int[][] mat) {
int rows = mat.length;
int cols = mat[0].length;
int[][] distances = new int[rows][cols];
Queue<int[]> que = new ArrayDeque<>();
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (mat[y][x] != 0) {
distances[y][x] = DEFAULT;
} else {
que.offer(new int[]{y, x});
}
}
}
int dist = 0;
while (!que.isEmpty()) {
int size = que.size();
dist++;
while (size-- > 0) {
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 || distances[ny][nx] != DEFAULT) {
continue;
}
distances[ny][nx] = dist;
que.offer(new int[]{ny, nx});
}
}
}
return distances;
}
}
Version BFS
一刷72.26 %
public class Solution {
private int[] dx = {1, 0, -1, 0};
private int[] dy = {0, 1, 0, -1};
public int[][] updateMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return matrix;
int rows = matrix.length;
int cols = matrix[0].length;
//Queue of indices
Queue<int[]> que = new LinkedList<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 0) {
que.add(new int[]{i, j});
} else {
matrix[i][j] = -1;
}
}
}
int dist = 1;
int[] curr;
int nx, ny;
while (!que.isEmpty()) {
int size = que.size();
//current level
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) {
//untouched
if (matrix[nx][ny] == -1) {
matrix[nx][ny] = dist;
que.add(new int[]{nx, ny});
}
}
}
}
dist++;
}
return matrix;
}
}
二刷
Runtime: 12 ms, faster than 78.09% of Java online submissions for 01 Matrix.
Memory Usage: 40.4 MB, less than 98.86% of Java online submissions for 01 Matrix.
class Solution {
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, 1, 0, -1};
public int[][] updateMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
Queue<int[]> que = new LinkedList<>();
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
if (matrix[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 && matrix[x][y] > 0) {
matrix[x][y] = -step;
que.offer(new int[]{x, y});
}
}
}
}
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
matrix[x][y] = Math.abs(matrix[x][y]);
}
}
return matrix;
}
}
No comments:
Post a Comment