Skip to content

Commit de52e0c

Browse files
fishercoder1534fishercoder1534
committed
add a solution for 542
1 parent 829f5a5 commit de52e0c

File tree

2 files changed

+106
-17
lines changed

2 files changed

+106
-17
lines changed

‎src/main/java/com/fishercoder/solutions/_542.java

+70-17
Original file line numberDiff line numberDiff line change
@@ -3,40 +3,93 @@
33
import java.util.Deque;
44
import java.util.LinkedList;
55
import java.util.List;
6+
import java.util.Queue;
67

78
public class _542 {
89

910
public static class Solution1 {
10-
11-
public List<List<Integer>> updateMatrix(List<List<Integer>> matrix) {
12-
int m = matrix.size();
13-
int n = matrix.get(0).size();
11+
public int[][] updateMatrix(int[][] mat) {
12+
int m = mat.length;
13+
int n = mat[0].length;
14+
int[][] ans = new int[m][n];
1415
Deque<int[]> deque = new LinkedList<>();
1516
for (int i = 0; i < m; i++) {
1617
for (int j = 0; j < n; j++) {
17-
if (matrix.get(i).get(j) == 0) {
18+
if (mat[i][j] == 0) {
1819
deque.offer(new int[]{i, j});
1920
} else {
20-
matrix.get(i).set(j, Integer.MAX_VALUE);
21+
ans[i][j] = m * n;
2122
}
2223
}
2324
}
24-
25-
final int[] dirs = new int[]{0, 1, 0, -1, 0};
25+
int[] directions = new int[]{0, 1, 0, -1, 0};
2626
while (!deque.isEmpty()) {
27-
int[] currentCell = deque.poll();
28-
for (int i = 0; i < dirs.length - 1; i++) {
29-
int nextRow = currentCell[0] + dirs[i];
30-
int nextCol = currentCell[1] + dirs[i + 1];
31-
if (nextRow < 0 || nextCol < 0 || nextRow >= m || nextCol >= n || matrix.get(nextRow).get(nextCol) <= matrix.get(currentCell[0]).get(currentCell[1]) + 1) {
32-
continue;
27+
int[] curr = deque.poll();
28+
for (int i = 0; i < directions.length - 1; i++) {
29+
int nextX = directions[i] + curr[0];
30+
int nextY = directions[i + 1] + curr[1];
31+
if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n && ans[nextX][nextY] > ans[curr[0]][curr[1]] + 1) {
32+
deque.offer(new int[]{nextX, nextY});
33+
ans[nextX][nextY] = ans[curr[0]][curr[1]] + 1;
3334
}
34-
deque.offer(new int[]{nextRow, nextCol});
35-
matrix.get(nextRow).set(nextCol, matrix.get(currentCell[0]).get(currentCell[1]) + 1);
3635
}
3736
}
38-
return matrix;
37+
return ans;
3938
}
4039
}
4140

41+
public static class Solution2 {
42+
/**
43+
* A silly, but working solution. Apparently, the above BFS approach is a smarter version of this one.
44+
*/
45+
public int[][] updateMatrix(int[][] mat) {
46+
int m = mat.length;
47+
int n = mat[0].length;
48+
int[][] ans = new int[m][n];
49+
Queue<int[]> queue = new LinkedList<>();
50+
for (int i = 0; i < m; i++) {
51+
for (int j = 0; j < n; j++) {
52+
if (mat[i][j] == 0) {
53+
queue.offer(new int[]{i, j});
54+
} else {
55+
ans[i][j] = m * n;
56+
}
57+
}
58+
}
59+
while (!queue.isEmpty()) {
60+
int[] curr = queue.poll();
61+
for (int i = curr[0] + 1, j = curr[1]; i < m && mat[i][j] != 0; i++) {
62+
ans[i][j] = Math.min(ans[i][j], i - curr[0]);
63+
}
64+
for (int i = curr[0] - 1, j = curr[1]; i >= 0 && mat[i][j] != 0; i--) {
65+
ans[i][j] = Math.min(ans[i][j], curr[0] - i);
66+
}
67+
for (int j = curr[1] + 1, i = curr[0]; j < n && mat[i][j] != 0; j++) {
68+
ans[i][j] = Math.min(ans[i][j], j - curr[1]);
69+
}
70+
for (int j = curr[1] - 1, i = curr[0]; j >= 0 && mat[i][j] != 0; j--) {
71+
ans[i][j] = Math.min(ans[i][j], curr[1] - j);
72+
}
73+
}
74+
for (int i = 0; i < m; i++) {
75+
for (int j = 0; j < n; j++) {
76+
if (i + 1 < m && ans[i + 1][j] >= 1) {
77+
ans[i][j] = Math.min(ans[i][j], ans[i + 1][j] + 1);
78+
}
79+
if (i - 1 >= 0 && ans[i - 1][j] >= 1) {
80+
ans[i][j] = Math.min(ans[i][j], ans[i - 1][j] + 1);
81+
}
82+
if (j + 1 < n && ans[i][j + 1] >= 1) {
83+
ans[i][j] = Math.min(ans[i][j], ans[i][j + 1] + 1);
84+
}
85+
if (j - 1 >= 0 && ans[i][j - 1] >= 1) {
86+
ans[i][j] = Math.min(ans[i][j], ans[i][j - 1] + 1);
87+
}
88+
}
89+
}
90+
return ans;
91+
}
92+
93+
}
94+
4295
}

‎src/test/java/com/fishercoder/_542Test.java

+36
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.utils.CommonUtils;
4+
import com.fishercoder.solutions._542;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import static org.junit.Assert.assertEquals;
9+
10+
public class _542Test {
11+
private static _542.Solution1 solution1;
12+
private static _542.Solution2 solution2;
13+
14+
@BeforeClass
15+
public static void setup() {
16+
solution1 = new _542.Solution1();
17+
solution2 = new _542.Solution2();
18+
}
19+
20+
@Test
21+
public void test1() {
22+
int[][] matrix = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[1,1,0,1,1,1,1,1,1,1],[1,1,0,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,1,1,0],[1,1,1,1,1,1,0,0,1,0],[1,0,0,1,1,1,0,1,0,1],[0,0,1,0,0,1,1,0,0,1],[0,1,0,1,1,1,1,1,1,1],[1,0,0,1,1,0,0,0,0,0],[0,0,1,1,1,1,0,1,1,1],[1,1,0,0,1,0,1,0,1,1]");
23+
int[][] expected = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[2,1,0,1,2,2,2,3,3,2],[2,1,0,1,1,1,1,2,2,1],[3,2,1,1,0,0,0,1,1,0],[2,1,1,2,1,1,0,0,1,0],[1,0,0,1,1,1,0,1,0,1],[0,0,1,0,0,1,1,0,0,1],[0,1,0,1,1,1,1,1,1,1],[1,0,0,1,1,0,0,0,0,0],[0,0,1,1,2,1,0,1,1,1],[1,1,0,0,1,0,1,0,1,2]");
24+
assertEquals(expected, solution1.updateMatrix(matrix));
25+
assertEquals(expected, solution2.updateMatrix(matrix));
26+
}
27+
28+
@Test
29+
public void test2() {
30+
int[][] matrix = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,0,0],[0,1,0],[0,0,0]");
31+
int[][] expected = CommonUtils.convertLeetCodeIrregularLengths2DArrayInputIntoJavaArray("[0,0,0],[0,1,0],[0,0,0]");
32+
assertEquals(expected, solution1.updateMatrix(matrix));
33+
assertEquals(expected, solution2.updateMatrix(matrix));
34+
}
35+
36+
}

0 commit comments

Comments
 (0)