来美帝后第一次写题解，终于刷到medium题了，不过发现medium题里有好多水DP和遍历二叉树之类的题，这道题感觉挺好玩的，做的中间还煮了锅方便面，开心~

题意：有n个灯泡，有n次操作：第一次，把所有灯都点亮

　　　　　　　　　　　　　　 第二次，把偶数的灯都关了

　　　　　　　　　　　　　　第三次到第n次：把次数的倍数倍数的灯都进行相反操作（开变关，关变开）问n次操作执行完还剩多少盏灯？

思路一：medium题也可能是水题吧，模拟一发试试，于是根据题意写一个O（n^2）的程序，先遍历每个灯，再遍历每个灯经历的操作，敲完过样例，完美！不过在一个99999的数据上TLE了

思路二:看来最大数据估计是99999了，那O（n）的程序应该可以过，于是观察操作。发现：操作具有对称关系。比如说第20这个灯，会经历从3到20次操作，其中对这盏灯有效的操作都是他的约数，即

4；5；20,于是可以发现，4*5 = 20；也就是一个非本身的约数m，都可以找到另一个约数 n / m，来对他进行抵消，使得这次操作无效，那么，真正对这个灯的状态有改变的只有n本身，以及

根号n（因为只有一个），按照这个思路写了一个O(n)的程序，判断每个数是不是完全平方数。这里后来遇到几个特例：

　　　　1）偶数，因为偶数的一个约数是2，但是我们操作是从3开始的，所以与2相对的那个操作不会抵消。

　　　　2）与2相对应的约数小于3，其实主要就是4这个数，要进行一个特判。

写好之后又开开心心地交了，跑了一会挂在了99999999这个数据上，卧槽！？

思路三：T了之后就去跟室友煮面了，吃饱之后回来再想解决方法，这里我主要是借助韦恩图来对情况进行归类。首先初始状态可以分为奇数位置和偶数位置两种可能。奇数位置都是亮（记为T），偶数位置

都是灭的（记为F），先考虑奇数位置：由于每个数都会经历本身，所以T先变为F;再考虑两个特例：是完全平方数以及是偶数。由于是奇数位置，所以不存在偶数的情况，那么特例只有完全平方数，会把

F再变为T，得到结论：在奇数位置内，只有完全平方数项的灯才是亮的，其余都是灭的。偶数部分可以顺着这个思路进行整理，得到的结论是一样的：即操作结束之后，只有完全平方项的灯才是亮的，其余

都是灭的。于是一个sqrt函数就得到了最终答案。这个推导过程用韦恩图来表示非常的清晰。

AC代码：（代码挺简单的）

 1 class Solution {
 2 public:
 3     int bulbSwitch(int n) {
 4         if(n == 1 || n == 0)
 5             return n;
 6         else if(n == 2)
 7             return n / 2;
 8         else{
 9             int ans = (int) sqrt(n);
10             return ans;
11         }
12     }
13 };

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

微信扫一扫
关注该公众号