[Leetcode][419. 甲板上的战舰] 4种方法:一次遍历,DFS,统计战舰起点

By Long Luo

Leetcode 419. 甲板上的战舰

方法一:一次遍历 + 不修改原始数组

一次扫描,O(m×n)O(m \times n)额外空间,使用一个与矩阵同等大小的辅助数组visitedvisited记录访问过的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public 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×n×max(m,n))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
24
public 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×n×max(m,n))O(m \times n \times \max(m, n))

  • 空间复杂度:O(1)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
35
public 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×n×max(m,n))O(m \times n \times \max(m, n))

  • 空间复杂度:O(1)O(1)

方法四:只需要统计起点

思路与算法:

只能一次扫描,使用O(1)O(1)额外空间,并且不修改甲板的值。

因为题目中给定的两艘战舰之间至少有一个水平或垂直的空位分隔,任意两个战舰之间是不相邻的,因此我们可以通过枚举每个战舰的左上顶点即可统计战舰的个数。假设矩阵的行数为row\textit{row},矩阵的列数col\textit{col},矩阵中的位置(i,j)(i, j)为战舰的左上顶点,需满足以下条件:

  • 满足当前位置所在的值board[i][j]=’X’\textit{board}[i][j] = \texttt{'X'}
  • 满足当前位置的左则为空位,即board[i][j1]=’.’\textit{board}[i][j-1] = \texttt{'.'}
  • 满足当前位置的上方为空位,即board[i1][j]=’.’\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
21
public 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×n)O(m \times n)

  • 空间复杂度:O(1)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. 😉😃💗