LeetCode 419. 棋盘上的战舰
题目描述
题意分析
棋盘用
X表示战舰格子、.表示空位。每艘战舰是一条连续的水平线或垂直线，也可以只占一个格子；不同战舰之间不会横向或纵向相邻，需要统计战舰总数。题目进阶要求只扫描一遍、使用常数额外空间，并且不修改棋盘。利用战舰的直线形状与间隔条件，只统计每艘舰唯一的起点即可满足这些要求。
解法：统计战舰起点
核心思路
[!blue]
给每艘舰选择唯一代表：水平舰取最左格，垂直舰取最上格，单格舰取它自己。这个代表都是一个“上方没有
X，左侧也没有X”的战舰格子。对水平舰，除最左格外的所有格子都有左侧相邻的同舰
X，所以都能排除；最左格没有左侧舰身，而上方也不能存在其他战舰的相邻格，因此会被保留。对垂直舰同理，除最上格外都有上方同舰X，只有最上格被保留。单格舰周围没有相邻舰格，也恰好计数一次。这样，每艘战舰恰好贡献一个满足条件的位置，所有舰身位置都被排除，统计这些位置就等于统计战舰。形状与互不相邻的保证，是这个一一对应关系成立的依据。
逐格检查当前值、上方和左侧就足够，不需要继续沿舰身搜索。判断始终读取原棋盘，不能为了标记已计数而修改
X，否则后续舰身可能失去用来识别同一艘舰的邻格。
解题步骤
- 扫描每个格子，当前不是
X就跳过。- 若不在第一行且上方是
X，它属于已有垂直舰的舰身，跳过。- 若不在第一列且左侧是
X，它属于已有水平舰的舰身，跳过。- 两个前驱都不存在的
X是舰首，将计数加一。第一行没有上方邻格，第一列没有左侧邻格，应先判断边界再读取。全空棋盘没有任何计数位置；代码还直接处理了空棋盘输入。
代码实现
class Solution {
public int countBattleships(char[][] board) {
if (board.length == 0 || board[0].length == 0) {
return 0;
}
int count = 0;
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[0].length; col++) {
if (board[row][col] != 'X') {
continue;
}
// 有上方同舰格时是竖向舰身，不重复计数。
if (row > 0 && board[row - 1][col] == 'X') {
continue;
}
// 有左侧同舰格时是横向舰身，其余位置才是舰首。
if (col > 0 && board[row][col - 1] == 'X') {
continue;
}
count++;
}
}
return count;
}
}
func countBattleships(board [][]byte) int {
if len(board) == 0 || len(board[0]) == 0 {
return 0
}
count := 0
for row := range board {
for col := range board[row] {
if board[row][col] != 'X' {
continue
}
// 有上方同舰格时是竖向舰身，不重复计数。
if row > 0 && board[row-1][col] == 'X' {
continue
}
// 有左侧同舰格时是横向舰身，其余位置才是舰首。
if col > 0 && board[row][col-1] == 'X' {
continue
}
count++
}
}
return count
}
复杂度分析
- 时间复杂度：$O(mn)$，其中 $m,n$ 是棋盘的行列数。每个格子只扫描一次，并检查常数个邻格。
- 空间复杂度：$O(1)$，只维护计数和下标，没有访问表，也不修改棋盘，满足进阶要求。
关键点总结
[!green]
- 唯一代表是最上或最左的舰首。
- 邻居边界先判断，再读取格子。
- 单格战舰自然满足两个前驱都不存在。
易错点总结
[!yellow]
- 只检查上方：横向舰身被重复统计。
- 只检查左侧：纵向舰身被重复统计。
- 上方和左侧同时为 X 才排除：普通直线舰身通常只有一个前驱。
- 计数后改写棋盘：会破坏后续用原格子判断舰身的依据。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！