題目
(https://leetcode-cn.com/problems/bulb-switcher/)
初始時(shí)有 n 個(gè)燈泡關(guān)閉苛吱。 第 1 輪尝丐，你打開所有的燈泡。 第 2 輪薪丁，每兩個(gè)燈泡你關(guān)閉一次候醒。 第 3 輪，每三個(gè)燈泡切換一次開關(guān)（如果關(guān)閉則開啟，如果開啟則關(guān)閉）岩馍。第 i 輪碉咆，每 i 個(gè)燈泡切換一次開關(guān)。 對于第 n 輪蛀恩，你只切換最后一個(gè)燈泡的開關(guān)疫铜。 找出 n 輪后有多少個(gè)亮著的燈泡。
示例:
輸入: 3
輸出: 1
解釋:
初始時(shí), 燈泡狀態(tài) [關(guān)閉, 關(guān)閉, 關(guān)閉].
第一輪后, 燈泡狀態(tài) [開啟, 開啟, 開啟].
第二輪后, 燈泡狀態(tài) [開啟, 關(guān)閉, 開啟].
第三輪后, 燈泡狀態(tài) [開啟, 關(guān)閉, 關(guān)閉].
你應(yīng)該返回 1双谆，因?yàn)橹挥幸粋€(gè)燈泡還亮著壳咕。
分析
首先理解一下開根號的含義。
sqrt(16)=4,表示在16之前有4個(gè)數(shù)顽馋，可以實(shí)現(xiàn)自己的平方小于16谓厘，分別是1,2,3,4
sqrt(26)=5,表示在26之前有5個(gè)數(shù)，可以實(shí)現(xiàn)自己的平方小于25寸谜，分別是1,2,3,4,5
回歸正題庞呕。首先假設(shè)n=5；
第5個(gè) 只有在 1,5的情況下回翻轉(zhuǎn) 翻轉(zhuǎn)后還是原來的狀態(tài)
第16個(gè) 只有在1,2,4,8,16情況下會翻轉(zhuǎn) 翻轉(zhuǎn)后是原來相反的狀態(tài)
如何判斷最后是原來的狀態(tài)還是原來相反的狀態(tài)呢程帕？
進(jìn)一步住练，第i個(gè)，就是只有在i的因數(shù)的的情況下才會翻轉(zhuǎn)愁拭，但是因數(shù)都是成對存在的讲逛。所以最后因數(shù)的情況下都會復(fù)原
那么就只剩完全平方數(shù)了。只要計(jì)算第n個(gè)位置有幾個(gè)完全平方數(shù)就有幾個(gè)開著的燈岭埠。也就是sqrt(n)
代碼
class Solution {
public int bulbSwitch(int n) {
return (int)Math.sqrt(n);
}
}
結(jié)果
