Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2e146cb

Browse files
add a solution for 130
1 parentda66b17 commit2e146cb

File tree

2 files changed

+137
-7
lines changed

2 files changed

+137
-7
lines changed

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

Lines changed: 88 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,10 @@
11
packagecom.fishercoder.solutions;
22

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

610
publicclass_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 problemeactually means: any grid that is 'O' but on
16+
* the problem means before coding. This problemactually 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 =newint[]{0,1,0, -1,0};
22+
int[]dirs =newint[]{0,1,0, -1,0};
1923

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

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

@@ -56,7 +60,7 @@ public void solve(char[][] board) {
5660
inty =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(newint[]{x,y});
63+
queue.offer(newint[]{x,y});
6064
}
6165
}
6266
}
@@ -73,4 +77,81 @@ public void solve(char[][] board) {
7377
}
7478
}
7579
}
80+
81+
publicstaticclassSolution2 {
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+
publicvoidsolve(char[][]board) {
89+
intm =board.length;
90+
intn =board[0].length;
91+
boolean[][]visited =newboolean[m][n];
92+
Map<Integer,List<int[]>>headMap =newHashMap<>();
93+
for (inti =0;i <m;i++) {
94+
for (intj =0;j <n;j++) {
95+
if (!visited[i][j] &&board[i][j] =='O') {
96+
booleancapturable =bfs(i,j,board,visited,headMap);
97+
if (capturable) {
98+
capture(headMap,board);
99+
}
100+
}
101+
}
102+
}
103+
}
104+
105+
privatevoidcapture(Map<Integer,List<int[]>>headMap,char[][]board) {
106+
intm =board.length;
107+
intn =board[0].length;
108+
for (inthead :headMap.keySet()) {
109+
List<int[]>list =headMap.get(head);
110+
for (int[]p :list) {
111+
board[p[0]][p[1]] ='X';
112+
}
113+
intx =head /m;
114+
inty =head %n;
115+
board[x][y] ='X';
116+
}
117+
}
118+
119+
privatebooleanbfs(intstartI,intstartJ,char[][]board,boolean[][]visited,Map<Integer,List<int[]>>headMap) {
120+
booleancapturable =true;
121+
Queue<int[]>queue =newLinkedList<>();
122+
intm =board.length;
123+
intn =board[0].length;
124+
queue.offer(newint[]{startI,startJ});
125+
inthead =startI *n +startJ;
126+
List<int[]>list =headMap.getOrDefault(head,newArrayList<>());
127+
list.add(newint[]{startI,startJ});
128+
int[]directions =newint[]{0,1,0, -1,0};
129+
while (!queue.isEmpty()) {
130+
intsize =queue.size();
131+
for (inti =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 (intj =0;j <directions.length -1;j++) {
138+
intnewx =directions[j] +curr[0];
139+
intnewy =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(newint[]{newx,newy});
142+
visited[newx][newy] =true;
143+
list.add(newint[]{newx,newy});
144+
}
145+
}
146+
}
147+
}
148+
if (!capturable) {
149+
headMap.remove(head);
150+
}else {
151+
headMap.put(head,list);
152+
}
153+
returncapturable;
154+
}
155+
156+
}
76157
}
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
packagecom.fishercoder;
2+
3+
importcom.fishercoder.common.utils.CommonUtils;
4+
importcom.fishercoder.solutions._130;
5+
importorg.junit.BeforeClass;
6+
importorg.junit.Test;
7+
8+
importstaticorg.junit.Assert.assertEquals;
9+
10+
publicclass_130Test {
11+
privatestatic_130.Solution1solution1;
12+
privatestatic_130.Solution2solution2;
13+
privatestaticchar[][]board;
14+
privatestaticchar[][]expected;
15+
16+
@BeforeClass
17+
publicstaticvoidsetup() {
18+
solution1 =new_130.Solution1();
19+
solution2 =new_130.Solution2();
20+
}
21+
22+
@Test
23+
publicvoidtest1() {
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+
publicvoidtest2() {
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)
[8]ページ先頭
©2009-2025 Movatter.jp