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

Commit17f4f58

Browse files
refactor 419
1 parent4556542 commit17f4f58

File tree

1 file changed

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

1 file changed

+73
-70
lines changed
Lines changed: 73 additions & 70 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,17 @@
11
packagecom.fishercoder.solutions;
22

3-
/**Given an 2D board, count how many battleships are in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may assume the following rules:
3+
/**
4+
* 419. Battleships in a Board
5+
*
6+
* Given an 2D board, count how many battleships are in it.
7+
* The battleships are represented with 'X's, empty slots are represented with '.'s.
8+
* You may assume the following rules:
49
510
You receive a valid board, made of only battleships or empty slots.
6-
Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
11+
Battleships can only be placed horizontally or vertically.
12+
In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
713
At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.
14+
815
Example:
916
1017
X..X
@@ -27,86 +34,82 @@
2734
*/
2835
publicclass_419 {
2936

30-
/**
31-
* credit: https://discuss.leetcode.com/topic/62970/simple-java-solution,
32-
* basically, it only counts the top-left one while ignoring all other parts of one battleship,
33-
* using the top-left one as a representative for one battle.
34-
* This is achieved by counting cells that don't have 'X' to the left and above them.
35-
*/
36-
publicintcountBattleships_no_modify_original_input(char[][]board) {
37-
if (board ==null ||board.length ==0) {
38-
return0;
39-
}
40-
intcount =0;
41-
intm =board.length;
42-
intn =board[0].length;
43-
for (inti =0;i <m;i++) {
44-
for (intj =0;j <n;j++) {
45-
if (board[i][j] =='.') {
46-
continue;//if it can pass this line, then board[i][j] must be 'X'
47-
}
48-
if (j >0 &&board[i][j -1] =='X') {
49-
continue;//then we check if its left is 'X'
50-
}
51-
if (i >0 &&board[i -1][j] =='X') {
52-
continue;//also check if its top is 'X'
37+
publicstaticclassSolution1 {
38+
/**
39+
* credit: https://discuss.leetcode.com/topic/62970/simple-java-solution,
40+
* <p>
41+
* This solution does NOT modify original input.
42+
* Basically, it only counts the top-left one while ignoring all other parts of one battleship,
43+
* using the top-left one as a representative for one battle.
44+
* This is achieved by counting cells that don't have 'X' to the left and above them.
45+
*/
46+
publicintcountBattleships(char[][]board) {
47+
if (board ==null ||board.length ==0) {
48+
return0;
49+
}
50+
intcount =0;
51+
intm =board.length;
52+
intn =board[0].length;
53+
for (inti =0;i <m;i++) {
54+
for (intj =0;j <n;j++) {
55+
if (board[i][j] =='.') {
56+
continue;//if it can pass this line, then board[i][j] must be 'X'
57+
}
58+
if (j >0 &&board[i][j -1] =='X') {
59+
continue;//then we check if its left is 'X'
60+
}
61+
if (i >0 &&board[i -1][j] =='X') {
62+
continue;//also check if its top is 'X'
63+
}
64+
count++;
5365
}
54-
count++;
5566
}
67+
returncount;
5668
}
57-
returncount;
5869
}
5970

60-
/**
61-
* My original solution, actually modified the input. I just undo it at the end.
62-
*/
63-
publicintcountBattleships(char[][]board) {
64-
if (board ==null ||board.length ==0) {
65-
return0;
66-
}
67-
intresult =0;
68-
intm =board.length;
69-
intn =board[0].length;
70-
for (inti =0;i <m;i++) {
71-
for (intj =0;j <n;j++) {
72-
if (board[i][j] =='X') {
73-
result++;
74-
dfs(board,i,j,m,n);
71+
publicstaticclassSolution2 {
72+
/**
73+
* My original solution, actually modified the input. I just undo it at the end.
74+
*/
75+
publicintcountBattleships(char[][]board) {
76+
if (board ==null ||board.length ==0) {
77+
return0;
78+
}
79+
intresult =0;
80+
intm =board.length;
81+
intn =board[0].length;
82+
for (inti =0;i <m;i++) {
83+
for (intj =0;j <n;j++) {
84+
if (board[i][j] =='X') {
85+
result++;
86+
dfs(board,i,j,m,n);
87+
}
7588
}
7689
}
77-
}
7890

79-
for (inti =0;i <m;i++) {
80-
for (intj =0;j <n;j++) {
81-
if (board[i][j] =='#') {
82-
board[i][j] ='X';
91+
for (inti =0;i <m;i++) {
92+
for (intj =0;j <n;j++) {
93+
if (board[i][j] =='#') {
94+
board[i][j] ='X';
95+
}
8396
}
8497
}
98+
returnresult;
8599
}
86-
returnresult;
87-
}
88100

89-
privatevoiddfs(char[][]board,intx,inty,intm,intn) {
90-
if (x <0 ||x >=m ||y <0 ||y >=n ||board[x][y] !='X') {
91-
return;
92-
}
93-
if (board[x][y] =='X') {
94-
board[x][y] ='#';
101+
privatevoiddfs(char[][]board,intx,inty,intm,intn) {
102+
if (x <0 ||x >=m ||y <0 ||y >=n ||board[x][y] !='X') {
103+
return;
104+
}
105+
if (board[x][y] =='X') {
106+
board[x][y] ='#';
107+
}
108+
dfs(board,x +1,y,m,n);
109+
dfs(board,x,y +1,m,n);
110+
dfs(board,x -1,y,m,n);
111+
dfs(board,x,y -1,m,n);
95112
}
96-
dfs(board,x +1,y,m,n);
97-
dfs(board,x,y +1,m,n);
98-
dfs(board,x -1,y,m,n);
99-
dfs(board,x,y -1,m,n);
100113
}
101114

102-
publicstaticvoidmain(String...strings) {
103-
char[][]board =newchar[][]{
104-
{'X','.','.','X'},
105-
{'.','.','.','X'},
106-
{'.','.','.','X'},
107-
};
108-
109-
_419test =new_419();
110-
System.out.println(test.countBattleships(board));
111-
}
112-
}
115+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp