Skip to content

Commit 2e146cb

Browse files
fishercoder1534fishercoder1534
committed
add a solution for 130
1 parent da66b17 commit 2e146cb

File tree

2 files changed

+137
-7
lines changed

2 files changed

+137
-7
lines changed

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

+88-7
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,10 @@
11
package com.fishercoder.solutions;
22

3+
import java.util.ArrayList;
4+
import java.util.HashMap;
35
import java.util.LinkedList;
6+
import java.util.List;
7+
import java.util.Map;
48
import java.util.Queue;
59

610
public class _130 {
@@ -9,13 +13,13 @@ public static class Solution1 {
913

1014
/**
1115
* I won't call this problem hard, it's just confusing, you'll definitely want to clarify what
12-
* the problem means before coding. This problem eactually means: any grid that is 'O' but on
16+
* the problem means before coding. This problem actually means: any grid that is 'O' but on
1317
* the four edges, will never be marked to 'X'; furthermore, any grid that is 'O' and that is
1418
* connected with the above type of 'O' will never be marked to 'X' as well; only all other
1519
* nodes that has any one direct neighbor that is an 'X' will be marked to 'X'.
1620
*/
1721

18-
int[] dirs = new int[] {0, 1, 0, -1, 0};
22+
int[] dirs = new int[]{0, 1, 0, -1, 0};
1923

2024
public void solve(char[][] board) {
2125
if (board == null || board.length == 0 || board[0].length == 0) {
@@ -29,23 +33,23 @@ public void solve(char[][] board) {
2933
for (int j = 0; j < n; j++) {
3034
if (board[0][j] == 'O') {
3135
board[0][j] = '+';
32-
queue.offer(new int[] {0, j});
36+
queue.offer(new int[]{0, j});
3337
}
3438
if (board[m - 1][j] == 'O') {
3539
board[m - 1][j] = '+';
36-
queue.offer(new int[] {m - 1, j});
40+
queue.offer(new int[]{m - 1, j});
3741
}
3842
}
3943

4044
//check first column and last column too
4145
for (int i = 0; i < m; i++) {
4246
if (board[i][0] == 'O') {
4347
board[i][0] = '+';
44-
queue.offer(new int[] {i, 0});
48+
queue.offer(new int[]{i, 0});
4549
}
4650
if (board[i][n - 1] == 'O') {
4751
board[i][n - 1] = '+';
48-
queue.offer(new int[] {i, n - 1});
52+
queue.offer(new int[]{i, n - 1});
4953
}
5054
}
5155

@@ -56,7 +60,7 @@ public void solve(char[][] board) {
5660
int y = curr[1] + dirs[i + 1];
5761
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
5862
board[x][y] = '+';
59-
queue.offer(new int[] {x, y});
63+
queue.offer(new int[]{x, y});
6064
}
6165
}
6266
}
@@ -73,4 +77,81 @@ public void solve(char[][] board) {
7377
}
7478
}
7579
}
80+
81+
public static class Solution2 {
82+
/**
83+
* My completely original solution on 11/1/2021, again, using a pen and paper to visualize my thought process and list out all key steps helps a lot!
84+
* 1. scan through this board;
85+
* 2. whenever we find an 'O', we'll do BFS to find all connected points and use the first 'O' as its head point for this entire connected region;
86+
* 3. whenever we visit a point, mark it as visited.
87+
*/
88+
public void solve(char[][] board) {
89+
int m = board.length;
90+
int n = board[0].length;
91+
boolean[][] visited = new boolean[m][n];
92+
Map<Integer, List<int[]>> headMap = new HashMap<>();
93+
for (int i = 0; i < m; i++) {
94+
for (int j = 0; j < n; j++) {
95+
if (!visited[i][j] && board[i][j] == 'O') {
96+
boolean capturable = bfs(i, j, board, visited, headMap);
97+
if (capturable) {
98+
capture(headMap, board);
99+
}
100+
}
101+
}
102+
}
103+
}
104+
105+
private void capture(Map<Integer, List<int[]>> headMap, char[][] board) {
106+
int m = board.length;
107+
int n = board[0].length;
108+
for (int head : headMap.keySet()) {
109+
List<int[]> list = headMap.get(head);
110+
for (int[] p : list) {
111+
board[p[0]][p[1]] = 'X';
112+
}
113+
int x = head / m;
114+
int y = head % n;
115+
board[x][y] = 'X';
116+
}
117+
}
118+
119+
private boolean bfs(int startI, int startJ, char[][] board, boolean[][] visited, Map<Integer, List<int[]>> headMap) {
120+
boolean capturable = true;
121+
Queue<int[]> queue = new LinkedList<>();
122+
int m = board.length;
123+
int n = board[0].length;
124+
queue.offer(new int[]{startI, startJ});
125+
int head = startI * n + startJ;
126+
List<int[]> list = headMap.getOrDefault(head, new ArrayList<>());
127+
list.add(new int[]{startI, startJ});
128+
int[] directions = new int[]{0, 1, 0, -1, 0};
129+
while (!queue.isEmpty()) {
130+
int size = queue.size();
131+
for (int i = 0; i < size; i++) {
132+
int[] curr = queue.poll();
133+
if (curr[0] == 0 || curr[0] == m - 1 || curr[1] == 0 || curr[1] == n - 1) {
134+
capturable = false;
135+
}
136+
visited[curr[0]][curr[1]] = true;
137+
for (int j = 0; j < directions.length - 1; j++) {
138+
int newx = directions[j] + curr[0];
139+
int newy = directions[j + 1] + curr[1];
140+
if (newx >= 0 && newx < m && newy >= 0 && newy < n && !visited[newx][newy] && board[newx][newy] == 'O') {
141+
queue.offer(new int[]{newx, newy});
142+
visited[newx][newy] = true;
143+
list.add(new int[]{newx, newy});
144+
}
145+
}
146+
}
147+
}
148+
if (!capturable) {
149+
headMap.remove(head);
150+
} else {
151+
headMap.put(head, list);
152+
}
153+
return capturable;
154+
}
155+
156+
}
76157
}

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

+49
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.utils.CommonUtils;
4+
import com.fishercoder.solutions._130;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import static org.junit.Assert.assertEquals;
9+
10+
public class _130Test {
11+
private static _130.Solution1 solution1;
12+
private static _130.Solution2 solution2;
13+
private static char[][] board;
14+
private static char[][] expected;
15+
16+
@BeforeClass
17+
public static void setup() {
18+
solution1 = new _130.Solution1();
19+
solution2 = new _130.Solution2();
20+
}
21+
22+
@Test
23+
public void test1() {
24+
board = CommonUtils.convertLeetCodeRegular2DCharArrayInputIntoJavaArray("[\"X\",\"O\",\"X\",\"O\",\"X\",\"O\",\"O\",\"O\",\"X\",\"O\"],[\"X\",\"O\",\"O\",\"X\",\"X\",\"X\",\"O\",\"O\",\"O\",\"X\"],[\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"X\",\"X\"],[\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"X\",\"O\",\"O\",\"X\"]," +
25+
"[\"O\",\"O\",\"X\",\"X\",\"O\",\"X\",\"X\",\"O\",\"O\",\"O\"],[\"X\",\"O\",\"O\",\"X\",\"X\",\"X\",\"O\",\"X\",\"X\",\"O\"],[\"X\",\"O\",\"X\",\"O\",\"O\",\"X\",\"X\",\"O\",\"X\",\"O\"],[\"X\",\"X\",\"O\",\"X\",\"X\",\"O\",\"X\",\"O\",\"O\",\"X\"],[\"O\",\"O\",\"O\",\"O\",\"X\",\"O\",\"X\",\"O\",\"X\",\"O\"]," +
26+
"[\"X\",\"X\",\"O\",\"X\",\"X\",\"X\",\"X\",\"O\",\"O\",\"O\"]");
27+
expected = CommonUtils.convertLeetCodeRegular2DCharArrayInputIntoJavaArray("[\"X\",\"O\",\"X\",\"O\",\"X\",\"O\",\"O\",\"O\",\"X\",\"O\"],[\"X\",\"O\",\"O\",\"X\",\"X\",\"X\",\"O\",\"O\",\"O\",\"X\"],[\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"X\",\"X\"],[\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"X\",\"O\",\"O\",\"X\"]," +
28+
"[\"O\",\"O\",\"X\",\"X\",\"O\",\"X\",\"X\",\"O\",\"O\",\"O\"],[\"X\",\"O\",\"O\",\"X\",\"X\",\"X\",\"X\",\"X\",\"X\",\"O\"],[\"X\",\"O\",\"X\",\"X\",\"X\",\"X\",\"X\",\"O\",\"X\",\"O\"],[\"X\",\"X\",\"O\",\"X\",\"X\",\"X\",\"X\",\"O\",\"O\",\"X\"],[\"O\",\"O\",\"O\",\"O\",\"X\",\"X\",\"X\",\"O\",\"X\",\"O\"]," +
29+
"[\"X\",\"X\",\"O\",\"X\",\"X\",\"X\",\"X\",\"O\",\"O\",\"O\"]");
30+
solution1.solve(board);
31+
assertEquals(expected, board);
32+
}
33+
34+
@Test
35+
public void test2() {
36+
board = CommonUtils.convertLeetCodeRegular2DCharArrayInputIntoJavaArray("[\"X\",\"O\",\"X\",\"O\",\"X\",\"O\",\"O\",\"O\",\"X\",\"O\"],[\"X\",\"O\",\"O\",\"X\",\"X\",\"X\",\"O\",\"O\",\"O\",\"X\"],[\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"X\",\"X\"],[\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"X\",\"O\",\"O\",\"X\"]," +
37+
"[\"O\",\"O\",\"X\",\"X\",\"O\",\"X\",\"X\",\"O\",\"O\",\"O\"],[\"X\",\"O\",\"O\",\"X\",\"X\",\"X\",\"O\",\"X\",\"X\",\"O\"],[\"X\",\"O\",\"X\",\"O\",\"O\",\"X\",\"X\",\"O\",\"X\",\"O\"],[\"X\",\"X\",\"O\",\"X\",\"X\",\"O\",\"X\",\"O\",\"O\",\"X\"],[\"O\",\"O\",\"O\",\"O\",\"X\",\"O\",\"X\",\"O\",\"X\",\"O\"]," +
38+
"[\"X\",\"X\",\"O\",\"X\",\"X\",\"X\",\"X\",\"O\",\"O\",\"O\"]");
39+
expected = CommonUtils.convertLeetCodeRegular2DCharArrayInputIntoJavaArray("[\"X\",\"O\",\"X\",\"O\",\"X\",\"O\",\"O\",\"O\",\"X\",\"O\"],[\"X\",\"O\",\"O\",\"X\",\"X\",\"X\",\"O\",\"O\",\"O\",\"X\"],[\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"X\",\"X\"],[\"O\",\"O\",\"O\",\"O\",\"O\",\"O\",\"X\",\"O\",\"O\",\"X\"]," +
40+
"[\"O\",\"O\",\"X\",\"X\",\"O\",\"X\",\"X\",\"O\",\"O\",\"O\"],[\"X\",\"O\",\"O\",\"X\",\"X\",\"X\",\"X\",\"X\",\"X\",\"O\"],[\"X\",\"O\",\"X\",\"X\",\"X\",\"X\",\"X\",\"O\",\"X\",\"O\"],[\"X\",\"X\",\"O\",\"X\",\"X\",\"X\",\"X\",\"O\",\"O\",\"X\"],[\"O\",\"O\",\"O\",\"O\",\"X\",\"X\",\"X\",\"O\",\"X\",\"O\"]," +
41+
"[\"X\",\"X\",\"O\",\"X\",\"X\",\"X\",\"X\",\"O\",\"O\",\"O\"]");
42+
CommonUtils.print2DCharArray(board);
43+
solution2.solve(board);
44+
CommonUtils.print2DCharArray(board);
45+
CommonUtils.print2DCharArray(expected);
46+
assertEquals(expected, board);
47+
}
48+
49+
}

0 commit comments

Comments
 (0)