题目描述
思路解析动画文字版
记住这把尺子:X 且「上不是 X、左不是 X」就计数。下面每一帧都在套它。
准备 · 全图待扫：蓝色是空位,灰色是还没扫到的战舰格 X。套路:一行一行、从左到右扫,只在 X 的「左上角」处计数。
扫描 · 遇到 X：扫到 (0,0) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船头,计数：上方是棋盘外边界,左方是棋盘外边界,所以 (0,0) 是一艘新战舰的左上角(变绿),战舰数加到 1。
扫描 · 空位：扫到 (0,1),这里是空位,什么都不用做,继续往右扫。当前战舰数 1。
扫描 · 遇到 X：扫到 (0,2) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船头,计数：上方是棋盘外边界,左方是空位,所以 (0,2) 是一艘新战舰的左上角(变绿),战舰数加到 2。
扫描 · 遇到 X：扫到 (0,3) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船身,跳过：它正左方 (0,2) 也是 X,说明 (0,3) 只是同一艘船的后半截(变灰),不是船头,跳过不计。战舰数仍是 2。
扫描 · 空位：扫到 (0,4),这里是空位,什么都不用做,继续往右扫。当前战舰数 2。
扫描 · 遇到 X：扫到 (1,0) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船身,跳过：它正上方 (0,0) 也是 X,说明 (1,0) 只是同一艘船的后半截(变灰),不是船头,跳过不计。战舰数仍是 2。
扫描 · 空位：扫到 (1,1),这里是空位,什么都不用做,继续往右扫。当前战舰数 2。
扫描 · 空位：扫到 (1,2),这里是空位,什么都不用做,继续往右扫。当前战舰数 2。
扫描 · 空位：扫到 (1,3),这里是空位,什么都不用做,继续往右扫。当前战舰数 2。
扫描 · 遇到 X：扫到 (1,4) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船头,计数：上方是空位,左方是空位,所以 (1,4) 是一艘新战舰的左上角(变绿),战舰数加到 3。
扫描 · 空位：扫到 (2,0),这里是空位,什么都不用做,继续往右扫。当前战舰数 3。
扫描 · 空位：扫到 (2,1),这里是空位,什么都不用做,继续往右扫。当前战舰数 3。
扫描 · 遇到 X：扫到 (2,2) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船头,计数：上方是空位,左方是空位,所以 (2,2) 是一艘新战舰的左上角(变绿),战舰数加到 4。
扫描 · 空位：扫到 (2,3),这里是空位,什么都不用做,继续往右扫。当前战舰数 4。
扫描 · 遇到 X：扫到 (2,4) 是 X(紫色)。判定它是不是船头:看它正上方和正左方有没有 X。
裁决 · 船身,跳过：它正上方 (1,4) 也是 X,说明 (2,4) 只是同一艘船的后半截(变灰),不是船头,跳过不计。战舰数仍是 4。
回放 · 四艘战舰：整张棋盘扫完。绿色的四格就是四艘战舰各自的左上角,数到 4 个,答案就是 4。灰色的都是被跳过的船身。
边界先想清:空盘 0、单 X 为 1、横竖混排按船头数。
两个高频追问:前提一旦放宽就回到岛屿数量;本解天然不改原图。
参考代码
from __future__ import annotationsfrom 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 ans复杂度
- 时间：O(m·n)，每个格子只看一次,外加常数次的上方、左方判断
- 空间：O(1)，只用一个计数变量,不开额外数组、也不改棋盘
易错点
面试追问把动画讲成自己的话
追问如果允许战舰相邻(挨着),这个 O(1) 解还成立吗?
追问面试官要求不修改 board,你的解满足吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
回旋镖的数量
LeetCode 447 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题