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

吴师兄学算法 · 公众号 · · 2020-03-07 12:15

正文

点击上方蓝字设为星标

下面开始今天的学习～

作者 | 程序员浩哥

来源 | 小浩算法

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

话不多说，直接看题。

第319题：开关灯泡

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

示例:

输入: 3

输出: 1

解释:

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

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

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

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

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

（只要一瞪，就会了）

题目分析

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

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

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

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

可以得到如下表格：

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

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

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

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

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

正文

请到「今天看啥」查看全文