There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Example:

Given n = 3.
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].
So you should return 1, because there is only one bulb is on.

我的超时解

递推法，当从n-1到n时，新加上去的一次操作是判断从[1,n]里面n的因子个数，这里记作f(n)好了，即a[n] = a[n-1] + f(n)
因子个数的求法可以精简一下时间，排除0,1,2这三个特殊值后，计算[2, sqrt(n)]里头能整除的数的个数就行了，如果碰到个平方数那个数+1，不然个数就是+2的（i能被n整除，那么它的补数n/i也行）。
这个方法的复杂度嘛，O(n^1.5)吧

class Solution {
public:
    int factors(int n){
        if(n == 0){
            return 0;
        } else if(n == 1){
            return 1;
        } else if(n == 2){
            return 2;
        }
        int count = 2;  //1和自己
        int sqr = (int)(sqrt(n));
        for(int i=2; i <= sqr; i++){
            if(n % i == 0){
                if(i *i == n)
                    count += 1; //平方数
                else
                    count += 2; //一个数和它的补数
            }
        }
        return count;
    }
    int bulbSwitch(int n) {
        if(n < 1){
            return 0;
        }
        int bCount = 0;
        for(int i=1; i<=n; i++){
            if((factors(i)&1) == 1){
                bCount ++;
            }
        }
        return bCount;
    }
};

智商碾压，O(1)解

真正的奥义用一行代码就能解释

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

呵呵哒！这个规律如果多试几次说不定能发现，0,1,1,1,2,2,2,2,2,3这种数列嘛
https://leetcode.com/discuss/91371/share-my-o-1-solution-with-explanation
大概意思是，要在[1,n]里头找哪些灯泡被执行了奇数次操作

•  对于一个非平方数来说（比如12），因为有成对的补数（1vs12; 2vs6），所以总是会按下2的倍数次
• 但是对于一个平方数来说（比如36），因为其中有个数(6)它的补数是自己，所以会按被下奇数次

然后这道题就变成了找[1,n]中间有几个平方数了
OMG…

题目：

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south,x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.
Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.
Example 1:

Given x = [2, 1, 1, 2],
┌───┐
│   │
└───┼──>
    │
Return true (self crossing)

Example 2:

Given x = [1, 2, 3, 4],
┌──────┐
│      │
│
│
└────────────>
Return false (not self crossing)

Example 3:

Given x = [1, 1, 1, 1],
┌───┐
│   │
└───┼>
Return true (self crossing)

思路：

https://leetcode.com/discuss/88054/java-oms-with-explanation
本人愚钝，想不到O(1)空间复杂度的方法，只能看Discussion啦，看完以后发现，遇到问题能够分析出各种情况真是不容易。
把大神的代码总结一下，可以变成下面这张图，图中给出了可能发生self-crossing的所有情况（其他情况都是这些情况的”旋转”版本）：

所以就是遍历所有移动步x[i]，判断之前的情况是否在这三种情况之内，如果有的话，那肯定就有crossing了。其中情况2的意思是，当前的步进x[i]覆盖到了x[i-4]了，其他情况看图应该都好理解的。

代码：

class Solution {
public:
    bool isSelfCrossing(vector<int>& x) {
        int numSz = x.size();
        if(numSz <= 3)
            return false;
        for(int i=3; i<numSz; i++){
            if(x[i]>=x[i-2] && x[i-1]<=x[i-3]) //Cond 1
                return true;
            else if(i>=4 && x[i-1]==x[i-3] && x[i]+x[i-4]>=x[i-2])//Cond 2
                return true;
            else if(i>=5 && x[i-1]<=x[i-3] && x[i-4]<=x[i-2] && x[i]+x[i-4]>=x[i-2] && x[i-1]+x[i-5]>=x[i-3]) //Cond 3
                return true;
        }
        return false;
    }
};