05 August 2008
具体做法,根据从左到右和从上到下的顺序遍历数组,碰到字符为’X’则向下或向右寻找,直到找不到’X’,并且把走过的点都重置为’.’
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
private int rows;
private int cols;
public int countBattleships(char[][] board) {
if (board == null || board.length == 0) return 0;
rows = board.length;
cols = board[0].length;
int sum = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if ('X' == board[i][j]) {
//由于战舰只能水平或者垂直放置,所以可以先确定下方向
if (j + 1 < cols && board[i][j + 1] == 'X') {
search(board, i, j, false);
} else if (i + 1 < rows && board[i + 1][j] == 'X') {
search(board, i, j, true);
}
sum++;
}
}
}
return sum;
}
private void search(char[][] board, int i, int j, boolean isVertical) {
if (i == rows || j == cols || board[i][j] == '.') return;
board[i][j] = '.';
if (isVertical) {
search(board, i + 1, j, isVertical);
} else {
search(board, i, j + 1, isVertical);
}
}
}
上面的写法虽然完成了题目要求,但进阶要求是不修改并且在O(1)额外空间内完成。
现在第一种做法虽然空间使用了O(1)但没有达到不修改甲板值的效果,可以稍微对上面的算法进行改进,将改值部分去掉,然后碰到’X’时,检查上方或左方是否有’X’,若存在,就代表已经计数过了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private int rows;
private int cols;
public int countBattleships(char[][] board) {
if (board == null || board.length == 0) {
return 0;
}
rows = board.length;
cols = board[0].length;
int sum = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if ('X' == board[i][j]) {
if (search(board, i - 1, j) && search(board, i, j - 1)) {
sum++;
}
}
}
}
return sum;
}
private boolean search(char[][] board, int i, int j) {
if (i == -1 || j == -1 || board[i][j] == '.') return true;
return board[i][j] != 'X';
}
}