漫画：骚操作系列（灯泡开关的经典面试题）

左手的ㄟ右手 2023-07-12 09:11 58阅读 0赞

点击上方蓝字设为星标![format_png][]

下面开始今天的学习～

![format_png 1][]

作者 | 程序员浩哥

来源 | 小浩算法

![09.png][]

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

话不多说，直接看题。

第319题：开关灯泡

![13.png][]

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

示例:

输入: 3

输出: 1

解释:

初始时, 灯泡状态 \[关闭, 关闭, 关闭\].

第一轮后, 灯泡状态 \[开启, 开启, 开启\].

第二轮后, 灯泡状态 \[开启, 关闭, 开启\].

第三轮后, 灯泡状态 \[开启, 关闭, 关闭\].

你应该返回 1，因为只有一个灯泡还亮着。

![format_png 2][]

（只要一瞪，就会了）

题目分析

![33.png][]

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

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

![format_png 3][]

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

![format_png 4][]

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

![format_png 5][]

可以得到如下表格：

![format_png 6][]

观察一下，这是什么？观察不出来，咱们看看这个：

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

//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);
        }
    };

![format_png 7][]

郑重申明（读我的文章必看）：

*  本系列所有教程都不会用到复杂的语言特性，大家不需要担心没有学过相关语法，使用各语言纯属本人爱好，毕竟我是一个博爱的人，需要雨露均沾。
 *  作为学术文章，虽然哥的风格很风趣，但是所有代码均在leetcode上进行过测试运行。严谨，我是认真的。
 *  最后，请记住，算法思想才是最重要的！

![format_png 8][]

证明

![26.png][]

我不服，没有证明，你说毛线！证明如下：

约数，又称因数。整数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有多少个数是完全平方数**。

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

到这里，基本就很明朗了。

**END**

--------------------

![format_png 9][]

● [答应我，别再if/else走天下了可以吗][if_else]

[● ][Link 1][如何利用寒假的时间来准备2020年的蓝桥杯?][2020]

● [给大家推荐一款软件][Link 2]

● [关于计算机读研的小建议][Link 3]

![format_png 10][]

点“在看”你懂得

![format_png 11][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9pY0hvZXJLTzNOakxHa0wzSmljWnh6WlVsTVBXYU9FVXRpYVZ5RHQ1QU9hSUpOa0xhbHRYT1lSaWFHU2J5aWJneFFzVkxSYXo5SnhmTjZLVkJtU05GYkZlNkx3LzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9ENjdwZWNlaWJlSVJiTkp1c21LYU5tck9QRTdjeDA3bUF3SWVDd1VmenY4T1RCWElOakNOaWJ6aGJJSGhjaWNmMkI5aWFXUUtEZDdkbjZwaWNPaWNZVVpwWUVwZy82NDA?x-oss-process=image/format,png
[09.png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybk8yRU94OEFZWnZXaWI1WnN0TjFZcmZBYTVFZjN4NGZMQ09nZHJJaWJ2dTRuMjlUNHRIWjdpYTJOS0ZRWDJYWUd3T1JIVWx6MjlOeGlheWcvNjQw?x-oss-process=image/format,png
[13.png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybTBhNXYyUXhmQ243aExrNUtCMWNBRlBHNWhLNUs5aWFYaWE4bU1vWEJkWm8wb3Nrb1VtSHRKTDdkZld2aWJmc1U1Nkx3eTB5djRha0E0US82NDA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9jWG9hMDdJOXFyazRpY2dhelNPa21IR1J6ZkkydDdTTUxTWHRwR0I3YTZhVVdtUzVKU3kzeWFpY2pCRmRCUzRMS0lpYk1WRnVrcnNpYXQ0YWliYzBnTFFlaWI5dy82NDA?x-oss-process=image/format,png
[33.png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybk8yRU94OEFZWnZXaWI1WnN0TjFZcmZLV2hWeHdGOHRIVUI3aWNJNGFwR1lHeEl3TW1hSm94UFV1TkJVa3d4aWFpY1ZPaGdxUGJOdU9idVEvNjQw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybk8yRU94OEFZWnZXaWI1WnN0TjFZcmZISThUUnFIbnpjMXBMNGY5S3hHWEhuUE41UXJsM2FYM0NFMjZFaFQ4N25ESUVPeVVVa0hrbncvNjQw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybk8yRU94OEFZWnZXaWI1WnN0TjFZcmZpYVJDQXpISUhBa0ZlMTRDaWJ6ZXNLQTFoVDJhaWFxWUZTZkxCN29KQ2dGbEZRMVFFaGhaeEx3SncvNjQw?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybk8yRU94OEFZWnZXaWI1WnN0TjFZcmZDeEhpYkplUkJ2R0JpYXJBMHBmdTVsalJ0ellXMVJuRVE1WUlFaWNvbU5ldG44RzV5dnhnN0c5TUEvNjQw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybk8yRU94OEFZWnZXaWI1WnN0TjFZcmZJbzdMeE5GbTJSWUJEWUFIbDZrT0FuNUNOeHJRVEFPVGRYTThTaHFYWVo2Y2RDd3R2U2ljTHVnLzY0MA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybk8yRU94OEFZWnZXaWI1WnN0TjFZcmZwQkt4b1F4YTY1aWJkTEd6c1JiQU1QdGYwWlZPRndZM2dGNE5yU2VOVGNpY2F3R0E1ZTNUaWJoVmcvNjQw?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9jWG9hMDdJOXFybk8yRU94OEFZWnZXaWI1WnN0TjFZcmY1RHNrM2E0T0ZPeUljQll1UXJad1QyaWExbVY3Q1ZDVUtmbmNpYTZUbWxNbU9GRFlpYVpnOUdlc1EvNjQw?x-oss-process=image/format,png
[26.png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jWG9hMDdJOXFybk8yRU94OEFZWnZXaWI1WnN0TjFZcmZrSUxZQnVrZHM1UTc4SXRCbTVCeXJOcjdudVJNZG1OVXVuZkpoUWliOWVpYkZvTUNZSGI2aGdxdy82NDA?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9wNldsMkxETVFsSEM2cERYeVFSYVdqbFdSNVBJaHVrSVVHVjFuZks2SDlxdEhab3huWHRWZGV6dG9GZXhrYWV2dWRtWjFNYlY5cVdOWlRYaWFvcEx5b1EvNjQw?x-oss-process=image/format,png
[if_else]: https://blog.csdn.net/kexuanxiu1163/article/details/104140332
[Link 1]: http://mp.weixin.qq.com/s?__biz=Mzg2MzE5MjMxNQ%3D%3D&chksm=ce7ef418f9097d0e01bfe9410a9e40e9f4337c835c87e28332e6a8d8fd8b91b4794164f4c1a1&idx=1&mid=2247491980&scene=21&sn=5ef03c0108a5730fa28e492ec77e22d9#wechat_redirect
[2020]: https://blog.csdn.net/kexuanxiu1163/article/details/104140333
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg%3D%3D&chksm=fa0e6038cd79e92ec7f54e62aaf535c402eed0be07e97d1fdbced663280d2dccdda047ee099c&idx=1&mid=2247487417&scene=21&sn=13d97404f7f5700bb901171e4d9f91e4#wechat_redirect
[Link 3]: https://blog.csdn.net/kexuanxiu1163/article/details/104078939
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9taWFabTA1NHZVaWJ1Mlo1T0d1SXpidXdUaWFpYmlhNWxNU3pJSnhabmliTURvdkhpY0lOZ2N3RWtKZXhlVVZkQTZGMVJNMzlGTVJaajE2U3JwOVFtRURpYXZhZmliQS82NDA?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9jNmdxbWhXaWFmeXI5djFSblJIZGdiRTlWTzljY2pWU0FuOGpxUXBoeUxKbDU5N1JzOUJ6RVViQlIwQUdmSmZ2a3pMOXJ1cWtUbVBBWHIyOXRISWNwRFEvNjQw?x-oss-process=image/format,png