Leetcode 【200、695】
Leetcode 【200、695】
echobingo
发布于 2019-06-16 12:02:44
发布于 2019-06-16 12:02:44
问题描述：【DFS】200. Number of Islands
解题思路：
求二维矩阵中由 '1' 连通的岛屿个数（上下左右有 '1' 视为连通）。很明显用回溯法（DFS）求解。 （1）在递归回溯的函数外部，遍历二维矩阵，如果某个位置为 '1'，则将岛屿个数加 1，并调用回溯函数。 （2）在递归回溯的函数内部，将 '1' 的位置修改为 '0'（防止重复搜索），对上、下、左、右、四个方向进行搜索（注意边界情况），如果某个位置为 '1'，则继续回溯；否则结束。
Python3 实现：
class Solution:
def __init__(self):
self.pos = [[-1,0],[1,0],[0,-1],[0,1]] # 上、下、左、右四个方向的相对位置
def numIslands(self, grid: List[List[str]]) -> int:
ans = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
ans += 1 # 有'1'，则岛屿数加1
self.search(grid, i, j)
return ans
def search(self, grid, i, j):
grid[i][j] = '0' # 将'1'变成'0'，防止重复搜索
for p in self.pos:
if i+p[0] >= 0 and i+p[0] < len(grid) and j+p[1] >= 0 and j+p[1] < len(grid[0]) and grid[i+p[0]][j+p[1]] == '1':
self.search(grid, i+p[0], j+p[1])问题描述：【DFS】695. Max Area of Island
解题思路：
求二维矩阵中由 1 连通的岛屿最大面积（上下左右有 1 视为连通）。很明显用回溯法（DFS）求解。
（1）在递归回溯的函数外部，遍历二维矩阵，如果某个位置为 '1'，则调用回溯函数，更新岛屿的最大面积。
（2）在递归回溯的函数内部，边界情况是如果 grid[i][j] = 0，则返回 0，表示上、下、左、右四个方向都没有 1 了，面积为 0；否则，将 grid[i][j] 由 1 改成 0（防止重复搜索），同时设当前岛屿面积 ans = 1；然后，对上、下、左、右、四个方向进行搜索（注意边界情况），并递归调用该函数累加当前岛屿面积 ans；最后，返回 ans，就是当前连通岛屿的最大面积。
Python3 实现：
class Solution:
def __init__(self):
self.pos = [[-1,0], [1,0], [0,-1], [0,1]] # 上、下、左、右四个方向的相对位置
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
max_area = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
max_area = max(max_area, self.search(grid, i, j))
return max_area
def search(self, grid, i, j):
if grid[i][j] == 0: # 上、下、左、右四个方向都没有 1 了，面积为 0
return 0
ans = 1 # 面积置为 1，因为已经youl
grid[i][j] = 0 # 将'1'变成'0'，防止重复搜索
for p in self.pos:
if 0 <= i+p[0] < len(grid) and 0 <= j+p[1] < len(grid[0]):
ans += self.search(grid, i+p[0], j+p[1]) # 累加面积
return ans # 当前岛屿的最大面积本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.06.15 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录