LeetCode 419. 棋盘上的战舰解题思路关键观察战舰之间不相邻至少有一个空格隔开因此每艘战舰必然有唯一的头部——即最左水平时或最上垂直时的那格 ‘X’。判断一个 ‘X’ 是头部只需· 左边不是 ‘X’或已在最左列· 上边不是 ‘X’或已在最上行满足这两条就说明它是某艘战舰的起点计数 1。因为不相邻战舰不会出现「L 形」或交叉头部与战舰一一对应不会漏数也不会重数。代码实现O(1) 空间推荐classSolution{publicintcountBattleships(char[][]board){intmboard.length,nboard[0].length;intcount0;for(inti0;im;i){for(intj0;jn;j){if(board[i][j]X){// 左边和上边都不是 X → 战舰头部booleanleftOk(j0)||board[i][j-1]!X;booleanupOk(i0)||board[i-1][j]!X;if(leftOkupOk){count;}}}}returncount;}}代码实现DFS思路通用如果题目放宽了「战舰不相邻」的条件例如允许 L 形、允许相接触头部计数法就失效了此时要用 DFS/BFS 做连通分量计数classSolution{privateintm,n;privatechar[][]board;publicintcountBattleships(char[][]board){this.boardboard;this.mboard.length;this.nboard[0].length;intcount0;for(inti0;im;i){for(intj0;jn;j){if(board[i][j]X){count;dfs(i,j);}}}returncount;}privatevoiddfs(inti,intj){if(i0||im||j0||jn||board[i][j]!X)return;board[i][j].;// 原地标记为已访问dfs(i1,j);dfs(i-1,j);dfs(i,j1);dfs(i,j-1);}}关键点说明头部判定是唯一性保证一艘战舰的水平部分只有最左格子的左边是 .垂直部分只有最上格子的上边是 .所以一艘战舰恰好贡献一个计数。j 0 / i 0 的边界要写成「越界视为空」的逻辑即 (j 0 || board[i][j-1] ! ‘X’)。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) 空间」的优化体现对题目特殊条件的敏感度。