p319

LeetCode 319 Bulb Switcher 题解

1.题目：

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.

题意：

这是一个开关灯泡的问题，步骤如下：最开始把所有的灯都关掉，然后进行1~n次操作，设当前为第i次操作，
则操作内容为改变所有i的倍数位置上灯泡的状态（开为关，关为开）。
求所有操作完毕开着的灯的个数。

2.解题思路:

这是一道有趣的题目，解法好帅气（帅气脸）。
下面进入分析（正经脸）：首先灯泡个数和操作次数时相等的。n个灯泡n次操作。
每个灯泡需要经历的操作应该是它分解出来的质因数的个数。令n=5,带大家走一遍流程：
灯泡1 1 一次 开
灯泡2 1 2 两次 关
灯泡3 1 3 两次 关
灯泡4 1 2 4 三次 开
灯泡5 1 5 两次 关
可以发现 当它所有可整除数（包括1）为奇数时灯泡最后状态为开
怎样才为奇数呢：原本为1 或者它是完全平方数。
所以对每个数循环判断就好了。开始我是打算这么做的。
等等我们真的需要循环判断么：回头想下。在5之内有1，2的平方数 3的平方为9大于5了，所以在5之内只会有两个灯泡为开
所以只要将5开平方取整得到的数，就是1~5中含有的完全平方数个数（包括1），就是我们最后要求的结果。

3.代码

---

[title] [] [url] [link text]

 

public class Solution {
    public int bulbSwitch(int n) {
        int i=0;
		i=(int) Math.sqrt(n);
		return i;
    }
}

---

4.一些总结：好神奇捂脸逃~