灯泡开关
在这个问题中，我们能够首先想到的就是使用暴力模拟。根据模拟可以直接模拟每一步的操作。但是这会发生TLE错误，分析时间复杂度。第一次会进行n次操作，第二次进行n/2次操作，第三次进行n/3次操作......因此总的时间复杂度为
其中C为欧拉常数，为0.5772...，虽然看起来这个只是一个的时间复杂度，但是在10000000的时候就会TLE。
使用代码如下：
public int bulbSwitch(int n){
// 有效区间1到n+1，便于模拟
int[] bulbs = new int[n+1];
for(int i = 1;i <= n;i++){
int j = 1;
int k = j*i;
while (k <= n){
bulbs[k] = bulbs[k]^1; //使用异或操作，安慰自己这样会快一些不会发生TLE
j++;
k = j*i;
}
}
int res = 0;
for(int i = 1;i <= n;i++){
res += bulbs[i]==0 ? 0:1;
}
return res;
}
因此，我们应该像一个方法来解决超时的问题，一般解决思路是空间换时间，另一种是使用数学方法或找规律。
现在我们在n=5的时候进行模拟，我们用1表示开，0表示关，可以看到以下结果：
- 初始状态 0 0 0 0 0
- 第一次时 1 1 1 1 1
- 第二次时 1 0 1 0 1
- 第三次时 1 0 0 0 1
- 第四次时 1 0 0 1 1
- 第五次时 1 0 0 1 0
经过观察，可以发现现在只有1和4是打开的，所以我们从数学的方向来观察该结果，1和4都是平方数，因此是不是平方数的位置就一定是打开的呢？
在这个题目里面，因为灯泡是改变状态，也就是关掉的会被打开，打开的会被关闭。因此所有会被改变偶数次的灯泡会变成关闭状态，被改变奇数次的灯泡会变成打开状态。那我们怎么计算灯泡被改变了偶数次还是奇数次呢？在第n个灯泡，只有一个数字是n的因数的时候才能改变n的位置的灯泡状态。当n为4的时候，他的因数为（1，4），（2，2）。因此在1，2，4的时候会改变位置为n的灯泡的状态，同时改变的也是奇数次，最后结果为灯泡开。因此这个问题变成了前n个数字中有多少个完全平方数。因此可以使用下面的方式来解决：
public int bulbSwitch(int n){
int res = 0;
while (res * res <= n) res++;
return res;
}
//更好的解法
public int bulbSwitch(int n){
return (int)Math.sqrt(n);
}
