|
695. 岛屿的最大面积
先上最经典的题目，详细思路看这题的官方题解，简单来说的岛屿问题就是遍历二维数组，一般都是从一块陆地开始，进行深度优先或者广度优先搜索，每次上下左右四个方向选其一然后寻找下一块陆地，最后找到一整个岛屿（一片陆地）。
广度优先搜索：
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ans = 0
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
for r in range(nr):
for c in range(nc):
if grid[r][c] == 1:
queue = collections.deque([(r, c)])
grid[r][c] = 2
cur = 1
while queue:
row, col = queue.popleft()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == 1:
cur += 1
queue.append((x, y))
grid[x][y] = 2
ans = max(ans, cur)
return ans
nr是行的长度，nc是列的长度，遍历整个二维数组，如果遇到陆地if grid[r][c] == 1就开始找岛屿。广度优先搜索用的是队列，记录的是二维坐标。grid[r][c] = 2的目的是防止重复遍历。cur是当前岛屿的面积。从一块陆地出发，如果它的四个方向[(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]的下一个坐标（x, y）在范围内并且为陆地的话，就把它加入队列中，同时标记已遍历，cur也加1。ans记录最大的岛屿面积。
深度优先搜索：
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ans = 0
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
for r in range(nr):
for c in range(nc):
if grid[r][c] == 1:
stack = [(r, c)]
grid[r][c] = 2
cur = 1
while stack:
row, col = stack.pop()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == 1:
cur += 1
stack.append((x, y))
grid[x][y] = 2
ans = max(ans, cur)
return ans
深度优先搜索和广度优先搜索基本一样，只是改用栈来实现，每次弹出的位置就是刚刚加入的，即一条路走到底，再往回走（深度）；广度优先则按顺序弹出，一定把最初的位置遍历完之后再遍历新的，如同石头落入水中产生涟漪（广度）。
广度优先与深度优先切换，只需要改一条初始化语句，一个pop函数，几个变量名就行了。
200. 岛屿数量
广度优先搜索：
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
ans = 0
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
queue = collections.deque([(r, c)])
grid[r][c] = "2"
ans += 1
while queue:
row, col = queue.popleft()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
queue.append((x, y))
grid[x][y] = "2"
return ans
深度优先搜索：
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
ans = 0
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
stack = [(r, c)]
grid[r][c] = "2"
ans += 1
while stack:
row, col = stack.pop()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
stack.append((x, y))
grid[x][y] = "2"
return ans
代码框架基本相同，区别：这题的数字用字符来表示，是“1”而不是1；不需要记录当前岛屿的面积，只需要在进入一块新陆地找岛屿时ans加1即可，实际上比上一题简单。
694. 不同岛屿的数量
广度优先搜索：
class Solution:
def numDistinctIslands(self, grid: List[List[int]]) -> int:
ans = set()
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
for r in range(nr):
for c in range(nc):
if grid[r][c] == 1:
queue = collections.deque([(r, c)])
grid[r][c] = 2
path = 'a'
while queue:
row, col = queue.popleft()
nxt = [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]
for i in range(4):
x, y = nxt[i]
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == 1:
path += str(i)
queue.append((x, y))
grid[x][y] = 2
path += 'a'
ans.add(path)
return len(ans)
深度优先搜索：
class Solution:
def numDistinctIslands(self, grid: List[List[int]]) -> int:
ans = set()
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
for r in range(nr):
for c in range(nc):
if grid[r][c] == 1:
stack = [(r, c)]
grid[r][c] = 2
path = 'a'
while stack:
row, col = stack.pop()
nxt = [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]
for i in range(4):
x, y = nxt[i]
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == 1:
path += str(i)
stack.append((x, y))
grid[x][y] = 2
path += 'a'
ans.add(path)
return len(ans)
这题找的是不同岛屿的数量，如何定义岛屿是否相同（模式）呢？题目说明：两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。由于我们找陆地时是从左上向右下找的，所以进入某种形状岛屿的位置是确定的，因此，可以用探索岛屿的路径（方向组合）来表示这个岛屿（类似动作游戏的上下左右组合技能）。
具体方法就是用字符串记录这个方向的组合，同时要避免不同形状的岛屿出现相同路径的情况，在每次遍历时加入标记path += 'a'，保证路径的唯一性。
463. 岛屿的周长
广度优先搜索：
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
ans = 0
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
for r in range(nr):
for c in range(nc):
if grid[r][c] == 1:
stack = [(r, c)]
grid[r][c] = 2
while stack:
row, col = stack.pop()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if (x < 0 or x >= nr or y < 0 or y >= nc) or (0 <= x < nr and 0 <= y < nc and grid[x][y] == 0):
ans += 1
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == 1:
stack.append((x, y))
grid[x][y] = 2
return ans
深度优先搜索：
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
ans = 0
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
for r in range(nr):
for c in range(nc):
if grid[r][c] == 1:
stack = [(r, c)]
grid[r][c] = 2
while stack:
row, col = stack.pop()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if (x < 0 or x >= nr or y < 0 or y >= nc) or (0 <= x < nr and 0 <= y < nc and grid[x][y] == 0):
ans += 1
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == 1:
stack.append((x, y))
grid[x][y] = 2
return ans
本题中只有一个岛屿，注意周长即岛屿的边界，只会出现在陆地与大边界或者海洋的交界处，即指向四个方向的下一个坐标（x，y）有 if (x < 0 or x >= nr or y < 0 or y >= nc) or (0 <= x < nr and 0 <= y < nc and grid[x][y] == 0):越界或者是海洋。
827. 最大人工岛
广度优先搜索：
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
ans = 0
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
area = {}
index = 2
for r in range(nr):
for c in range(nc):
if grid[r][c] == 1:
queue = collections.deque([(r, c)])
grid[r][c] = index
cur = 1
while queue:
row, col = queue.popleft()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == 1:
cur += 1
queue.append((x, y))
grid[x][y] = index
area[index] = cur
index += 1
ans = max(area.values() or [0])
for r in range(nr):
for c in range(nc):
if grid[r][c] == 0:
seen = set()
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] > 1:
seen.add(grid[x][y])
ans = max(ans, 1 + sum(area[i] for i in seen))
return ans
深度优先搜索：
class Solution:
def largestIsland(self, grid: List[List[int]]) -> int:
ans = 0
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
area = {}
index = 2
for r in range(nr):
for c in range(nc):
if grid[r][c] == 1:
stack = [(r, c)]
grid[r][c] = index
cur = 1
while stack:
row, col = stack.pop()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == 1:
cur += 1
stack.append((x, y))
grid[x][y] = index
area[index] = cur
index += 1
ans = max(area.values() or [0])
for r in range(nr):
for c in range(nc):
if grid[r][c] == 0:
seen = set()
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] > 1:
seen.add(grid[x][y])
ans = max(ans, 1 + sum(area[i] for i in seen))
return ans
一道困难题，基本思路是将现有的岛屿遍历一次，用字典标记不同的岛屿和岛屿面积，然后再遍历所有的海洋格子，填充该格子后的大岛屿面积就是这个格子四个方向的任两个岛屿面积之和加1，找出最大值即可。
|