题目
给你一个大小为 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.lengthn == board[i].length1 <= m, n <= 200board[i][j]是 ‘.’ 或 ‘X’
进阶：你可以实现一次扫描算法，并只使用 O(1) 额外空间，并且不修改 board 的值来解决这个问题吗？
代码
完整代码
void findX(char** board, int boardSize, int* boardColSize, int i, int j)
{
while((i + 1 < boardSize) && board[i + 1][j] == 'X') // 竖着
{
board[i + 1][j] = '.';
i++;
}
while ((j + 1 < (*boardColSize)) && board[i][j + 1] == 'X') // 横着
{
board[i][j + 1] = '.';
j++;
}
}
int countBattleships(char** board, int boardSize, int* boardColSize){
int Xcnt = 0;
for (int i = 0; i < boardSize; i++)
{
for (int j = 0; j < (*boardColSize); j++)
{
if(board[i][j] == 'X')
{
Xcnt++;
findX(board, boardSize, boardColSize, i, j);
}
}
}
return Xcnt;
}
思路分析
题目的要求是计算出矩阵 board 中放置的战舰数量。战舰只能水平或者垂直放置且彼此之间没有相邻。我们的目标是遍历整个矩阵，找到所有的战舰并进行计数。
拆解分析
- 遍历矩阵：使用两层嵌套的
for循环遍历整个board。 - 找到战舰：当找到一个战舰（即 ‘X’），增加战舰计数。
- 清理战舰：为了防止重复计数，调用
findX函数将已经计数的战舰用 ‘.’ 替换（通过横向和纵向搜索替换）。 - 返回结果：遍历完成后，返回计数的战舰数量。
复杂度分析
- 时间复杂度：
O(m * n)，其中m是矩阵的行数，n是矩阵的列数。我们需要遍历每个单元格来查找战舰。 - 空间复杂度：
O(1)，没有使用额外的空间，只在原矩阵上进行操作。
结果
一题多解
一次扫描法（Single Pass Approach）
一次扫描法思路分析
我们可以通过一次扫描矩阵，并使用额外的条件检查来避免修改矩阵值。在扫描时，仅在战舰的起始位置（即左上角）进行计数。此解法符合进阶条件。
具体步骤：
- 仅在当前位置的上方和左方均为空位（或者越界）时计数战舰。
- 继续扫描直到完成整个矩阵。
一次扫描法复杂度分析
- 时间复杂度：
O(m * n)，需要遍历每个单元格。 - 空间复杂度：
O(1)，只使用常量空间。
下面是具体的实现代码：
完整代码
int countBattleshipsSinglePass(char** board, int boardSize, int* boardColSize) {
int Xcnt = 0;
for (int i = 0; i < boardSize; i++) {
for (int j = 0; j < (*boardColSize); j++) {
if (board[i][j] == 'X' &&
(i == 0 || board[i - 1][j] == '.') &&
(j == 0 || board[i][j - 1] == '.')) {
Xcnt++;
}
}
}
return Xcnt;
}
复杂度分析
- 时间复杂度：
O(m * n)，因为需要遍历每个单元格。 - 空间复杂度：
O(1)，只使用常量空间。
