leetcode319 灯泡的开关

初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。

示例:

输入: 3
输出: 1 
解释: 
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 

你应该返回 1，因为只有一个灯泡还亮着。

思路：

规律显而易见，只有在轮数是该位置因数的时候才会执行翻转操作。

于是我们回答了那个问题：只要找到该位置的所有因数个数，我们就知道该位置翻转了多少次。

更进一步的，除了完全平方数，因数都是成对出现的，这意味着实际起到翻转作用(0->1)的，只有
完全平方数而已。

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
 int bulbSwitch(int n) {
     
    
   

    

     

    
    

     
 return sqrt(n);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      };
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/103251588