一亩三分地论坛

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

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

DropBox OA Grid Illumination

[复制链接] |试试Instant~ |关注本帖
火火火bit 发表于 2016-9-10 11:03:40 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Dropbox - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
给一个数N, 是正方形grid的边长。给一组灯的二维坐标,灯可以照到自己行和自己列以及所在两条对角线的所有点。给定一组(m 长度 array)施工位置的二维坐标,该位置及周围8个格的灯要关掉(施工完恢复)。问还有没有灯能照到当前施工位置,返回m长度array。. Waral 鍗氬鏈夋洿澶氭枃绔,

空间复杂度n平方的话有的test case过不了,还要照顾时间复杂度.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

6

查看全部评分

yrfzh 发表于 2016-9-10 11:50:13 | 显示全部楼层
请问lz网投等了多久发oa啊
回复 支持 反对

使用道具 举报

 楼主| 火火火bit 发表于 2016-9-10 12:23:45 | 显示全部楼层
yrfzh 发表于 2016-9-10 11:50
请问lz网投等了多久发oa啊

一两周吧
回复 支持 反对

使用道具 举报

yrfzh 发表于 2016-9-10 12:27:42 | 显示全部楼层

明白了多谢lz啊
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-9-10 12:59:20 | 显示全部楼层
这样行吗,对每个灯,假设位置是(i, j),把i,j,还有i - j,i + j分别存到4和multimap里面,记录该行,该列,以及两个斜线被多少个灯照亮。施工时候去掉周围八个再查map,施工完再加上。或者用multiset也行。
回复 支持 反对

使用道具 举报

 楼主| 火火火bit 发表于 2016-9-10 13:31:56 | 显示全部楼层
daniel_hl 发表于 2016-9-10 12:59
这样行吗,对每个灯,假设位置是(i, j),把i,j,还有i - j,i + j分别存到4和multimap里面,记录该行,该 ...
.1point3acres缃
如果你只存这样的四个map,怎么检查周围八个呢
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-9-10 13:39:47 | 显示全部楼层
火火火bit 发表于 2016-9-10 13:31
如果你只存这样的四个map,怎么检查周围八个呢

哦,总以为给出了一个matrix,那就再加一个保存点的set?
回复 支持 反对

使用道具 举报

 楼主| 火火火bit 发表于 2016-9-10 13:45:04 | 显示全部楼层
daniel_hl 发表于 2016-9-10 13:39
哦,总以为给出了一个matrix,那就再加一个保存点的set?

可以可以~
回复 支持 反对

使用道具 举报

eros 发表于 2016-9-10 13:46:28 | 显示全部楼层
哇塞 宁神太厉害了
回复 支持 反对

使用道具 举报

 楼主| 火火火bit 发表于 2016-9-10 13:53:38 | 显示全部楼层
eros 发表于 2016-9-10 13:46
哇塞 宁神太厉害了

别逗了。。。
回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-9-11 01:00:04 | 显示全部楼层
请问lz是内推还是海投?
回复 支持 反对

使用道具 举报

superxiaoding 发表于 2016-9-11 01:10:59 | 显示全部楼层
请问楼主什么是施工完恢复?怎么定义“施工完”?
我的想法是直接用一个哈希,然后key是灯的位置,value是灯能照到的所有位置的list,然后遍历施工位置来删哈希,然后遍历value来找是否能照到。
回复 支持 反对

使用道具 举报

iccen8 发表于 2016-9-11 02:22:06 | 显示全部楼层
楼主请问下   m长度的array里的每一个坐标代表施工位置,然后以它为中心的九个点都要关灯吧?如果都关掉了为什么还能有灯能照亮当前的施工位置呢?还是说还有什么条件吗?还是说一次只有一个坐标在施工? 有点不懂
回复 支持 反对

使用道具 举报

nanyang 发表于 2016-9-11 02:38:48 | 显示全部楼层
这道题。。1小时做出来 好难。。。
回复 支持 反对

使用道具 举报

iccen8 发表于 2016-9-11 02:52:54 | 显示全部楼层
nanyang 发表于 2016-9-11 02:38
这道题。。1小时做出来 好难。。。

你明白题目意思吗
回复 支持 反对

使用道具 举报

 楼主| 火火火bit 发表于 2016-9-11 02:54:35 | 显示全部楼层
iccen8 发表于 2016-9-11 02:22
楼主请问下   m长度的array里的每一个坐标代表施工位置,然后以它为中心的九个点都要关灯吧?如果 ...

只是关了最近的九个,远处没施工的灯可以照到
回复 支持 反对

使用道具 举报

iccen8 发表于 2016-9-11 03:01:29 | 显示全部楼层
火火火bit 发表于 2016-9-11 02:54.鏈枃鍘熷垱鑷1point3acres璁哄潧
只是关了最近的九个,远处没施工的灯可以照到

噢噢噢噢明白了。。。谢谢!
回复 支持 反对

使用道具 举报

iccen8 发表于 2016-9-11 03:02:21 | 显示全部楼层
火火火bit 发表于 2016-9-11 02:54. Waral 鍗氬鏈夋洿澶氭枃绔,
只是关了最近的九个,远处没施工的灯可以照到

灯只有一个吧?

补充内容 (2016-9-11 03:13):
噢不可能只有一个。。  写题的时候函数名称和parameter这些都已经限定好了吗?
回复 支持 反对

使用道具 举报

xzqingzi 发表于 2016-9-11 07:38:20 | 显示全部楼层
请问是施工地点时同时施工,还是一个接着一个来的啊?
回复 支持 反对

使用道具 举报

 楼主| 火火火bit 发表于 2016-9-11 07:50:38 | 显示全部楼层
iccen8 发表于 2016-9-11 03:02
灯只有一个吧?.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2016-9-11 03:13):
.鐣欏璁哄潧-涓浜-涓夊垎鍦
限定好了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 15:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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