难度: Medium
原题连接
内容描述
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Example:
Input: 3
Output: 1
Explanation:
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].
So you should return 1, because there is only one bulb is on.
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
bulb代表第一轮结束后的所有灯亮灭的情况，从第二轮开始
- 如果是最后一轮，则bulb的最后一个灯要switch
- 对于其他轮，相应的第i-1+C(i)个灯要siwitch，且C为常数，i-1+C(i)必须<=n-1
但是发现这样提交会超时 Last executed input: 999999
class Solution(object):
def bulbSwitch(self, n):
"""
:type n: int
:rtype: int
"""
bulb = [1] * n
for i in range(2,n+1):
for x in range(i-1, n, i):
bulb[x] = 1 if bulb[x] == 0 else 0
return bulb.count(1)
思路 2 - 时间复杂度: O(1)- 空间复杂度: O(1)******
原来，这是一道智商碾压题：
A bulb ends up on iff it is switched an odd number of times. Bulb i is switched in round d iff d divides i. So bulb i ends up on iff it has an odd number of >divisors. Divisors come in pairs, like i=12 has divisors 1 and 12, 2 and 6, and 3 and 4. Except if i is a >square, like 36 has divisors 1 and 36, 2 and 18, 3 and 12, 4 and 9, and double divisor 6. So bulb >i ends up on iff and only if i is a square. So just count the square numbers.
大概解释一下，当一个灯泡被执行偶数次switch操作时它是灭着的，当被执行奇数次switch操作时它是亮着的，那么这题就是要找出哪些编号的灯泡会被执行奇数次操作。
现在假如我们执行第i次操作，即从编号i开始对编号每次+i进行switch操作，对于这些灯来说， 如果其编号j（j=1,2,3,⋯,n）能够整除i，则编号j的灯需要执行switch操作。 具备这样性质的i是成对出现的，比如：
- 12 = 1 * 12，
- 12 = 2 * 6
- 12 = 3 * 4
所以编号为12的灯，在第1次，第12次；第2次，第6次；第3次，第4次一定会被执行Switch操作，这样的话，编号为12的灯执行偶数次switch，肯定为灭。 这样推出，完全平方数一定是亮着的，因为它有两个相同的因子，总因子数为奇数，如36 = 6 * 6，所以本题的关键在于找完全平方数的个数。
为什么时间复杂度是O(1)呢，因为追溯到最底层，求开方就是O(1)的，详细见
class Solution(object):
def bulbSwitch(self, n):
"""
type n: int
rtype: int
"""
# The number of full/perfect squares.
return int(math.sqrt(n))