python-leetcode-50.岛屿数量
目录
python-leetcode 50.岛屿数量
题目：
给定一个由“1”陆地和“0”水组成的网格，请计算网格中岛屿的数量
岛屿总是被水包围，并且每座岛屿只能由水平方向和竖直方向上相邻的陆地连接形成
此外，可以假设该网格的四条边均被水包围
方法一：深度优先搜索
将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连
为了求出岛屿的数量，可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。最终岛屿的数量就是我们进行深度优先搜索的次数。
class Solution(object):
def dfs(self,grid,r,c):
grid[r][c]="0" #标记已经访问过的陆地
nr,nc=len(grid),len(grid[0])
#遍历四个方向上下左右
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":
self.dfs(grid,x,y) #递归搜索相邻陆地
def numIslands(self,grid):
nr=len(grid) #获取行数
if nr==0:
return 0
nc=len(grid[0]) #获取列数
num_islands=0 #记录岛屿的数量
for r in range(nr):
for c in range(nc):
if grid[r][c]=="1": #发现新的岛屿
num_islands+=1
self.dfs(grid,r,c) # 用 DFS 访问整个岛屿
return num_islands时间复杂度：O(MN)其中 M 和 N 分别为行数和列数
时间复杂度：O(MN)
方法二：广度优先搜素
为了求出岛屿的数量，我们可以扫描整个二维网格，如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束
最终岛屿的数量就是我们进行广度优先搜索的次数。
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
nr=len(grid) #获取网格的行数
if nr==0: #网格为空，返回0
return 0
nc=len(grid[0]) #获取网格的列数
nums_islands=0 #初始化岛屿数目
for r in range(nr):
for c in range(nc):
if grid[r][c]=="1": #如果当前单元格的值是 "1"，表示发现一个新的岛屿
nums_islands+=1
grid[r][c]=="0" #将当前单元格的值从 "1" 改为 "0"，表示已经访问过
neighbors=deque([(r,c)])#初始化一个双端队列 neighbors，并将当前单元格的坐标 (r, c) 加入队列
while neighbors:
row,col=neighbors.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":
neighbors.append((x,y)) #将符合条件的相邻单元格加入队列
grid[x][y]="0"
return nums_islands时间复杂度：O(MN)
空间复杂度：O(min(M,N))，在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M,N)
源自力扣官方题解