LeetCode--200.Number of Islands(孤岛个数)Python_leetcode岛屿数量python-程序员宅基地

技术标签： LeetCode

题目：

给定一个2维网格图，其中“1”(陆地)和“0”(水)，计算岛屿的数量。岛屿被水包围，通过水平或垂直连接相邻的陆地形成。你可以假设网格的四边都被水包围着。例子如下图所示

解题思路：

从最左上角开始遍历这个网格图，当遍历到该点值为1的时候，将其更新为0，并以该点进行扩展，扩展方式为上下左右四个方向，扩展到的陆地（即值为1）将其值更新为0，直到不能扩展。再继续遍历下一个值为1点的，更新为0后进行扩展。

代码（Python）：

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        output = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=='1':
                    output += 1
                    self.dfs(grid,i,j)
        return output
    
    def dfs(self,grid,i,j):
        grid[i][j] = '0'
        if i-1>=0 and grid[i-1][j]=='1':
            self.dfs(grid,i-1,j)
        if i+1<len(grid) and grid[i+1][j]=='1':
            self.dfs(grid,i+1,j)
        if j-1>=0 and grid[i][j-1]=='1':
            self.dfs(grid,i,j-1)
        if j+1<len(grid[0]) and grid[i][j+1]=='1':
            self.dfs(grid,i,j+1)

本文链接：https://blog.csdn.net/xiaoxiaoley/article/details/82557634

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

【.Net码农】RDLC报表显示外部图片方法_rdlc 外部图片不清晰-程序员宅基地

文章浏览阅读1.8k次。工作时的总结,希望以后不要再犯!!! 在Windows窗体设计上进行必要条件：(需要使用下面的控件)代码设置：this.reportViewer1.LocalReport.EnableExternalImages = true; // RDLC报表显示本地图片必须设置(默认是关闭) 下面方法需要在设计RDLC上进行**********_rdlc 外部图片不清晰

隐马尔科夫模型（HMM）学习笔记二-程序员宅基地

文章浏览阅读459次。　　这里接着学习笔记一中的问题2，说实话问题2中的Baum-Welch算法编程时矩阵转换有点烧脑，开始编写一直不对（编程还不熟练hh），后面在纸上仔细推了一遍，由特例慢慢改写才运行成功，所以代码里面好多处都有print。　　笔记一中对于问题1（概率计算问题）采用了前向或后向算法，根据前向和后向算法可以得到一些后面要用到的概率与期望值。一、问题2..._π的导数为什么是1

动态给select下拉框添加option_ie动态添加option-程序员宅基地

文章浏览阅读2w次，点赞6次，收藏17次。方法很多：1.JQuery的方法：///先定义一个数组 var data=new Array();///然后.............给数组data赋值 ............///最后把数组的值写入下拉框for(var j=0;j<data.length;j++) $("#selectId").append("<option val..._ie动态添加option

在ubuntu 11.10 加入fb0 并且正常显示图片_ubuntu使用dev/fb-程序员宅基地

文章浏览阅读2.4k次。我用的系统是虚拟机下的ubuntu 11.10最近在做视频方面的研究，初步采用 framebuffe用来显示采集视频，可是查看时却不存在/dev/fb0在网上得到建议是用下面命令添加就可以，即：mknod /dev/fb0 c 29 0该命令执行后，肯定能够在/dev目录下产生fb0节点，可是这样产生的fb0却是不能够用的。所以好几天我尝试找出应该怎么解决，今天看了下面一个文章，经_ubuntu使用dev/fb

mybatis插入date类型_Java使用Mybatis插入Mysql数据库时间跟取出的时间不一致的解决办法...-程序员宅基地

文章浏览阅读1.8k次。通过下面的步骤，就可以完全解决java插入mysql数据库时间以后再取出的的时间跟插入时的时间不一致，或者丢失了毫秒数的问题，或者插入数据库前的时间转为Long的值跟取出的时间转为的long值不一致的问题。。1.类的属性类型首先需要注意的是，Java中的实体类中的这个时间属性的类型需要是Timestamp类型，例如：privateTimestampcreateTime;//创建时间除此之..._java mybitspus 日期格式插入数据库变动了

jep自定义函数_jep 自定义-程序员宅基地

文章浏览阅读2.8k次。jep自定义函数jep自定义函数使用,下面是jep自定义函数计算年利率一个demojep在使用函数时,需要把相应的函数加入jep幂函数Jep jep = new Jep();jep.addFunction(“pow”, new Power());自定义函数也是如此1.定义年利率计算类AnnualInterestRate,由于需要多个参数,故继承NaryFunction类,该类根据个人..._jep 自定义

随便推点

oracle中null值问题以及滤空函数（nvl）_oracle select null-程序员宅基地

文章浏览阅读3k次。1、select语句中的null问题：（1）包含null的表示式都为null（2）null永远不等于null（3）如果集合中含有null,不能使用not in,但可以使用innot in相当于<>all举例解释：a not in(3,4,null)相当于a!=3 and a!=4 and a!=null，a!=null永远为false（4）null值在order..._oracle select null

基于windows文件共享服务器,windows文件共享服务器-程序员宅基地

文章浏览阅读644次。windows文件共享服务器内容精选换一换文件系统创建完成后，用户需在客户端挂载文件共享，在本地共享目录和CSG的文件共享建立映射，通过操作本地的目录实现对CSG共享目录的操作，实现数据实时上云管理。本章节主要介绍在Windows Server 2008客户端挂载NFS文件共享的操作指导。不同操作系统安装NFS客户端的命令不同，已明确服务器操作系统类型为Windows。已在CSG华为云帮助中心，..._windows共享服务器

图网络embeding transE及node2vec方法_node2vec计算知识图谱三元组-程序员宅基地

文章浏览阅读1k次。1、 transE 表示学习知识图谱中的事实是用三元组 (h,l,t)(h,l,t)(h,l,t) 表示的，那么如何用低维稠密向量来表示它们，才能得到这种依赖关系呢？transE算法的思想非常简单，它受word2vec平移不变性的启发，希望h+l≈t参考：https://github.com/Anery/transEimport codecsimport randomimport mathimport numpy as npimport copyimport timeentity2id _node2vec计算知识图谱三元组