LeetCode 419中等数组 · 哈希
棋盘上的战舰 图解题解
这道题到底在问什么
给一个 m×n 的棋盘 board,格子是战舰 X 或空位点。战舰只能是 1×k 的横排或 k×1 的竖排,且任意两艘之间至少隔一个空格(不相邻)。返回战舰的数量。
- 输入
- board = [[X,.,.,X],[.,.,.,X],[.,.,.,X]]
- 输出
- 2 (一艘单格 + 一艘竖排三格)
- 输入
- board = [[.]]
- 输出
- 0 (没有 X)
最优解：一步一步想明白
- 3记住这把尺子:X 且「上不是 X、左不是 X」就计数。下面每一帧都在套它。
- 4count = 0;扫描指针从 (0,0) 起逐行往右走蓝色是空位,灰色是还没扫到的战舰格 X。套路:一行一行、从左到右扫,只在 X 的「左上角」处计数。
- 5看 (0,0) = X,检查它的上方与左方 | 战舰数 = 0扫到 (0,0) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
- 6(0,0) 是船头,战舰数 = 1上方是棋盘外边界,左方是棋盘外边界,所以 (0,0) 是一艘新战舰的左上角(变绿),战舰数加到 1。
- 7看 (0,1) = 空位 | 战舰数 = 1扫到 (0,1),这里是空位,什么都不用做,继续往右扫。当前战舰数 1。
- 8看 (0,2) = X,检查它的上方与左方 | 战舰数 = 1扫到 (0,2) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
- 9(0,2) 是船头,战舰数 = 2上方是棋盘外边界,左方是空位,所以 (0,2) 是一艘新战舰的左上角(变绿),战舰数加到 2。
- 10看 (0,3) = X,检查它的上方与左方 | 战舰数 = 2扫到 (0,3) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
- 11(0,3) 是船身,跳过 | 战舰数 = 2它正左方 (0,2) 也是 X,说明 (0,3) 只是同一艘船的后半截(变灰),不是船头,跳过不计。战舰数仍是 2。
- 12看 (0,4) = 空位 | 战舰数 = 2扫到 (0,4),这里是空位,什么都不用做,继续往右扫。当前战舰数 2。
- 13看 (1,0) = X,检查它的上方与左方 | 战舰数 = 2扫到 (1,0) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
- 14(1,0) 是船身,跳过 | 战舰数 = 2它正上方 (0,0) 也是 X,说明 (1,0) 只是同一艘船的后半截(变灰),不是船头,跳过不计。战舰数仍是 2。
- 15看 (1,1) = 空位 | 战舰数 = 2扫到 (1,1),这里是空位,什么都不用做,继续往右扫。当前战舰数 2。
- 16看 (1,2) = 空位 | 战舰数 = 2扫到 (1,2),这里是空位,什么都不用做,继续往右扫。当前战舰数 2。
- 17看 (1,3) = 空位 | 战舰数 = 2扫到 (1,3),这里是空位,什么都不用做,继续往右扫。当前战舰数 2。
- 18看 (1,4) = X,检查它的上方与左方 | 战舰数 = 2扫到 (1,4) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
- 19(1,4) 是船头,战舰数 = 3上方是空位,左方是空位,所以 (1,4) 是一艘新战舰的左上角(变绿),战舰数加到 3。
- 20看 (2,0) = 空位 | 战舰数 = 3扫到 (2,0),这里是空位,什么都不用做,继续往右扫。当前战舰数 3。
- 21看 (2,1) = 空位 | 战舰数 = 3扫到 (2,1),这里是空位,什么都不用做,继续往右扫。当前战舰数 3。
- 22看 (2,2) = X,检查它的上方与左方 | 战舰数 = 3扫到 (2,2) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
- 23(2,2) 是船头,战舰数 = 4上方是空位,左方是空位,所以 (2,2) 是一艘新战舰的左上角(变绿),战舰数加到 4。
- 24看 (2,3) = 空位 | 战舰数 = 4扫到 (2,3),这里是空位,什么都不用做,继续往右扫。当前战舰数 4。
- 25看 (2,4) = X,检查它的上方与左方 | 战舰数 = 4扫到 (2,4) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
- 26(2,4) 是船身,跳过 | 战舰数 = 4它正上方 (1,4) 也是 X,说明 (2,4) 只是同一艘船的后半截(变灰),不是船头,跳过不计。战舰数仍是 4。
- 27扫描结束,共数到 4 个船头 | 战舰数 = 4整张棋盘扫完。绿色的四格就是四艘战舰各自的左上角,数到 4 个,答案就是 4。灰色的都是被跳过的船身。
⚠️ 容易写错的地方
✗ 错：对每个 X 做 DFS/BFS 整艘船染色
✓ 对：只判「上左是否为 X」数船头
题目保证战舰是直线且互不相邻,船头唯一,不必遍历整艘船,O(1) 空间即可
✗ 错：忘了第 0 行、第 0 列的边界
✓ 对：i 等于 0 时视作上方无 X,j 等于 0 时视作左方无 X
越界访问会出错,边界处天然就是船头候选
✗ 错：只检查上方漏了左方
✓ 对：上方和左方都要为非 X 才算船头
横排战舰的非头格,是靠「左方是 X」被正确跳过的
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:
m, n = len(board), len(board[0])
ans = 0
for i in range(m):
for j in range(n):
if board[i][j] == '.':
continue
if i > 0 and board[i - 1][j] == 'X':
continue
if j > 0 and board[i][j - 1] == 'X':
continue
ans += 1
return ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int countBattleships(vector<vector<char>>& board) {
int m = board.size(), n = board[0].size();
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == '.') {
continue;
}
if (i > 0 && board[i - 1][j] == 'X') {
continue;
}
if (j > 0 && board[i][j - 1] == 'X') {
continue;
}
++ans;
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int countBattleships(char[][] board) {
int m = board.length, n = board[0].length;
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == '.') {
continue;
}
if (i > 0 && board[i - 1][j] == 'X') {
continue;
}
if (j > 0 && board[i][j - 1] == 'X') {
continue;
}
++ans;
}
}
return ans;
}
}复杂度
时间
O(m·n)
每个格子只看一次,外加常数次的上方、左方判断
空间
O(1)
只用一个计数变量,不开额外数组、也不改棋盘
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 棋盘上的战舰 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
如果允许战舰相邻(挨着),这个 O(1) 解还成立吗?+
不成立。本解依赖「战舰互不相邻且是直线」这个前提,船头才唯一。若允许相邻或拐弯,就退化成一般的「岛屿数量」问题,得用并查集或 DFS/BFS 把每个连通块整体染色,空间不再是 O(1)。
面试官要求不修改 board,你的解满足吗?+
满足。我们全程只读 board、只维护一个计数变量,从不写回棋盘,所以原图保持不变,这正是进阶版的考点。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 棋盘上的战舰 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。