初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。
第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。
找出并返回 n 轮后有多少个亮着的灯泡。
超时。
class Solution {public int bulbSwitch(int n) {int[] arr = new int[n];int cnt = 1;int c = 0;while (cnt <= n) {for (int i = 0; i < n; i = i + cnt) {arr[i] = arr[i] == 0 ? 1 : 0;}}for (int i = 0; i < n; i++) {if (arr[i] == 1) {c++;}}return c;}
}
class Solution {public int bulbSwitch(int n) {return (int) Math.sqrt(n);}
}
关键观察：灯泡状态由其因子数量决定
对于灯泡 i，它会被切换的次数等于 i 的因子数量。例如：
灯泡 6 会在第 1、2、3、6 次被切换，因为 6 的因子是 1, 2, 3, 6。
灯泡 12 会在第 1、2、3、4、6、12 次被切换，因为 12 的因子是 1, 2, 3, 4, 6, 12。
每个灯泡的最终状态是开还是关，取决于它被切换的次数：如果被切换的次数是 偶数次，则它最终会是关闭的。
如果被切换的次数是 奇数次，则它最终会是开启的。需要找到小于等于 n 的完全平方数的个数，这样我们就可以知道最终有多少灯泡是开启的。
这个问题的核心就是：灯泡编号为完全平方数的灯泡，才会有奇数个因子，最终保持开启状态
