初始時有 n 個燈泡，均處于關閉狀態。

對某個燈泡切換開關意味著：如果燈泡狀態為關閉，那該燈泡就會被開啟；而燈泡狀態為開啟，那該燈泡就會被關閉。

第 1 輪，每個燈泡切換一次開關。即打開所有的燈泡。

第 2 輪，每兩個燈泡切換一次開關。即每兩個燈泡關閉后一個。

第 3 輪，每三個燈泡切換一次開關。即位于第3、6、9···的燈泡切換開關。

第 i 輪，每 i 個燈泡切換一次開關。而第 n 輪，你只切換最后一個燈泡的開關。

找出 n 輪后有多少個亮著的燈泡。

示例 1：

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

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

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

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

我們仔細看看上面的數據就會發現，最后亮燈的位置都在第1、4、9位上，這些位置恰好都是某個因子的平方，比如4，就是2的平方，不知道大家還記得不，在數學上這種數字就叫做完全平方數。

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

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

都已經驗證到100輪了，那么基本就是這個規律了。

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

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

我們從上面的規律，可以猜測燈泡亮的數量一定和平方根的特性有關系的。

我們先看看一些非完全平方數：

8的因子: 1 2 4 8；

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

這些因子一定是偶數個，為什么呢？

因為一個因子，一定是和另一個因子，配合起來，才能得到這個數字。

回到我們的燈泡，比如我們拿n=3的情況來說，第一輪打開了第三輪的燈泡，第三輪就會給它關掉，因為1、3是3的成對因子。

但如果是n=4的情況，1、4雖然也會成對抵消，但是第二輪的操作卻無法抵消，因為2的成對因子是2，不會再重復出現。

從這里我們就可以看出來，每增加一個完全平方數，就會多一個不會被抵消掉的因子出現，所以個數也就增加了1。

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

要找到有多少個完全平方數，是否一定要遍歷完1-n？

稍微思考下就可以發現并不是，拿9舉個：3是9的完全平方因子，在3以上的數字一定不能構成完全平方因子，因為開平方一定超過最大數字9了。如此一來，我們只用考慮3之前的。

不難發現，3之前的1、2是必然滿足完全平方因子的，因為它們做平方，一定小于3的平方，也就一定在數據范圍內。

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

return (int)Math.sqrt(n)