甲板上的战舰
难度:
标签:
题目描述
给你一个大小为 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)
额外空间,并且不修改 board
的值来解决这个问题吗?
代码结果
运行时间: 21 ms, 内存: 18.2 MB
/*
* 题目思路:
* 使用Java Stream API同样可以实现对战舰数量的统计。利用流的遍历特性进行判断,
* 如果当前格子是'X',且其上边和左边的格子不是'X',则认为这是一个战舰的头部。
*/
import java.util.stream.IntStream;
public class Solution {
public int countBattleships(char[][] board) {
return (int) IntStream.range(0, board.length)
.flatMap(i -> IntStream.range(0, board[0].length)
.filter(j -> board[i][j] == 'X' && (i == 0 || board[i - 1][j] != 'X') && (j == 0 || board[i][j - 1] != 'X'))
).count();
}
}
解释
方法:
这个题解采用了一次遍历的思路。从矩阵的左上角开始,遍历每个格子。当遇到一个战舰('X')时,将计数器加1,并将该格子标记为已访问('.')。然后向下和向右分别搜索,将连续的战舰格子都标记为已访问,直到遇到空位('.')或越界为止。这样可以确保每个战舰只被计数一次。
时间复杂度:
O(m*n)
空间复杂度:
O(1)
代码细节讲解
🦆
在遍历矩阵时,你是如何决定只在发现'X'的首个单元格时增加战舰计数器,而不是对每个'X'都增加?
▷🦆
为什么在检测到一个'X'后,只向下和向右搜索连续的战舰,而不是向上或向左?
▷🦆
题解中提到标记已访问的战舰格子为'.',这种修改原数据的方法会不会对问题求解产生其他影响,例如重新运行算法或并行处理?
▷🦆
在代码中,如果遇到一个边界上的战舰(例如在矩阵的最右列或最下行),算法如何确保不会越界?
▷