一道让我怀疑人生的题
之前经常有人说刚开始刷题时会怀疑人生，觉得每道题都很难，问这正不正常。其实这是正常的，算法本来就是诸多智慧的结晶，何况能拿出来面试的题目都不容易，哪有人万事通，总有我们从未解决过的难题出现，今天我还随机到了一道让我做到怀疑人生的题。
题目是这样的：初始时有 n 个灯泡关闭。第 1 轮，你打开所有的灯泡。第 2 轮，每两个灯泡你关闭一次。第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。对于第 n 轮，你只切换最后一个灯泡的开关。找出 n 轮后有多少个亮着的灯泡。
这题目乍一看，很简单呀，我套一下循环就能做出来，后期再看怎么优化：
public int bulbSwitch(int n) {
int result = 0;
int [] arr = new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = 1;
}
for (int i = 1; i <= arr.length -1; i++) {
int times = i +1;//第多少轮
for (int j = 0; j < arr.length; j++) {
if ((j+1) %times == 0) {
if (arr[j] == 0) {
arr[j]=1;
}else{
arr[j] =0;
}
}
}
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
result ++;
}
}
return result;
}当我兴高采烈地提交的时候，心想着虽然这种暴力解法不够优雅，没有灵魂在里面，但至少算写出来了吧，等会儿我再慢慢优化，没想到直接超时了！
我这下有点懵了，这道题不满足动态规划的结构，也没有我总结的那些套路中关键的条件，还是说有什么隐藏的信息我没有考虑到，抓耳挠腮两个小时也就过去了，再折腾下去我也想不出解法了。默默地点开了题解，题解短到让人看不懂：
int bulbSwitch(int n)
{
return (int)sqrt(n);
}这是个什么意思，求平方根？这代码的每一个单词我都认识，代码的功能我也都明白，可是它是怎么解答这个问题的呢？
我又默默点开了大神们的讨论，他们有条不紊的分析，一个个的数学公式，一个个的“显而易见”让我头皮发麻，觉得受到了降维打击，虽然咱智商比不过大神们，还是硬着头皮逼着自己去理解他们的思路。
首先，我们得知道判断灯泡是开还是关的方法，将包含本轮在内的对第i个灯泡的所有操作次数做和，若为奇数，说明第i个灯泡，经过j轮以后，是亮着的，因为第0轮一定是关闭的。同理，若为偶数，说明第i个灯泡，经过j轮以后，是关闭的。所以我们的问题也就转换成了，经过n轮，第i个灯泡被操作了奇数次还是偶数次？奇数次则最后是亮的，偶数次则最后是关闭的。
那么如何计算操作的次数呢？这看起来是个大活儿啊。我们再来观察一下：第1个灯泡在什么时候会被操作？第1轮。第10个灯泡在什么时候会被操作？第1轮，第2轮，第5轮，第10轮。第20个灯泡在什么时候会被操作？第1轮，第2轮，第4轮，第5轮，第10轮，第20轮。我们可以发现，第 i 个灯泡只有在第 k 轮会被操作，而 k 一定是 i 的因数。并且 n>=k。所以如果一个数的因数的个数为奇数个，那么它最后一定是亮的，否则是关闭的。
这时候我们的问题已经转换成，什么数的因数的个数是奇数个？回答是完全平方数。为什么它的因数就是奇数个呢？设P,A,B 为正整数，如果 P=A*B，则A和B为P的因数。P的因数A和B总是成对出现。也就是说他们总是一起为 P 的因数个数做贡献，为2。但是如果他们相等呢？这个时候他们一起只会为因数的个数贡献 1。
所以正解就是求平方根了。
看到这里相信好多同学也觉得智商被压制了。没关系，想告诉大家的是觉得刷题吃力也不要有压力，都是这么熬过来的，没有什么路是一直轻松的，跟我一样厚着脸皮看题解就好了嘛。学到了总结出经验了就是自己的，这种需要大量经验跟智商的题做不出来也没什么丢人的嘛（自我洗脑中），前路漫漫，大家共勉。