初始時(shí)有 n 個(gè)燈泡，均處于關(guān)閉狀態(tài)。

對某個(gè)燈泡切換開關(guān)意味著：如果燈泡狀態(tài)為關(guān)閉，那該燈泡就會(huì)被開啟；而燈泡狀態(tài)為開啟，那該燈泡就會(huì)被關(guān)閉。

第 1 輪，每個(gè)燈泡切換一次開關(guān)。即打開所有的燈泡。

第 2 輪，每兩個(gè)燈泡切換一次開關(guān)。即每兩個(gè)燈泡關(guān)閉后一個(gè)。

第 3 輪，每三個(gè)燈泡切換一次開關(guān)。即位于第3、6、9···的燈泡切換開關(guān)。

第 i 輪，每 i 個(gè)燈泡切換一次開關(guān)。而第 n 輪，你只切換最后一個(gè)燈泡的開關(guān)。

找出 n 輪后有多少個(gè)亮著的燈泡。

示例 1：

通過上面的圖例，我們可以很清楚地看到，每一輪都會(huì)切換一批燈泡。關(guān)鍵是可能切換到之前已經(jīng)切換過的燈泡，如果我們通過模擬來暴力解決，那么每一輪就要遍歷一次，肯定超時(shí)。

那我們換種思路想想，這道題似乎更像一道有數(shù)學(xué)規(guī)律的題，這種類型在面試中也不少見。

不過我們不一定能馬上找到規(guī)律，那也不要著急，就按部就班：用0表示off, 1表示on，先列出前10個(gè)燈泡的答案，看看其中有什么規(guī)律可循。

n=1：1

n=2：1 0

n=3：1 0 0

n=4：1 0 0 1

n=5：1 0 0 1 0

n=6：1 0 0 1 0 0

n=7：1 0 0 1 0 0 0

n=8：1 0 0 1 0 0 0 0

n=9：1 0 0 1 0 0 0 0 1

n=10: 1 0 0 10 0 0 0 1 0

我們仔細(xì)看看上面的數(shù)據(jù)就會(huì)發(fā)現(xiàn)，最后亮燈的位置都在第1、4、9位上，這些位置恰好都是某個(gè)因子的平方，比如4，就是2的平方，不知道大家還記得不，在數(shù)學(xué)上這種數(shù)字就叫做完全平方數(shù)。

那我們就可以大膽猜測：最后亮燈的位置，都是完全平方數(shù)。那么每多一個(gè)完全平方數(shù)，就多一個(gè)亮的燈泡。

當(dāng)然，這只是一個(gè)猜測，我們可以用暴力法寫一個(gè)程序，把前100個(gè)的情況打印出來，就能看出，是滿足這個(gè)規(guī)律的。

都已經(jīng)驗(yàn)證到100輪了，那么基本就是這個(gè)規(guī)律了。

所以這道題，其實(shí)就是尋找n以內(nèi)有多少個(gè)完全平方數(shù)，具體做法是從數(shù)字1遍歷到數(shù)字n，對每個(gè)數(shù)字判斷是否是完全平方數(shù)，最差也是O(n)可以解決。

牛牛是個(gè)打破砂鍋問到底的人，雖然通過規(guī)律，解決了問題，但是不搞清楚為什么，總是心里癢癢的。

我們從上面的規(guī)律，可以猜測燈泡亮的數(shù)量一定和平方根的特性有關(guān)系的。

我們先看看一些非完全平方數(shù)：

8的因子: 1 2 4 8；

12的因子：1 2 3 4 6 12；

這些因子一定是偶數(shù)個(gè)，為什么呢？

因?yàn)橐粋€(gè)因子，一定是和另一個(gè)因子，配合起來，才能得到這個(gè)數(shù)字。

回到我們的燈泡，比如我們拿n=3的情況來說，第一輪打開了第三輪的燈泡，第三輪就會(huì)給它關(guān)掉，因?yàn)?、3是3的成對因子。

但如果是n=4的情況，1、4雖然也會(huì)成對抵消，但是第二輪的操作卻無法抵消，因?yàn)?的成對因子是2，不會(huì)再重復(fù)出現(xiàn)。

從這里我們就可以看出來，每增加一個(gè)完全平方數(shù)，就會(huì)多一個(gè)不會(huì)被抵消掉的因子出現(xiàn)，所以個(gè)數(shù)也就增加了1。

一般的算法題，O(n)就是性能的極致，但這是一道數(shù)學(xué)規(guī)律題，那我們就得多想想還有沒有更快的辦法。

要找到有多少個(gè)完全平方數(shù)，是否一定要遍歷完1-n？

稍微思考下就可以發(fā)現(xiàn)并不是，拿9舉個(gè)：3是9的完全平方因子，在3以上的數(shù)字一定不能構(gòu)成完全平方因子，因?yàn)殚_平方一定超過最大數(shù)字9了。如此一來，我們只用考慮3之前的。

不難發(fā)現(xiàn)，3之前的1、2是必然滿足完全平方因子的，因?yàn)樗鼈冏銎椒剑欢ㄐ∮?的平方，也就一定在數(shù)據(jù)范圍內(nèi)。

基于上面的分析，我們可以看出，燈泡亮的個(gè)數(shù)，就是n的平方根向下取整個(gè)，代碼就一行：

return (int)Math.sqrt(n)