Medium

题目描述

给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格上都可能停有一艘战舰 'X' 或者是空位 '.'，返回在甲板 board 上放置的战舰的数量。

战舰只能水平或者垂直放置在 board 上。换句话说，战舰只能由 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状构成，其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔（即没有相邻的战舰）。

示例 1：

输入：board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
输出：2

示例 2：

输入：board = [["."]]
输出：0

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] 是 '.' 或 'X'

进阶： 你可以实现一次扫描算法，并只使用 O(1) 额外空间，并且不修改甲板的值来解决这个问题吗？

解题思路

这道题有两种主要解法：

解法一：DFS遍历 使用深度优先搜索，当遇到战舰的第一个格子时，通过DFS将整艘战舰标记为已访问，然后计数加一。这种方法需要修改原数组或使用额外的visited数组。

解法二：一次扫描（推荐） 观察题目特点：战舰只能水平或垂直放置，且战舰之间不相邻。这意味着每艘战舰都有一个"左上角"的起始点。我们只需要统计这些起始点的数量即可。

对于每个 'X' 格子，如果它的左边和上边都不是 'X'，那么它就是一艘战舰的起始点。这样就能在一次遍历中完成统计，时间复杂度O(mn)，空间复杂度O(1)，且不需要修改原数组。

具体判断条件：

  • 当前格子是 'X'
  • 左边格子不存在或不是 'X'
  • 上边格子不存在或不是 'X'

这种方法充分利用了题目约束条件，是最优解法。

代码实现

class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int count = 0;
        int m = board.size(), n = board[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') {
                    // 检查是否为战舰的起始点（左上角）
                    if ((i == 0 || board[i-1][j] == '.') && 
                        (j == 0 || board[i][j-1] == '.')) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        count = 0
        m, n = len(board), len(board[0])
        
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'X':
                    # 检查是否为战舰的起始点（左上角）
                    if (i == 0 or board[i-1][j] == '.') and \
                       (j == 0 or board[i][j-1] == '.'):
                        count += 1
        
        return count

public class Solution {
    public int CountBattleships(char[][] board) {
        int count = 0;
        int m = board.Length, n = board[0].Length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') {
                    // 检查是否为战舰的起始点（左上角）
                    if ((i == 0 || board[i-1][j] == '.') && 
                        (j == 0 || board[i][j-1] == '.')) {
                        count++;
                    }
                }
            }
        }
        
        return count;
    }
}

/**
 * @param {character[][]} board
 * @return {number}
 */
var countBattleships = function(board) {
    let count = 0;
    
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[i].length; j++) {
            if (board[i][j] === 'X') {
                if ((i === 0 || board[i-1][j] === '.') && 
                    (j === 0 || board[i][j-1] === '.')) {
                    count++;
                }
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n)需要遍历整个矩阵一次
空间复杂度O(1)只使用常数级额外空间

相关题目