:-: 16.2 [灯泡开关](https://leetcode-cn.com/problems/bulb-switcher) ***** **题干：** 初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。 示例: ~~~ 输入: 3 输出: 1 解释: 初始时, 灯泡状态 [关闭, 关闭, 关闭]. 第一轮后, 灯泡状态 [开启, 开启, 开启]. 第二轮后, 灯泡状态 [开启, 关闭, 开启]. 第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 你应该返回 1，因为只有一个灯泡还亮着。 ~~~ **题目分析：** 这种明显是一种找规律的题目，最简单的做法就是按照题意强行来解，也是最容易超时的一种方法，可以试试，超出时间限制的话就不要强求了。我们先根据题意来分析一下，求的是*n* 轮后有多少个亮着的灯泡。我们应该明确一个事情，灯泡一开始都是关闭的，如果某一个灯泡最后是亮的，则**肯定是被按了奇数次开关**。我们找一下被按了奇数次开关都是第几个灯泡（按照第一种思路来写个程序，找出来就行）。 我们假设只有20个灯泡，根据我们写的程序的输出为\[true, false, false, true, false, false, false, false, true, false, false, false, false, false, false, true, false, false, false, false\]，发现1，4，9，16位置的为true，它们的共同特性就是**完全平方数**（这里已经可以着手解题了，统计完全平方的个数呗），这就让我们纳闷了？为什么只有位置是完全平方数的灯泡被按了奇数次？ 我们假设只有6个灯泡，根据我们的程序输出一下中间过程，看看能否发现什么规律？ 1：true true true true true true 2：true false true false true false 3：true false false false true true 4：true false false true true true 5：true false false true false true 6：true false false true false false 第一个灯泡一直没有变过，看第四个灯泡，在第1轮，第2轮，第4轮被按了；看第六个灯泡第1轮会被按，第2轮，第3轮，第6轮都会被按。我们由此可以分析看出 4 = 1 \* 4 = 2 \* 2，6 = 1 \* 6 = 2 \* 3。由此我们看出来原来是看因子个数啊，但是一般因子都是成双结对，只有完全平方数是某个整数的平方的形式，此时的因子是一个，比如4 = 2 \* 2。 于是经过这么多步骤，我们的问题就变成了1~n中有几个完全平方数，我们可以根据[判断一个数是否为平方数](https://blog.csdn.net/puqutogether/article/details/42098609)的方法统计完全平方数个数，但是还是太复杂了些。其实我们求1~n中完全平方数的个数，只需要将n开方向下取整即可。 **新手有可能遇到的解题思路陷阱：** 沉迷于暴力法优化不可自拔，对因子不够熟悉。 **解题思路分析以及代码实现：** 第一种思路：暴力法。 第一种思路代码： ~~~ public static int bulbSwitch(int n) { boolean[] bulb = new boolean[n]; int i = 0; while (i <= n) { for (int j = i; j < n; j += (i + 1)) { bulb[j] = !bulb[j]; } i++; } n = 0; for (boolean sign : bulb) { if (sign) n++; } return n; } ~~~ **复杂度分析：** 时间复杂度：O(n^2)。 空间复杂度：O(n)。 第二种思路：求完全平方数个数。 第二种思路代码： ~~~ public static int bulbSwitch(int n) { return (int) Math.sqrt(n); } ~~~ **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**