【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,因为在循环里是多加了一次的。
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论