LeetCode 419. 棋盘上的战舰

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 华为
标签
数组 深度优先搜索 矩阵
目录

题目描述

✅ 419. 棋盘上的战舰

题意分析

题目目标：给定一个由 'X' 和 '.' 组成的二维棋盘，'X' 表示战舰所占的格子，要求返回棋盘上战舰的总数。
核心约束：题目给了两条极强的形状保证——每艘战舰只能是横着的一行或竖着的一列（也可以只有一格），并且任意两艘战舰之间至少隔着一个空格，不会相邻。这两条合起来意味着任何一个 'X' 连通块必然恰好是一艘完整的战舰，绝不会出现两艘舰粘在一起变成 L 形的情况，因此不需要真的去做连通性搜索来区分它们。进阶要求还提出「只扫描一次、不修改棋盘、不使用额外空间」，这实际上是在把解法往「用局部信息就地判定」的方向逼。
边界处理：棋盘可能只有一行或一列，判断邻居时必须先做下标越界检查；第一行的格子没有上方邻居、第一列的格子没有左方邻居，这两处正是判定条件最容易写错的地方；棋盘可能全是 '.'，答案为 0；单个 'X' 也算一艘完整战舰，不能因为它只有一格就被漏掉。

解法：原地标记

核心思路

战舰只能是水平或垂直直线，并且不同战舰不相邻。每艘战舰因此都有且只有一个“舰首”：水平舰最左侧的格子、垂直舰最上侧的格子、单格舰本身。

一个 'X' 是舰首，当且仅当它上方不是 'X'，并且左侧也不是 'X'。若上方有 'X'，它属于同一艘竖舰；若左侧有 'X'，它属于同一艘横舰。只数舰首即可，无需搜索、访问数组或修改棋盘。

不变量：按行扫描到 (row, col) 时，count 等于此前所有格子中舰首的数量；当前格只依据自身、上方和左侧即可唯一判定。

正确性：每艘合法战舰恰有一个最上或最左起点，该格上方和左侧均不是 'X'，一定被计数；舰身其余格至少有上方或左侧同舰格，一定不会重复计数。舰首与战舰一一对应，所以计数就是答案。

解题步骤

  1. 按行遍历棋盘中的每个格子。
  2. 跳过 '.'。
  3. 若上方或左侧是 'X'，当前格属于已出现的舰身，跳过。
  4. 其余 'X' 即为新战舰舰首，答案加一。

棋盘 [[X,.,.,X],[.,.,.,X],[.,.,.,X]] 中，只会计数 (0,0) 与 (0,3)，答案为 2。单行、单列和单格战舰都由同一条件覆盖；空棋盘安全返回 0。

代码实现

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)$，每个格子只检查一次。
  • 空间复杂度：$O(1)$，不修改棋盘，也不使用访问标记或递归栈。

关键点总结

  • 强形状约束允许为每个连通对象选择唯一代表元，本题的代表元是舰首。
  • 舰首判定只看上方和左侧，不需要检查完整舰身。
  • 短路边界判断必须写在邻居访问之前。
  • 若战舰允许相邻或弯折，这个局部判定将失效，必须改用连通块搜索。

易错点总结

  • 只检查上方：单行横舰的每个 'X' 都会被重复计数。
  • 只检查左侧：单列竖舰会被重复计数。
  • 要求上方和左侧同时为 'X' 才跳过：舰身通常只在一个方向有前驱，应使用两个独立排除条件。
  • 邻居访问前不判断边界：首行或首列会发生越界。
  • 搜索并改写棋盘：结果虽可能正确，却违反不修改输入和常数额外空间的进阶要求。

相似题目

题目 难度 考察点
200. 岛屿数量 中等 连通块形状任意且允许相邻，判定式失效，必须用 DFS/BFS 或并查集
695. 岛屿的最大面积 中等 不止要数块数还要度量每块的大小，搜索时需要携带并返回累计面积
463. 岛屿的周长 简单 同样可以只靠局部邻居关系一次遍历得出答案，统计的是暴露边而非起点
130. 被围绕的区域 中等 需要从边界反向染色来区分「与外界连通」和「被包围」，考察搜索起点的选择
1254. 统计封闭岛屿的数目 中等 在数连通块的基础上追加「不能触碰边界」的过滤条件
305. 岛屿数量 II 困难 陆地动态加入，静态扫描完全不适用，必须用并查集在线维护连通块数量