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

By Long Luo

Leetcode 419. 甲板上的战舰。

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

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

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 \times n \times \max(m, n))$。

• 空间复杂度：$$O(m \times n)$$。

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

一次扫描，允许修改原始数组，遍历之后将原来的X修改为.。

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 \times n \times \max(m, n))$。

• 空间复杂度：$O(1)$。

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

DFS一次扫描，允许修改原始数组，遍历之后将原来的X修改为.。

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 \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{'.'}$；

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

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