leetcode_319

发表于   |   分类于

Bulb Switcher

题目戳这

题意

给定n个灯泡，刚开始都是灭的。第一轮打开所有的灯，第二轮把灯泡编号为2的整数倍的全灭了，第三轮把灯泡编号为3的整数倍的改变状态，就是亮的灭掉，灭的点亮。一直到第n轮，仅改变第n个灯泡的状态。

解法

这个首先我们模拟一下就知道了，如果某个灯泡的编号含有的因子数目为奇数的时候，这个灯泡最终的状态就是亮着的，反之亦然。但是怎么找到那些含有因子数为奇数的数字呢？

分析一下就会有一个很巧妙的方法，，就是因子其实都是成对出现的，比如6，它含有的因子对为1和6，2和3。这样它的因子数就是偶数。什么数字因子数为奇数呢？那就是平方数，，比如16，它的因子对为1和16，2和8，4和4。4和4就是同一个数字，即16有的因子数为1，2，4，8，16。一共5个因子。所以在[1,n]的范围里面，我们只要找到有几个平方数就行了。

怎么快速找有几个平方数呢？只要sqrt(n)即可。。比如n=20, sqrt(n)=4，分别为11，22，33，44。。

Orz…

代码

1
2
3
4
5
6
7
8
class Solution(object):
    def bulbSwitch(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        return int(n**(0.5))