Skip to content

319 Bulb Switcher

319. Bulb Switcher

题目: https://leetcode.com/problems/Bulb-Switcher/

难度:

Medium

思路

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)

原来,这是一道智商碾压题:

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,所以本题的关键在于找完全平方数的个数。

class Solution(object):
    def bulbSwitch(self, n):
        """
        type n: int
        rtype: int
        """
        # The number of full squares.
        return int(math.sqrt(n))


回到顶部