[Leetcode][419. 甲板上的战舰] 4种方法：一次遍历，DFS，统计战舰起点
By Long Luo
方法一：一次遍历 + 不修改原始数组
一次扫描，\(O(m \times n)\) 额外空间，使用一个与矩阵同等大小的辅助数组 \(visited\) 记录访问过的位置。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public static int countBattleships(char[][] board) {
int ans = 0;
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && board[i][j] == 'X') {
visited[i][j] = true;
ans++;
for (int k = i + 1; k < m && board[k][j] == 'X'; k++) {
visited[k][j] = true;
}
for (int k = j + 1; k < n && board[i][k] == 'X'; k++) {
visited[i][k] = true;
}
}
}
}
return ans;
}
复杂度分析：
时间复杂度：\(O(m \times n \times \max(m, n))\)。
空间复杂度：\[O(m \times n)\]。
方法二：一次遍历 + 修改原始数组
一次扫描，允许修改原始数组，遍历之后将原来的X修改为.。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public static int countBattleships(char[][] board) {
int ans = 0;
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && board[i][j] == 'X') {
visited[i][j] = true;
ans++;
for (int k = i + 1; k < m && board[k][j] == 'X'; k++) {
visited[k][j] = true;
}
for (int k = j + 1; k < n && board[i][k] == 'X'; k++) {
visited[i][k] = true;
}
}
}
}
return ans;
}
复杂度分析：
时间复杂度：\(O(m \times n \times \max(m, n))\)。
空间复杂度：\(O(1)\)。
方法三：DFS一次遍历 + 修改原始数组
DFS一次扫描，允许修改原始数组，遍历之后将原来的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
35public int countBattleships(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return 0;
}
int ans = 0;
int row = board.length;
int col = board[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'X') {
ans++;
dfs(board, i, j);
}
}
}
return ans;
}
public void dfs(char[][] board, int x, int y) {
int[] dx = {0, 1};
int[] dy = {1, 0};
board[x][y] = '.';
for (int dir = 0; dir < 2; dir++) {
int nX = x + dx[dir];
int nY = y + dy[dir];
if (nX >= 0 && nX < board.length && nY >= 0 && nY < board[0].length && board[nX][nY] == 'X') {
dfs(board, nX, nY);
}
}
}
复杂度分析：
时间复杂度：\(O(m \times n \times \max(m, n))\)。
空间复杂度：\(O(1)\)。
方法四：只需要统计起点
思路与算法：
只能一次扫描，使用 \(O(1)\) 额外空间，并且不修改甲板的值。
因为题目中给定的两艘战舰之间至少有一个水平或垂直的空位分隔，任意两个战舰之间是不相邻的，因此我们可以通过枚举每个战舰的左上顶点即可统计战舰的个数。假设矩阵的行数为 \(\textit{row}\)，矩阵的列数 \(\textit{col}\)，矩阵中的位置 \((i, j)\) 为战舰的左上顶点，需满足以下条件：
- 满足当前位置所在的值 \(\textit{board}[i][j] = \texttt{'X'}\)；
- 满足当前位置的左则为空位，即 \(\textit{board}[i][j-1] = \texttt{'.'}\)；
- 满足当前位置的上方为空位，即 \(\textit{board}[i-1][j] = \texttt{'.'}\)；
我们统计出所有战舰的左上顶点的个数即为所有战舰的个数。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public static int countBattleships(char[][] board) {
int ans = 0;
int row = board.length;
int col = board[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'X') {
ans++;
if (i > 0 && board[i - 1][j] == 'X') {
continue;
}
if (j > 0 && board[i][j - 1] == 'X') {
continue;
}
}
}
}
return ans;
}
复杂度分析：
时间复杂度：\(O(m \times n)\)。
空间复杂度：\(O(1)\)。
All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗