题目描述
思路解析动画文字版
核心就一句话:一块陆地起步算 4 条边,它每挨着一块陆地就少一条边。逐格扫、逐边数,加起来就是周长。
初始网格 5×5:这张 5×5 网格里,深色是陆地(1)、浅色是水(0)。我们从左上角一行一行往下扫,周长从 0 开始累加。
第 1 块陆地 (0,1) · 看四条边:扫到第 1 块陆地 (0,1)。挨个看它四周:上出界、下陆、左水、右陆。其中露在外面(挨水或出界)的有 2 条边。
第 1 块陆地 (0,1) · 计入周长:把这 2 条外露边加进周长,累计变成 2。这块陆地数完,标记为已处理(变灰),继续扫下一块。
第 2 块陆地 (0,2) · 看四条边:扫到第 2 块陆地 (0,2)。挨个看它四周:上出界、下陆、左陆、右水。其中露在外面(挨水或出界)的有 2 条边。
第 2 块陆地 (0,2) · 计入周长:把这 2 条外露边加进周长,累计变成 4。这块陆地数完,标记为已处理(变灰),继续扫下一块。
第 3 块陆地 (1,1) · 看四条边:扫到第 3 块陆地 (1,1)。挨个看它四周:上陆、下水、左水、右陆。其中露在外面(挨水或出界)的有 2 条边。
第 3 块陆地 (1,1) · 计入周长:把这 2 条外露边加进周长,累计变成 6。这块陆地数完,标记为已处理(变灰),继续扫下一块。
第 4 块陆地 (1,2) · 看四条边:扫到第 4 块陆地 (1,2)。挨个看它四周:上陆、下陆、左陆、右陆。其中露在外面(挨水或出界)的有 0 条边。
第 4 块陆地 (1,2) · 计入周长:把这 0 条外露边加进周长,累计变成 6。这块陆地数完,标记为已处理(变灰),继续扫下一块。
第 5 块陆地 (1,3) · 看四条边:扫到第 5 块陆地 (1,3)。挨个看它四周:上水、下水、左陆、右水。其中露在外面(挨水或出界)的有 3 条边。
第 5 块陆地 (1,3) · 计入周长:把这 3 条外露边加进周长,累计变成 9。这块陆地数完,标记为已处理(变灰),继续扫下一块。
第 6 块陆地 (2,2) · 看四条边:扫到第 6 块陆地 (2,2)。挨个看它四周:上陆、下陆、左水、右水。其中露在外面(挨水或出界)的有 2 条边。
第 6 块陆地 (2,2) · 计入周长:把这 2 条外露边加进周长,累计变成 11。这块陆地数完,标记为已处理(变灰),继续扫下一块。
第 7 块陆地 (3,1) · 看四条边:扫到第 7 块陆地 (3,1)。挨个看它四周:上水、下陆、左水、右陆。其中露在外面(挨水或出界)的有 2 条边。
第 7 块陆地 (3,1) · 计入周长:把这 2 条外露边加进周长,累计变成 13。这块陆地数完,标记为已处理(变灰),继续扫下一块。
第 8 块陆地 (3,2) · 看四条边:扫到第 8 块陆地 (3,2)。挨个看它四周:上陆、下水、左陆、右水。其中露在外面(挨水或出界)的有 2 条边。
第 8 块陆地 (3,2) · 计入周长:把这 2 条外露边加进周长,累计变成 15。这块陆地数完,标记为已处理(变灰),继续扫下一块。
第 9 块陆地 (4,1) · 看四条边:扫到第 9 块陆地 (4,1)。挨个看它四周:上陆、下出界、左水、右水。其中露在外面(挨水或出界)的有 3 条边。
第 9 块陆地 (4,1) · 计入周长:把这 3 条外露边加进周长,累计变成 18。这块陆地数完,标记为已处理(变灰),继续扫下一块。
扫描结束:每块陆地的外露边都数完了,全部加起来周长 = 18,这就是答案。
三个高频追问:贡献公式的来历、只看上左为何能不重复、以及有湖时的情况。
参考代码
def islandPerimeter(grid): R, C = len(grid), len(grid[0]) per = 0 for i in range(R): for j in range(C): if grid[i][j] == 1: # 只看陆地 per += 4 # 起步算 4 条边 if i > 0 and grid[i-1][j] == 1: # 上邻是陆地 per -= 2 # 共享边, 两块各减 1 if j > 0 and grid[i][j-1] == 1: # 左邻是陆地 per -= 2 return per复杂度
- 时间:O(R×C),把网格每个格子扫一遍,每格只看常数条边
- 空间:O(1),只用一个计数器累加周长,不开额外网格
易错点
面试追问把动画讲成自己的话
追问为什么一块陆地的贡献是「4 减相邻陆地个数」?
追问代码里为什么只检查上邻和左邻,还减 2?
追问如果岛里有湖(被陆地围住的水),这个解法还对吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
托普利茨矩阵
LeetCode 766 · 简单 · 沿着 矩阵套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题