一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1240|回复: 5
收起左侧

问一道面试题

[复制链接] |试试Instant~ |关注本帖
redolent 发表于 2014-10-14 03:53:25 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 实习@Facebook - 校园招聘会 - 技术电面 |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
电面,只做了一道题,就是给了一张图,上面有一些形状大小不规则的黑色区域,剩下的地方为白色,要求输出一共有多少个黑色区域。
我知道应该是用flood fill 算法,可是不确定数目在什么时候update. 希望有人可以指点一下,有兴趣的可以写个伪代码。
Bless us all~
头像被屏蔽
hungryhuang 发表于 2014-10-17 05:17:03 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 1 反对 1

使用道具 举报

tyr034 发表于 2014-10-14 04:23:50 | 显示全部楼层
有什么类似的题嘛?不太懂题目的意思
回复 支持 反对

使用道具 举报

kuyen 发表于 2014-10-14 07:12:26 | 显示全部楼层
tyr034 发表于 2014-10-14 04:23
有什么类似的题嘛?不太懂题目的意思

leetcode "Surrounded Regions" 可能类似
回复 支持 反对

使用道具 举报

迷彩的瓜皮帽 发表于 2014-10-14 08:40:43 | 显示全部楼层
这张图是以什么形式给的?matrix?还是需要自己分析
回复 支持 反对

使用道具 举报

eecsece 发表于 2014-10-14 09:10:32 | 显示全部楼层
这道题类似POJ的lake counting: http://poj.org/problem?id=2386
具体到楼主这道题:双层循环遍历图中每个点(假设图是m*n的矩阵),遇到黑点就开始DFS,过程中把遍历过得所有的黑点都改成白色的点,每次DFS就更新一次count。抛砖引玉写个伪代码:
时间复杂度是O(mn)
. From 1point 3acres bbsfor(int i=0;i<m;i++){
     for(int j=0;j<n;j++){
            if(mat[j]是黑色){
                    DFS(i,j,mat);. from: 1point3acres.com/bbs
                    count++;
            }
     }.鐣欏璁哄潧-涓浜-涓夊垎鍦
}
DFS(int i, int j, matrix mat){
      mat改为白色;
      搜索所有方向,有黑色继续DFS(newi,newj,mat). 鍥磋鎴戜滑@1point 3 acres
}
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 17:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表