leetcode_200岛屿数量
通过遍历岛屿中为1的点,然后进行bfs,将"1"变成"0",岛屿填成海洋.进行计数.
空间复杂度：\O(min(M,N))，在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M,N)。斜对角线
注意在面试中需要问面试官可以直接在二维数组上进行更改吗?如果不可以自己另开一个数组.
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
queue=collections.deque()
count=0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]=="1":
grid[i][j]="0"
queue.append((i,j))
while queue:
x,y=queue.popleft()
for di in [(1,0),(0,1),(-1,0),(0,-1)]:
if 0<=x+di[0]<len(grid) and 0<=y+di[1]<len(grid[0]) and grid[x+di[0]][y+di[1]]!="0":
queue.append((x+di[0],y+di[1]))
grid[x+di[0]][y+di[1]]="0"
count+=1
return count使用栈进行递归版,与队列进行bfs非常相似.
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
stack=[]
count=0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]=="1":
stack.append((i,j))
while stack:
x,y=stack.pop()
for di in [(1,0),(0,1),(-1,0),(0,-1)]:
if 0<=x+di[0]<len(grid) and 0<=y+di[1]<len(grid[0]) and grid[x+di[0]][y+di[1]]!="0":
stack.append((x+di[0],y+di[1]))
grid[x+di[0]][y+di[1]]="0"
count+=1
return count使用dfs函数进行解决
from collections import deque
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(x,y):
for di in [(1,0),(0,1),(-1,0),(0,-1)]:
if 0<=x+di[0]<len(grid) and 0<=y+di[1]<len(grid[0]) and grid[x+di[0]][y+di[1]]!="0":
grid[x+di[0]][y+di[1]]="0"
dfs(x+di[0],y+di[1])
count=0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j]=="1":
dfs(i,j)
count+=1
return count
