难度: Medium
初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。
第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。
找出并返回 n 轮后有多少个亮着的灯泡。
示例 1：
输入：n = 3 输出：1 解释： 初始时, 灯泡状态 [关闭, 关闭, 关闭]. 第一轮后, 灯泡状态 [开启, 开启, 开启]. 第二轮后, 灯泡状态 [开启, 关闭, 开启]. 第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 你应该返回 1，因为只有一个灯泡还亮着。
示例 2：
输入：n = 0 输出：0
示例 3：
输入：n = 1 输出：1
提示：
0 <= n <= 109运行时间: 17 ms
内存: 16.0 MB
class Solution:
def bulbSwitch(self, n: int) -> int:
return int(math.sqrt(n))
该问题的核心在于观察每个灯泡在n轮后的状态。一个灯泡i在第k轮被操作，当且仅当k是i的除数。因此，灯泡i在n轮后变化的次数等于它的除数的数量。一个数有奇数个因数当且仅当它是完全平方数（例如，4的因数有1, 2, 4）。因此，问题转化为计算1到n之间完全平方数的数量，这可以通过计算sqrt(n)的整数部分得到，因为这表示了最大的数k，使得k*k <= n。
时间复杂度: O(1)
空间复杂度: O(1)
import math
class Solution:
def bulbSwitch(self, n: int) -> int:
# 计算n的平方根，然后取整，这是因为我们需要找出所有小于等于n的完全平方数的数量
return int(math.sqrt(n))
通常情况下，一个数的因数是成对出现的，例如对于数15，其因数有1, 3, 5, 15，可以看到1对应15，3对应5。这是因为因数是成对乘积等于原数的两个数。但是，对于完全平方数，如16，其因数有1, 2, 4, 8, 16，可以看到除了4之外，其他因数都是成对出现的。数4是16的一个因数，同时也是平方根，它不需要配对就能成为16的因数。这样，平方数的因数总数是奇数，因为它有一个中间的因数（即其平方根），它不与任何不同的数配对。因此，只有完全平方数具有奇数个因数，而其他数的因数总是成对的，因此是偶数个。
题解中使用的方法是基于数学原理的，计算sqrt(n)并取其整数部分的方法确实能准确计算出1到n之间所有完全平方数的数量。这是因为完全平方数的定义是某整数k的平方，k^2。计算sqrt(n)实际上是找到最大的整数k，使得k^2小于等于n。这个方法在数学上是准确的，因为它直接基于完全平方数的定义。不存在因此方法而导致的误差，但需要注意的是，这种计算方式假定n是非负整数，并且使用的函数库能够正确处理大数和浮点数运算。
在这个特定问题中，使用math.sqrt函数后取整不会对结果造成负面影响。这是因为我们的目的是寻找最大的整数k，使得k^2小于等于n。math.sqrt(n)计算n的平方根，取整操作确保我们得到的是不大于sqrt(n)的最大整数。这个整数恰好是我们想要找到的k。因为完全平方数是连续的（1的平方，2的平方，...），取整操作确保我们没有包含超过n的平方数。因此，这种取整方法是适合这个问题的，没有引入误差。