【leetcode319】Bulb Switcher

  • 方法1:
    最简单的想法就是记录各个灯泡在每次变化后的状态,但是复杂度较高,为O(N*lgN),不建议此种方法。

  • 方法2:
    我们可以很容易地想到,最后状态是on的灯泡代表的标号,说明只有奇数个约数。

    eg:在N足够大的情况下:
        1号:因为只为1的倍数,只switch一次,on
        2号:为1,2的倍数,switch两次,off
        3号:为1,3的倍数,switch两次,off
        4号:为1,2,4的倍数,switch三次,on
        ...

    而什么情况会只有奇数个约数呢,平方数。

因而只需找到在不大于N的范围内的平方数个数即可。

class Solution(object):
    def bulbSwitch(self, n):
        count = 0
        if n == 0:
           return 0

        while count * count <= n:
            print(count)
            count += 1

        return count - 1

特别需要注意的地方是count最后需要-1,因为在循环里是多加了一次的。

评论

暂无评论