319. 灯泡开关
题目描述
有 n 个灯泡排成一排，一开始全部是灭的。接下来进行 n 轮操作。
第 1 轮把所有灯泡都打开。第 2 轮把编号为 2 的倍数的灯泡都关掉。从第 3 轮起，第 i 轮把编号为 i 的倍数的灯泡都拨一下开关：亮的变灭，灭的变亮。第 n 轮只拨最后一个灯泡。灯泡从 1 开始编号。
返回 n 轮之后还亮着的灯泡数。
示例 1
输入：n = 3 输出：1
解释：三轮之后依次为 [亮, 亮, 亮]、[亮, 灭, 亮]、[亮, 灭, 灭]，只剩 1 个亮着。
示例 2
输入：n = 0 输出：0
解释：没有灯泡。
示例 3
输入：n = 1 输出：1
解释：唯一的灯泡在第 1 轮被打开。
数据范围
0 <= n <= 10^9
解题思路
第 k 个灯泡在第 i 轮被切换，当且仅当 i 整除 k，所以它被切换的次数 = k 的因数个数。因数总是成对出现（d 与 k/d），只有完全平方数的 √k 自己配对，因数个数才是奇数。所以最后亮着的就是 1, 4, 9, … 这些完全平方数，个数为 ⌊√n⌋。
为什么正确
灯泡 k 最终亮 ⇔ k 的因数个数为奇数 ⇔ k 是完全平方数。
复杂度分析
时间 O(1)，空间 O(1)。
易错点
n 可达 10^9，直接模拟 O(n log n) 会超时。用浮点 sqrt 时要用整数校正，避免大数时的精度误差。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def bulbSwitch(self, n: int) -> int:
r = int(n ** 0.5)
while (r + 1) * (r + 1) <= n:
r += 1
while r * r > n:
r -= 1
return rclass Solution {
public int bulbSwitch(int n) {
int r = (int) Math.sqrt(n);
while ((long) (r + 1) * (r + 1) <= n) r++;
while ((long) r * r > n) r--;
return r;
}
}class Solution {
public:
int bulbSwitch(int n) {
int r = (int)sqrt((double)n);
while ((long long)(r + 1) * (r + 1) <= n) r++;
while ((long long)r * r > n) r--;
return r;
}
};func bulbSwitch(n int) int {
r := int(math.Sqrt(float64(n)))
for (r+1)*(r+1) <= n {
r++
}
for r*r > n {
r--
}
return r
}var bulbSwitch = function(n) {
let r = Math.floor(Math.sqrt(n));
while ((r + 1) * (r + 1) <= n) r++;
while (r * r > n) r--;
return r;
};function bulbSwitch(n: number): number {
let r = Math.floor(Math.sqrt(n));
while ((r + 1) * (r + 1) <= n) r++;
while (r * r > n) r--;
return r;
}