python3 头条笔试部门合并问题

这是一道今日头条2018年校招第三次笔试的题目,原题如下

通用的思路都是DFS和BFS,我这里想说的并不是这两个,而是图像处理中的连通域分析思想

简单画了个示意图,步骤如下:

1 分析取得每一行的连通区域,图中红色表示部分

2,初始化连通域总数SUM=0

3,开始向下检测,SUM = SUM + 该行连通域的个数

4,逐个检测该行中的连通域是否与上一行中每一个连通域有交集,有则SUM = SUM -1,没有则集训

5, 循环3,4步直到结束,输出SUM

代码如下:

 


m = [
    [1,0,0,0,0],
    [0,0,1,1,0],
    [0,1,0,0,0],
    [0,0,1,0,0],
    [1,0,1,0,0],
]
l = len(m)

lists = []

for i in range(l):
    tmp_line = []
    tmp = [0,0]
    flag = False
    for j in range(l):
        if m[i][j] == 1:
            if flag is True:
                tmp[1] = j
            else:
                tmp[0] = j
                flag = True
        else:
            if flag is True:
                tmp[1] = j
                tmp_line.append(tmp)
                tmp = [0,0]
                flag = False

    if flag is True:
        tmp[1] = l-1
        tmp_line.append(tmp)
        flag = False
    lists.append(tmp_line)

print(lists)

sum1 = len(lists[0])
for i in range(1,l):
    queue = lists[i-1]
    sum1 += len(lists[i])
    for ls in lists[i]:
        if len(ls) == 0:
            continue
        if len(queue) == 0:
            continue
        if i != l - 2:
            depend_size = 0
        a = ls[0]
        b = ls[1]
        for k in queue:
            # 独立单元
            if k[0] >= b or k[1]<=a:
                continue
            else:
                sum1 -=1

print(sum1)

运行结果如下:

[[[0, 1]], [[2, 4]], [[1, 2]], [[2, 3]], [[0, 1], [2, 3]]]
5

共有5个连通域

这题还可以变化为8连通,坐标位置的8个方向都视为连通,有兴趣可以考虑下

版权声明:本文为liangxun0712原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/liangxun0712/article/details/82558532

智能推荐

Python学习练习6----列表、字典的运用2

range 用法参见http://blog.csdn.net/chiclewu/article/details/50592368 直接在 在线编程工具中练习: https://www.tutorialspoint.com/execute_python_online.php 代码如下,增加range、列表的len()、字典的items()函数,for 函数也有了新变化 练习2: 2的运行结果,注意p...

PoolThreadCache

缓存构成   PoolThreadCache的缓存由三部分构成:tiny、small 和 normal。 tiny   缓存数据大小区间为[16B, 496B]数据,数组长度为32,根据数据大小计算索引的办法:数据大小除以16,如下代码所示: small   缓存数据大小区间为[512B, 4KB]数据,数组长度为4,根据数据大小计算索引的办法:数据大小除以512,然后log2得到指数,如下代码所...

Intellij IDEA 搭建Spring Boot项目(一)

Intellij IDEA 搭建Spring Boot项目 标签(空格分隔): SpringBoot JAVA后台 第一步 选择File –> New –> Project –>Spring Initialer –> 点击Next  第二步 自己修改 Group 和 Artif...

CentOS学习之路1-wget下载安装配置

参考1: https://blog.csdn.net/zhaoyanjun6/article/details/79108129 参考2: http://www.souvc.com/?p=1569 CentOS学习之路1-wget下载安装配置 1.wget的安装与基本使用 安装wget yum 安装软件 默认安装保存在/var/cache/yum ,用于所有用户使用。 帮助命令 基本用法 例子:下载...

深入浅出Spring的IOC容器,对Spring的IOC容器源码进行深入理解

文章目录 DispatcherServlet整体继承图 入口:DispatcherServlet.init() HttpServletBean.init() FrameworkServlet.initServletBean() 首先大家,去看Spring的源码入口,第一个就是DispatcherServlet DispatcherServlet整体继承图 入口:DispatcherServlet....

猜你喜欢

laravel框架的课堂知识点概总

1. MVC 1.1 概念理解 MVC全名是Model View Controller,是模型(model)-视图(view)-控制器(controller)的缩写,一种软件设计典范,用一种业务逻辑、数据、界面显示分离的方法组织代码,将业务逻辑聚集到一个部件里面,在改进和个性化定制界面及用户交互的同时,不需要重新编写业务逻辑 MVC 是一种使用 MVC(Model View Controller ...

Unity人物角色动画系统学习总结

使用动画系统控制人物行走、转向、翻墙、滑行、拾取木头 混合树用来混合多个动画 MatchTarget用来匹配翻墙贴合墙上的某一点,人物以此为支点翻墙跳跃 IK动画类似于MatchTarget,控制两只手上的两个点来指定手的旋转和位置,使得拾取木头时更逼真 创建AnimatorController: 首先创建一个混合树,然后双击 可以看到该混合树有五种状态机,分别是Idle、WalkForward、...

Composer 安装 ThinkPHP6 问题

Composer 安装 ThinkPHP6 问题 先说说问题 一.运行环境要求 二.配置 参考: ThinkPHP6.0完全开发手册 先说说问题 执行ThinkPHP6的安装命令 遇到问题汇总如下: 看提示是要更新版本,执行命令更新。 更新之后,再次安装ThinkPHP,之后遇到如下问题。 尝试了很多方法,依然不能解决。其中包括使用https://packagist.phpcomposer.com...

Spring Boot 整合JDBC

今天主要讲解一下SpringBoot如何整合JDBC,没啥理论好说的,直接上代码,看项目整体结构 看一下对应的pom.xml 定义User.java 定义数据源配置,这里使用druid,所以需要写一个配置类 上面指定druid的属性配置,和用户登录的账号信息以及对应的过滤规则: 下面定义数据访问接口和对应的实现: 数据访问层很简单,直接注入JdbcTemplate模板即可,下面再看对应的servi...

html鼠标悬停显示样式

1.显示小手:     在style中添加cursor:pointer 实现鼠标悬停变成小手样式     实例:         其他参数: cursor语法: cursor : auto | crosshair | default | hand | move | help | wait | tex...