题目一：leetcode200.岛屿数量

1.题目描述

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入: 11110 11010 11000 00000

输出: 1 示例 2:

输入: 11000 11000 00100 00011

输出: 3

2.解题思路

遇到1，则把1的上下左右都感染成2，res+=1，最后返回res

时间复杂度 ：外层O（n*m），内层递归中，一个点最多被调用五次（上、下、左、右、自己），是个常数级别，因此总的时间复杂度：O（n*m）

3.代码实现

class Solution(object): def infect(self, grid,m,n,i,j): if (i<0) or (j<0) or (i>m-1) or (j>n-1) or (grid[i][j]!='1'): return else: grid[i][j]='2' self.infect(grid,m,n,i-1,j) self.infect(grid,m,n,i+1,j) self.infect(grid,m,n,i,j-1) self.infect(grid,m,n,i,j+1) def numIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ res=0 if not grid or not grid[0]: return res m=len(grid) n=len(grid[0]) for i in range(m): for j in range(n): if grid[i][j]=='1': res+=1 self.infect(grid,m,n,i,j) return res

题目二：leetcode695.岛屿的最大面积

1.题目描述

给定一个包含了一些 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。

2.解题思路

和上一题方法一样，只不过在递归函数中要加入一个变量来计算当前连通岛屿中岛屿的个数。最后取所有可能的最大值。

3.代码实现

class Solution(object): def infect(self, grid,m,n,i,j,res): if (i<0) or (j<0) or (i>m-1) or (j>n-1) or (grid[i][j]!=1): return else: grid[i][j]='2' res[0] += 1 self.infect(grid,m,n,i-1,j,res) self.infect(grid,m,n,i+1,j,res) self.infect(grid,m,n,i,j-1,res) self.infect(grid,m,n,i,j+1,res) def maxAreaOfIsland(self, grid): """ :type grid: List[List[int]] :rtype: int """ if not grid or not grid[0]: return 0 m=len(grid) n=len(grid[0]) ans = 0 for i in range(m): for j in range(n): res = [0] if grid[i][j]==1: self.infect(grid,m,n,i,j,res) ans = max(ans,res[0]) return ans