Skip to content

Commit 17f4f58

Browse files
fishercoder1534fishercoder1534
committed
refactor 419
1 parent 4556542 commit 17f4f58

File tree

1 file changed

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

1 file changed

+73
-70
lines changed

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

Lines changed: 73 additions & 70 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,17 @@
11
package com.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
public class _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-
public int countBattleships_no_modify_original_input(char[][] board) {
37-
if (board == null || board.length == 0) {
38-
return 0;
39-
}
40-
int count = 0;
41-
int m = board.length;
42-
int n = board[0].length;
43-
for (int i = 0; i < m; i++) {
44-
for (int j = 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+
public static class Solution1 {
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+
public int countBattleships(char[][] board) {
47+
if (board == null || board.length == 0) {
48+
return 0;
49+
}
50+
int count = 0;
51+
int m = board.length;
52+
int n = board[0].length;
53+
for (int i = 0; i < m; i++) {
54+
for (int j = 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+
return count;
5668
}
57-
return count;
5869
}
5970

60-
/**
61-
* My original solution, actually modified the input. I just undo it at the end.
62-
*/
63-
public int countBattleships(char[][] board) {
64-
if (board == null || board.length == 0) {
65-
return 0;
66-
}
67-
int result = 0;
68-
int m = board.length;
69-
int n = board[0].length;
70-
for (int i = 0; i < m; i++) {
71-
for (int j = 0; j < n; j++) {
72-
if (board[i][j] == 'X') {
73-
result++;
74-
dfs(board, i, j, m, n);
71+
public static class Solution2 {
72+
/**
73+
* My original solution, actually modified the input. I just undo it at the end.
74+
*/
75+
public int countBattleships(char[][] board) {
76+
if (board == null || board.length == 0) {
77+
return 0;
78+
}
79+
int result = 0;
80+
int m = board.length;
81+
int n = board[0].length;
82+
for (int i = 0; i < m; i++) {
83+
for (int j = 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 (int i = 0; i < m; i++) {
80-
for (int j = 0; j < n; j++) {
81-
if (board[i][j] == '#') {
82-
board[i][j] = 'X';
91+
for (int i = 0; i < m; i++) {
92+
for (int j = 0; j < n; j++) {
93+
if (board[i][j] == '#') {
94+
board[i][j] = 'X';
95+
}
8396
}
8497
}
98+
return result;
8599
}
86-
return result;
87-
}
88100

89-
private void dfs(char[][] board, int x, int y, int m, int n) {
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+
private void dfs(char[][] board, int x, int y, int m, int n) {
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-
public static void main(String... strings) {
103-
char[][] board = new char[][]{
104-
{'X', '.', '.', 'X'},
105-
{'.', '.', '.', 'X'},
106-
{'.', '.', '.', 'X'},
107-
};
108-
109-
_419 test = new _419();
110-
System.out.println(test.countBattleships(board));
111-
}
112-
}
115+
}

0 commit comments

Comments
 (0)