关于javascript:Leetcode-319灯泡开关

刚读完这道题后，很容易会想到用两重循环去模拟题中的过程，然而，如果真的用两重循环去解，就会失去超时的后果。。。

解题思路：

（1）第 i 个灯泡开关次数为 i 的约数个数；如果 i 有奇数个约数，则第 i 个灯泡最初为关上状态；如果 i 有偶数个约数，则第 i 个灯泡最初为敞开状态。

（2）因为约数总是成对呈现（即如果 x 是 i 的约数，那么 i / x 也是 i 的约数），所以只有当 i 为齐全平方数时，i 才有奇数个约数

（3）[1, n]中齐全平方数的个数就是最初关上状态的灯泡个数

（4）设 m 为 n 开平方并向下取整，m m 便是 [1, n] 中最大的齐全平方数，即 [1, n] 中有 m 个齐全平方数（即 1 1, 22, 33, … , m*m）

程序实现：

/**

 * @param {number} n

 * @return {number}

 */

var bulbSwitch = function(n) {return Math.floor(Math.sqrt(n));

};

复杂度剖析：

工夫复杂度 O(1)

空间复杂度 O(1)