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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 3 分钟

By Long Luo

Leetcode 419. 甲板上的战舰 。

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

一次扫描，O(m×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
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×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(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(1) 。

方法四：只需要统计起点

思路与算法：

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

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

  • 满足当前位置所在的值 board[i][j]='X' ；
  • 满足当前位置的左则为空位，即 board[i][j−1]='.' ；
  • 满足当前位置的上方为空位，即 board[i−1][j]='.' ；

我们统计出所有战舰的左上顶点的个数即为所有战舰的个数。

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(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. 😉😃💗