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