Skip to content

Commit ae37c8c

Browse files
fishercoder1534fishercoder1534
committed
refactor 764
1 parent 9f87dfc commit ae37c8c

File tree

1 file changed

+73
-137
lines changed
  • src/main/java/com/fishercoder/solutions

1 file changed

+73
-137
lines changed

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

+73-137
Original file line numberDiff line numberDiff line change
@@ -3,147 +3,83 @@
33
import java.util.HashSet;
44
import java.util.Set;
55

6-
/**
7-
* 764. Largest Plus Sign
8-
*
9-
* In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1,
10-
* except those cells in the given list mines which are 0.
11-
* What is the largest axis-aligned plus sign of 1s contained in the grid? Return the order of the plus sign.
12-
* If there is none, return 0.
13-
*
14-
* An "axis-aligned plus sign of 1s of order k" has some center grid[x][y] = 1 along with 4 arms of length k-1 going up, down, left, and right, and made of 1s.
15-
* This is demonstrated in the diagrams below.
16-
* Note that there could be 0s or 1s beyond the arms of the plus sign,
17-
* only the relevant area of the plus sign is checked for 1s.
18-
19-
Examples of Axis-Aligned Plus Signs of Order k:
20-
21-
Order 1:
22-
000
23-
010
24-
000
25-
26-
Order 2:
27-
00000
28-
00100
29-
01110
30-
00100
31-
00000
32-
33-
Order 3:
34-
0000000
35-
0001000
36-
0001000
37-
0111110
38-
0001000
39-
0001000
40-
0000000
41-
42-
43-
Example 1:
44-
Input: N = 5, mines = [[4, 2]]
45-
Output: 2
46-
Explanation:
47-
11111
48-
11111
49-
11111
50-
11111
51-
11011
52-
In the above grid, the largest plus sign can only be order 2. One of them is marked in bold.
53-
54-
Example 2:
55-
Input: N = 2, mines = []
56-
Output: 1
57-
Explanation:
58-
There is no plus sign of order 2, but there is of order 1.
59-
60-
Example 3:
61-
Input: N = 1, mines = [[0, 0]]
62-
Output: 0
63-
Explanation:
64-
There is no plus sign, so return 0.
65-
66-
Note:
67-
N will be an integer in the range [1, 500].
68-
mines will have length at most 5000.
69-
mines[i] will be length 2 and consist of integers in the range [0, N-1].
70-
(Additionally, programs submitted in C, C++, or C# will be judged with a slightly smaller time limit.)
71-
72-
*/
73-
746
public class _764 {
75-
public static class Solution1 {
76-
/**Brute force
77-
*
78-
* Time: O(N^3)
79-
* Space: O(mines.length)*/
80-
public int orderOfLargestPlusSign(int N, int[][] mines) {
81-
Set<Integer> banned = new HashSet<>();
82-
for (int[] mine : mines) {
83-
banned.add(mine[0] * N + mine[1]);
84-
}
85-
int result = 0;
86-
for (int row = 0; row < N; row++) {
87-
for (int col = 0; col < N; col++) {
88-
int k = 0;
89-
while (k <= row && row < N - k && k <= col && col < N - k
90-
&& !banned.contains((row - k) * N + col)
91-
&& !banned.contains((row + k) * N + col)
92-
&& !banned.contains(row * N + col - k)
93-
&& !banned.contains(row * N + col + k)) {
94-
k++;
95-
}
96-
result = Math.max(result, k);
7+
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;
9734
}
98-
}
99-
return result;
10035
}
101-
}
102-
103-
public static class Solution2 {
104-
/**Dp
105-
*
106-
* Time: O(N^2)
107-
* Space: O(N^2)
108-
* Credit: https://leetcode.com/articles/largest-plus-sign/*/
109-
public int orderOfLargestPlusSign(int N, int[][] mines) {
110-
Set<Integer> banned = new HashSet<>();
111-
for (int[] mine : mines) {
112-
banned.add(mine[0] * N + mine[1]);
113-
}
114-
115-
int[][] dp = new int[N][N];
116-
117-
for (int row = 0; row < N; row++) {
118-
int count = 0;
119-
for (int col = 0; col < N; col++) {
120-
count = banned.contains(row * N + col) ? 0 : count + 1;
121-
dp[row][col] = count;
122-
}
123-
124-
count = 0;
125-
for (int col = N - 1; col >= 0; col--) {
126-
count = banned.contains(row * N + col) ? 0 : count + 1;
127-
dp[row][col] = Math.min(dp[row][col], count);
128-
}
129-
}
130-
131-
int result = 0;
132-
for (int col = 0; col < N; col++) {
133-
int count = 0;
134-
for (int row = 0; row < N; row++) {
135-
count = banned.contains(row * N + col) ? 0 : count + 1;
136-
dp[row][col] = Math.min(dp[row][col], count);
137-
}
13836

139-
count = 0;
140-
for (int row = N - 1; row >= 0; row--) {
141-
count = banned.contains(row * N + col) ? 0 : count + 1;
142-
dp[row][col] = Math.min(dp[row][col], count);
143-
result = Math.max(result, dp[row][col]);
37+
public static class Solution2 {
38+
/**
39+
* Dp
40+
* <p>
41+
* Time: O(N^2)
42+
* Space: O(N^2)
43+
* Credit: https://leetcode.com/articles/largest-plus-sign/
44+
*/
45+
public int orderOfLargestPlusSign(int N, int[][] mines) {
46+
Set<Integer> banned = new HashSet<>();
47+
for (int[] mine : mines) {
48+
banned.add(mine[0] * N + mine[1]);
49+
}
50+
51+
int[][] dp = new int[N][N];
52+
53+
for (int row = 0; row < N; row++) {
54+
int count = 0;
55+
for (int col = 0; col < N; col++) {
56+
count = banned.contains(row * N + col) ? 0 : count + 1;
57+
dp[row][col] = count;
58+
}
59+
60+
count = 0;
61+
for (int col = N - 1; col >= 0; col--) {
62+
count = banned.contains(row * N + col) ? 0 : count + 1;
63+
dp[row][col] = Math.min(dp[row][col], count);
64+
}
65+
}
66+
67+
int result = 0;
68+
for (int col = 0; col < N; col++) {
69+
int count = 0;
70+
for (int row = 0; row < N; row++) {
71+
count = banned.contains(row * N + col) ? 0 : count + 1;
72+
dp[row][col] = Math.min(dp[row][col], count);
73+
}
74+
75+
count = 0;
76+
for (int row = N - 1; row >= 0; row--) {
77+
count = banned.contains(row * N + col) ? 0 : count + 1;
78+
dp[row][col] = Math.min(dp[row][col], count);
79+
result = Math.max(result, dp[row][col]);
80+
}
81+
}
82+
return result;
14483
}
145-
}
146-
return result;
14784
}
148-
}
14985
}

0 commit comments

Comments
 (0)