<>
题目描述
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
我的思路
1. dfs(pos_x,pos_y) 函数通过递归在陆地上移动
2. 通过self.count来记录陆地的数量
class Solution(object): def __init__(self): self.count = 0 def maxAreaOfIsland(self, grid): """ :type grid: List[List[int]] :rtype: int """ def dfs(pos_x,pos_y): if pos_x<0 or pos_x>=len(grid) or pos_y<0 or pos_y>=len(grid[0]): return if idx[pos_x][pos_y] == 1 or grid[pos_x][pos_y]==0: return self.count+=1 idx[pos_x][pos_y] = 1 for mv_ in move_: dfs(pos_x + mv_[0],pos_y + mv_[1]) idx = [[0 for x in range(len(grid[0])) ] for y in range(len(grid)) ] move_ = [(-1,0),(0,-1),(0,1),(1,0)] ans = 0 for x in range(len(grid)): for y in range(len(grid[0])): self.count = 0 dfs(x,y) ans = max(ans,self.count) return ans
小结
1. 构造一个二维数组的方法 ： matrix = [[0 in range(5)] in range(5)]
2. 通过公共变量self.count来保存递归的中间值。（那么如何用return来返回递归的中间值呢？）
3. for mv_ in move_: dfs(pos_x + mv_[0],pos_y + mv_[1])
这一句可以这样写更简洁
for mi, mj in move_:pass
4. 我的思路中用了额外的空间 idx[][]来记录访问的情况，题解的处理方法是把访问过的陆地(1) 改成 海洋(0) 。降低了空间复杂度。
题解
class Solution: def dfs(self, grid, cur_i, cur_j): if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1: return 0 grid[cur_i][cur_j] = 0 ans = 1 for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]: next_i, next_j = cur_i + di, cur_j + dj ans += self.dfs(grid, next_i, next_j) return ans def maxAreaOfIsland(self, grid: List[List[int]]) -> int: ans = 0 for i, l in enumerate(grid): for j, n in enumerate(l): ans = max(self.dfs(grid, i, j), ans) return ans
总结
1. 注意题解中保存递归结果的方法。