漫画算法:骚操作系列(灯泡开关的经典面试题)

业余杂谈 herman 407浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:codedq,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:codedq,之前的微信号好友位已满,备注:返现
饿了么大量招人,我内推!Java 方向!薪资不设上限,工作年龄不限!工作地点限魔都,可电话面试!简历,发我微信:codedq
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

今天为大家分享一道关于“电灯泡”的题目。

话不多说,直接看题。

初始时有 n 个灯泡关闭。第 1 轮,你打开所有的灯泡。第 2 轮,每两个灯泡关闭一次。第 3 轮,每三个灯泡切换一次开关(如果关闭则开启,如果开启则关闭)。第 i 轮,每 i 个灯泡切换一次开关。对于第 n 轮,你只切换最后一个灯泡的开关。找出 n 轮后有多少个亮着的灯泡。

www.xttblog.com

示例:

输入: 3
输出: 1

解释:
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭].
你应该返回 1,因为只有一个灯泡还亮着。

这是一道难度评定为困难的题目。但是,其实这并不是一道算法题,而是一个脑筋急转弯。只要我们模拟一下开关灯泡的过程,大家就会瞬间get,一起来分析一下:

我们模拟一下n从1到12的过程。在第一轮,你打开了12个灯泡:

灯泡开关面试题

因为对于大于n的灯泡你是不care的,所以我们用黑框框表示:

灯泡面试题解法

然后我们列出n从1-12的过程中所有的灯泡示意图:

灯泡面试题解法

可以得到如下表格:

枚举灯泡面试题答案

观察一下,这是什么?观察不出来,咱们看看这个:

//go
func main() {
    for n := 1; n <= 12; n++ {
        fmt.Println("n=", n, "\t灯泡数\t", math.Sqrt(float64(n)))
    }
}

上面代码是用 go 实现的,大家也可以使用 Java 来实现。

//print
n= 1     灯泡数  1
n= 2     灯泡数  1.4142135623730951
n= 3     灯泡数  1.7320508075688772
n= 4     灯泡数  2
n= 5     灯泡数  2.23606797749979
n= 6     灯泡数  2.449489742783178
n= 7     灯泡数  2.6457513110645907
n= 8     灯泡数  2.8284271247461903
n= 9     灯泡数  3
n= 10    灯泡数  3.1622776601683795
n= 11    灯泡数  3.3166247903554
n= 12    灯泡数  3.4641016151377544

没错,只要我们对n进行开方,就可以得到最终的灯泡数。根据分析,得出代码:

//给一个c++版本的
class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};
灯泡面试题算法耗时统计

也可能有人对上面的结果表示不服,没有证明,你说毛线!证明如下:

约数,又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数,我们就说a能被b整除,或b能整除a。a称为b的倍数,b称为a的约数。

从我们观察可以发现,如果一个灯泡有奇数个约数,那么最后这个灯泡一定会亮着。

什么,你问我奇数是什么?奇数(odd)指不能被2整除的整数 ,数学表达形式为:2k+1, 奇数可以分为正奇数和负奇数。

所以其实我们是求,从1-n有多少个数的约数有奇数个。而有奇数个约数的数一定是完全平方数。这是因为,对于数n,如果m是它的约数,则n/m也是它的约数,若m≠n/m,则它的约数是以m、n/m的形式成对出现的。而m=n/m成立且n/m是正整数时,n是完全平方数,而它有奇数个约数。

我们再次转化问题,求1-n有多少个数是完全平方数。

什么,你又不知道什么是完全平方数了?完全平方指用一个整数乘以自己例如11,22,3*3等,依此类推。若一个数能表示成某个整数的平方的形式,则称这个数为完全平方数。

到这里,基本就很明朗了。剩下的,我想不需要再说了吧!

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号1:xmtxtt(5000人已满),微信号2:xttblog(5000人已满),微信号3:codedq(超3800)。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » 漫画算法:骚操作系列(灯泡开关的经典面试题)