題目大意
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.
解題思路
題意對于燈的操作：第一次全部點亮圆恤，第二次每兩個反轉(zhuǎn)一次，第三次，每三個翻轉(zhuǎn)一次.......比如第6個燈泡，只會在第一次點亮沮尿，然后第二次滅檐束，然后再在第三次亮，最后在第六次滅轰豆，可見每一次操作會是在6的系數(shù)上面進行雪营，那么問題轉(zhuǎn)化為到燈泡n有多少個系數(shù)弓千，每一個系數(shù)意味著反轉(zhuǎn)一次，所以等價于求系數(shù)個數(shù)的奇偶献起，每一個數(shù)的系數(shù)都是成對的洋访，比如1和n,n/q和q等镣陕，特殊情況，比如3*3=9姻政，這時只有一個系數(shù)呆抑。所以對于完全平方數(shù)，系數(shù)為奇數(shù)個扶歪，對于非完全平方數(shù)理肺，系數(shù)有偶數(shù)個摄闸。
因為初始時滅的善镰，所以若反轉(zhuǎn)奇數(shù)次（亮滅亮滅亮....），則最終是亮的
若反轉(zhuǎn)偶數(shù)次（亮滅亮滅....)年枕，則最終是暗的
題目要求這n個燈泡在n次操作后最終還剩下幾盞燈亮炫欺，通過上面分析，我們可以知道完全平方數(shù)有奇數(shù)個系數(shù)熏兄，因此最終會反轉(zhuǎn)奇數(shù)次品洛，即最后燈會亮;而對于非完全平方數(shù)，其系數(shù)會是偶數(shù)個摩桶，所以最終燈會滅桥状。
因此題目等價于求不小于n的數(shù)中有幾個是完全平方數(shù)，我們可以從1開始算硝清，一直平方辅斟，知道這個數(shù)的平方大于等于n，即 sqrt(n)
代碼如下：
class Solution
{
public:
int bulbSwitch(int n)
{
return sqrt(n);
}
};
