一亩三分地论坛

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

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

[编程题] 这样的熄灯问题会不会面试?

[复制链接] |试试Instant~ |关注本帖
数字媒体技术 发表于 2014-5-16 21:40:47 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 数字媒体技术 于 2014-5-16 21:45 编辑

2.jpg 3.jpg 4.jpg 5.jpg 6.jpg 7.jpg 360桌面截图20140516213320.jpg



这得老长时间了。。。
4.jpg
ccarter 发表于 2014-5-23 14:31:39 | 显示全部楼层
本帖最后由 ccarter 于 2014-5-23 14:33 编辑

会面试……其实这个与其说是算法题还不如说是脑筋急转弯
比如一个m*n的矩阵
简单的想法就是2^(m*n) 遍历所有可能 但是复杂度太高
我们考虑这样的一个矩阵
11010
00100
01001
........
如果我不动第一排的灯,那我怎么能让第一排的第三个和第五个灯熄灭呢?我只能通过第二排的第三个灯和第五个灯。注意第二排我只能动第三个和第五个灯,动其他灯都会造成第一排的某个灯亮起。
这样矩阵变成了:
11111
01001
01100
........
对第三行做同样的操作:目的是灭掉第二行亮着的灯。只能操作第三行的1、3、4号灯。如此往复直到最后一行,如果最后一行操作完,也全灭了,那你就成功了……
于是问题变成了:第一行应该怎么操作。
这个就好办了,2^n遍历。然后进行刚才介绍的操作看最后一行能否全灭。总复杂度(2^n)*m*n。
那如果n特别大呢?比如5*100000?那当然按列操作了……所以总复杂度是(2^min(m,n))*m*n。如果m和n都特别大呢?面试不会问的,相信我……(其实是我也不知道有没有有效的算法了)

评分

2

查看全部评分

回复 支持 反对

使用道具 举报

RonHe 发表于 2014-5-23 17:19:03 | 显示全部楼层
ccarter 发表于 2014-5-23 14:31
会面试……其实这个与其说是算法题还不如说是脑筋急转弯
比如一个m*n的矩阵
简单的想法就是2^(m*n) 遍历 ...

赞思路。这个面试的时候会要求把代码也写出来么
回复 支持 反对

使用道具 举报

 楼主| 数字媒体技术 发表于 2014-5-23 22:01:29 | 显示全部楼层
ccarter 发表于 2014-5-23 14:31
会面试……其实这个与其说是算法题还不如说是脑筋急转弯
比如一个m*n的矩阵
简单的想法就是2^(m*n) 遍历 ...

大神啊!我写出来要一个多小时。。。。
回复 支持 反对

使用道具 举报

robinho364 发表于 2014-5-23 22:39:48 | 显示全部楼层
这个问题是经典算法题,早就被人研究透了。

复杂度就是mn(2^n),我相信很难有更优的算法了。

事实上也可以用高斯消元法求一组解。
回复 支持 反对

使用道具 举报

 楼主| 数字媒体技术 发表于 2014-5-23 22:43:07 | 显示全部楼层
robinho364 发表于 2014-5-23 22:39
这个问题是经典算法题,早就被人研究透了。

复杂度就是mn(2^n),我相信很难有更优的算法了。

嗯,我刚刚开始算法这类的训练,以前玩开发,用些小工具,活少简单,算法太难,懒得搞~
回复 支持 反对

使用道具 举报

robinho364 发表于 2014-5-23 22:46:21 | 显示全部楼层
哦,对了。

如果你只要求输出一组解的话,高斯消元的确就是高效解法哈。
回复 支持 反对

使用道具 举报

robinho364 发表于 2014-5-23 22:53:41 | 显示全部楼层
数字媒体技术 发表于 2014-5-23 22:43
嗯,我刚刚开始算法这类的训练,以前玩开发,用些小工具,活少简单,算法太难,懒得搞~

Hi,突然发现你看的是pku的课件?

pku讲的倒是很不错!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 04:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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