题解 | #岛屿数量#python实现

岛屿数量

http://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e

  1. BFS方法:借用一个队列 queue,实现BFS。
    判断队列首部节点 (i, j) 是否未越界且为 1:
class Solution:
    def solve(self , grid ):
        # write code here
        def BFS(grid,i,j):
            queue = [[i,j]]
            while queue:#直到队列为空,搜索结束。
                #循环pop 队列首节点,直到整个队列为空,此时已经遍历完此岛屿。
                [i,j] = queue.pop(0)
                # 如果一个位置为 1,则将其加入队列,开始进行广度优先搜索。
                if 0 <= i <len(grid) and 0 <= j <len(grid[0]) and grid[i][j] == '1':
                    #在广度优先搜索的过程中,每个搜索到的 11 都会被重新标记为 0。
                    grid[i][j] = '0'
                    #(删除岛屿节点),并将此节点上下左右节点 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 加入队列; 若不是则跳过此节点; 
                    queue += [[i - 1,j] , [i + 1, j],[i,j - 1],[i, j + 1]]
        count = 0
         #为了求出岛屿的数量,我们可以扫描整个二维网格。
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '0':continue 
                BFS(grid, i, j)
                count += 1
        return count

2、DFS解决:

每走过一个陆地格子,就把格子的值改为 2,这样当我们遇到 2 的时候,就知道这是遍历过的格子了。
0 —— 海洋格子
1 —— 陆地格子(未遍历过)
2 —— 陆地格子(已遍历过)

如果遍历过的陆地取0,这样我们就无法区分「海洋格子」和「已遍历过的陆地格子」了。如果题目更复杂一点,这很容易出 bug。

class Solution:
    def solve(self , grid ):
        # write code here
        def dfs(grid, i, j):
            #判断 base case
            #如果这个格子不是岛屿,直接返回
            if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or grid[i][j] != '1': return
            grid[i][j] = '2'
            #访问上、下、左、右四个相邻结点
            dfs(grid, i + 1, j)
            dfs(grid, i, j + 1)
            dfs(grid, i - 1, j)
            dfs(grid, i, j - 1)
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                #判断坐标 (i, j) 是否在
                if grid[i][j] == '1':
                    dfs(grid, i, j)
                    count += 1
        return count
全部评论

相关推荐

若怜君欢:驾驶证去掉吧,PPT啥的也去掉,本硕课程去掉,导师和研究方向去掉;加入本硕排名(好才写);技能栏加入你会的那些控制算法和滤波算法,这个比你会啥啥啥软件更有用;获奖写上去,奖学金啊,有没有专利啊之类的 电机和硬件这一块,属于传统制造业,制造业实习并不多。多投一些攒攒经验,有实习最好,没有也不需要焦虑(制造业实习其实除了转正,没多大用处) 最后,划重点,等秋招开始后,把你所有社交软件都发一份简历上去,并经常更新,找人内推你!
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务