319. Bulb Switcher

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.
There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be.
Suppose n lights are labeled as number[1, 2, 3 ..., n], function of these 4 buttons are given below:
Flip all the lights.
Flip lights with even numbers.
Flip lights with odd numbers.
Flip lights with (3k + 1) numbers, k = 0, 1, 2, …
Example 1:
Input: n = 1, m = 1.
Output: 2
Explanation: Status can be: [on], [off]
Example 2:
Input: n = 2, m = 1.
Output: 3
Explanation: Status can be:[on, off], [off, on], [off, off]
Example 3:
Input: n = 3, m = 1.
Output: 4
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].

[leetcode 319]Bulb Switcher

题目的意思是说，对长度为n的数组，做n次操作，第一次全部打开，第二次将2的倍数反转，第三次将3的倍数反转，…，直到第n次，将n的倍数反转，然后输出开灯的个数。
先给出有点无语的解法，再讲原理，也难怪这么多人点反对，毕竟是medium难度。

1
2
3

public int bulbSwitch(int n) {
    return (int)Math.sqrt(n);
}

我们知道对于一个数而言，其因子都是成对出现的，除了平方外，比如12，其因子是1,12，2,6，3,4，那么对应到上面的数组，下标为12的值就为off，也就是说只有含有平方的因子最后的结果才是on，比如9，其因子是1,9，3,3，那么问题等价为求解n中有多少个含有平方因子的数，可以发现，小于1的为0，大于1小于4的为1，大于4小于9的为2，大于9小于16的为3…，就是对n开平方向下取整，就是上面代码所示。

[leetcode 672] Bulb Switcher II

这道题也和上面一道题一个德行，当然反对的人也特多，还是先给出代码：

public int flipLights(int n, int m) {
    if(m==0) return 1;
    if(n==1) return 2;
    if(n==2&&m==1) return 3;
    if(n==2) return 4;
    if(m==1) return 4;
    if(m==2) return 7;
    if(m>=3) return 8;
    return 8;
}

这是排名第一的解法：
题目中可供选择的4种flip方法分别是：1反转全部灯，2反转奇数的灯，3反转偶数的灯，4反转(3k+1)倍数的灯。
分析可得：

反转全部灯+反转奇数的灯=反转偶数的灯(1+2=3)
反转全部灯+反转偶数的灯=反转奇数的灯(1+3=2)
反转奇数的灯+反转偶数的灯=反转全部灯(2+3=1)

那么问题的结果只可能是这么几种：

全部亮(也就是说执行一个过程偶数次，这里一定可以做到，只要m>2，因为m为奇数的话可以通过上面两次等价一次来将m变为偶数)
1反转全部灯：其他的次数抵消，只剩下1反转全部灯
2反转奇数的灯：其他的次数抵消，只剩下2反转奇数的灯
3反转偶数的灯：其他的次数抵消，只剩下3反转偶数的灯
4反转(3k+1)倍数的灯：其他的次数抵消，只剩下4反转(3k+1)倍数的灯
1+4：因为4无法被抵消，也就是说会剩下4和其他的情况的组合，下同
2+4
3+4

over….