企业官网建设流程全解析

LeetCode 419. 棋盘上的战舰

解题思路

关键观察：战舰之间不相邻（至少有一个空格隔开）

因此每艘战舰必然有唯一的"头部"——即最左（水平时）或最上（垂直时）的那格 ‘X’。判断一个 ‘X’ 是头部只需：

· 左边不是 ‘X’（或已在最左列）
· 上边不是 ‘X’（或已在最上行）

满足这两条，就说明它是某艘战舰的起点，计数 +1。因为不相邻，战舰不会出现「L 形」或交叉，头部与战舰一一对应，不会漏数也不会重数。

代码实现（O(1) 空间，推荐）

classSolution{publicintcountBattleships(char[][]board){intm=board.length,n=board[0].length;intcount=0;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(board[i][j]=='X'){// 左边和上边都不是 'X' → 战舰头部booleanleftOk=(j==0)||board[i][j-1]!='X';booleanupOk=(i==0)||board[i-1][j]!='X';if(leftOk&&upOk){count++;}}}}returncount;}}

代码实现（DFS，思路通用）

如果题目放宽了「战舰不相邻」的条件（例如允许 L 形、允许相接触），头部计数法就失效了，此时要用 DFS/BFS 做连通分量计数：

classSolution{privateintm,n;privatechar[][]board;publicintcountBattleships(char[][]board){this.board=board;this.m=board.length;this.n=board[0].length;intcount=0;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(board[i][j]=='X'){count++;dfs(i,j);}}}returncount;}privatevoiddfs(inti,intj){if(i<0||i>=m||j<0||j>=n||board[i][j]!='X')return;board[i][j]='.';// 原地标记为已访问dfs(i+1,j);dfs(i-1,j);dfs(i,j+1);dfs(i,j-1);}}

关键点说明

1. 头部判定是唯一性保证：一艘战舰的水平部分只有最左格子的左边是 .，垂直部分只有最上格子的上边是 .，所以一艘战舰恰好贡献一个计数。
2. j == 0 / i == 0 的边界：要写成「越界视为空」的逻辑，即 (j == 0 || board[i][j-1] != ‘X’)。
3. DFS 版会修改原数组：用 ‘.’ 覆盖 ‘X’ 做访问标记，省一个 visited 数组；如果不想改输入，需额外开 boolean[][]。

复杂度分析

解法 时间复杂度 空间复杂度
头部计数 O(m × n) O(1)
DFS O(m × n) O(m × n)（递归栈最坏）

延伸与对比

· LeetCode 200. 岛屿数量：几乎同款，但岛屿可以相邻/斜接，只能用 DFS/BFS/并查集，本题因「不相邻」条件可用更简洁的头部计数。
· LeetCode 695. 岛屿的最大面积：连通分量 + 面积统计。
· 面试小技巧：先说 DFS 通解，再点出「战舰不相邻 ⇒ 头部计数 O(1) 空间」的优化，体现对题目特殊条件的敏感度。