Skip to content

Commit 80de360

Browse files
fishercoder1534fishercoder1534
committed
refactor 764
1 parent 9d30967 commit 80de360

File tree

2 files changed

+100
-50
lines changed

2 files changed

+100
-50
lines changed

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

+77-30
Original file line numberDiff line numberDiff line change
@@ -5,36 +5,6 @@
55

66
public class _764 {
77
public static class Solution1 {
8-
/**
9-
* Brute force
10-
* <p>
11-
* Time: O(N^3)
12-
* Space: O(mines.length)
13-
*/
14-
public int orderOfLargestPlusSign(int N, int[][] mines) {
15-
Set<Integer> banned = new HashSet<>();
16-
for (int[] mine : mines) {
17-
banned.add(mine[0] * N + mine[1]);
18-
}
19-
int result = 0;
20-
for (int row = 0; row < N; row++) {
21-
for (int col = 0; col < N; col++) {
22-
int k = 0;
23-
while (k <= row && row < N - k && k <= col && col < N - k
24-
&& !banned.contains((row - k) * N + col)
25-
&& !banned.contains((row + k) * N + col)
26-
&& !banned.contains(row * N + col - k)
27-
&& !banned.contains(row * N + col + k)) {
28-
k++;
29-
}
30-
result = Math.max(result, k);
31-
}
32-
}
33-
return result;
34-
}
35-
}
36-
37-
public static class Solution2 {
388
/**
399
* Dp
4010
* <p>
@@ -82,4 +52,81 @@ public int orderOfLargestPlusSign(int N, int[][] mines) {
8252
return result;
8353
}
8454
}
55+
56+
public static class Solution2 {
57+
/**
58+
* credit: https://leetcode.com/problems/largest-plus-sign/discuss/113314/JavaC%2B%2BPython-O(N2)-solution-using-only-one-grid-matrix
59+
*/
60+
public int orderOfLargestPlusSign(int n, int[][] mines) {
61+
int[][] grid = new int[n][n];
62+
for (int i = 0; i < n; i++) {
63+
for (int j = 0; j < n; j++) {
64+
grid[i][j] = n;
65+
}
66+
}
67+
for (int i = 0; i < mines.length; i++) {
68+
grid[mines[i][0]][mines[i][1]] = 0;
69+
}
70+
for (int i = 0; i < n; i++) {
71+
for (int j = 0, k = n - 1, l = 0, r = 0, u = 0, d = 0; j < n; j++, k--) {
72+
grid[i][j] = Math.min(grid[i][j], l = (grid[i][j] == 0 ? 0 : l + 1));//left direction
73+
grid[i][k] = Math.min(grid[i][k], r = (grid[i][k] == 0 ? 0 : r + 1));//right direction
74+
grid[j][i] = Math.min(grid[j][i], u = (grid[j][i] == 0 ? 0 : u + 1));//upwards
75+
grid[k][i] = Math.min(grid[k][i], d = (grid[k][i] == 0 ? 0 : d + 1));//downwards
76+
}
77+
}
78+
int result = 0;
79+
for (int i = 0; i < n; i++) {
80+
for (int j = 0; j < n; j++) {
81+
result = Math.max(result, grid[i][j]);
82+
}
83+
}
84+
return result;
85+
}
86+
87+
/**
88+
* break the above into FOUR separate loops to go over four directions for easier understanding
89+
*/
90+
public int orderOfLargestPlusSign_initialVersion(int n, int[][] mines) {
91+
int[][] grid = new int[n][n];
92+
for (int i = 0; i < n; i++) {
93+
for (int j = 0; j < n; j++) {
94+
grid[i][j] = n;
95+
}
96+
}
97+
for (int i = 0; i < mines.length; i++) {
98+
grid[mines[i][0]][mines[i][1]] = 0;
99+
}
100+
for (int i = 0; i < n; i++) {
101+
for (int j = 0, l = 0; j < n; j++) {
102+
grid[i][j] = Math.min(grid[i][j], l = (grid[i][j] == 0 ? 0 : l + 1));
103+
}
104+
}
105+
106+
for (int i = 0; i < n; i++) {
107+
for (int j = 0, k = n - 1, r = 0; j < n; j++, k--) {
108+
grid[i][k] = Math.min(grid[i][k], r = (grid[i][k] == 0 ? 0 : r + 1));
109+
}
110+
}
111+
112+
for (int i = 0; i < n; i++) {
113+
for (int j = 0, k = n - 1, u = 0; j < n; j++, k--) {
114+
grid[j][i] = Math.min(grid[j][i], u = (grid[j][i] == 0 ? 0 : u + 1));
115+
}
116+
}
117+
118+
for (int i = 0; i < n; i++) {
119+
for (int j = 0, k = n - 1, d = 0; j < n; j++, k--) {
120+
grid[k][i] = Math.min(grid[k][i], d = (grid[k][i] == 0 ? 0 : d + 1));
121+
}
122+
}
123+
int result = 0;
124+
for (int i = 0; i < n; i++) {
125+
for (int j = 0; j < n; j++) {
126+
result = Math.max(result, grid[i][j]);
127+
}
128+
}
129+
return result;
130+
}
131+
}
85132
}

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

+23-20
Original file line numberDiff line numberDiff line change
@@ -7,27 +7,30 @@
77
import static org.junit.Assert.assertEquals;
88

99
public class _764Test {
10-
private static _764.Solution1 solution1;
11-
private static _764.Solution2 solution2;
12-
private static int[][] mines;
10+
private static _764.Solution1 solution1;
11+
private static _764.Solution2 solution2;
12+
private static int[][] mines;
1313

14-
@BeforeClass
15-
public static void setup() {
16-
solution1 = new _764.Solution1();
17-
solution2 = new _764.Solution2();
18-
}
14+
@BeforeClass
15+
public static void setup() {
16+
solution1 = new _764.Solution1();
17+
solution2 = new _764.Solution2();
18+
}
1919

20-
@Test
21-
public void test1() {
22-
mines = new int[][] {{0, 1}, {1, 0}, {1, 1}};
23-
assertEquals(1, solution1.orderOfLargestPlusSign(2, mines));
24-
assertEquals(1, solution2.orderOfLargestPlusSign(2, mines));
25-
}
20+
@Test
21+
public void test1() {
22+
mines = new int[][]{{0, 1}, {1, 0}, {1, 1}};
23+
assertEquals(1, solution1.orderOfLargestPlusSign(2, mines));
24+
assertEquals(1, solution2.orderOfLargestPlusSign(2, mines));
25+
assertEquals(1, solution2.orderOfLargestPlusSign_initialVersion(2, mines));
26+
}
27+
28+
@Test
29+
public void test2() {
30+
mines = new int[][]{{4, 2}};
31+
assertEquals(2, solution1.orderOfLargestPlusSign(5, mines));
32+
assertEquals(2, solution2.orderOfLargestPlusSign(5, mines));
33+
assertEquals(2, solution2.orderOfLargestPlusSign_initialVersion(5, mines));
34+
}
2635

27-
@Test
28-
public void test2() {
29-
mines = new int[][] {{4, 2}};
30-
assertEquals(2, solution1.orderOfLargestPlusSign(5, mines));
31-
assertEquals(2, solution2.orderOfLargestPlusSign(5, mines));
32-
}
3336
}

0 commit comments

Comments
 (0)