每日一题——319. 灯泡开关

319. 灯泡开关

初始时有 n 个灯泡处于关闭状态。第一轮,你将会打开所有灯泡。接下来的第二轮,你将会每两个灯泡关闭一个。

第三轮,你每三个灯泡就切换一个灯泡的开关(即,打开变关闭,关闭变打开)。第 i 轮,你每 i 个灯泡就切换一个灯泡的开关。直到第 n 轮,你只需要切换最后一个灯泡的开关。

找出并返回 n 轮后有多少个亮着的灯泡。

public class Solution {
    public int BulbSwitch(int n) {
         return (int)Math.Sqrt(n + 0.5);
    }
}

这题直接把孩子整麻了

去看了题解才知道这是一道纯粹的数学题

我试着画图去找规律但确实总结不出来

只知道是第i次i的倍数的灯泡都要变换状态

总之这道题挺烦的

根据题意我们能知道因为第一次灯泡是全亮的

那么经过n次后还亮着的灯泡一定是切换了奇数次


从1到n,这盏灯泡经历了什么呢?

他会分别被1、2、3…n试图去除

假如它被除了奇数次,也就是它切换了奇数次

所以问题转换为从1到n这n个灯泡里有几个灯泡的约数是奇数


根据约数的概念,约数总是成对出现的

如果某个数的约数是奇数,就代表有一个约数重复使用了

例如1*1 2*2 3*3

符合这种条件的数我们通常叫它完全平方数

那问题就变成了1到n有几个完全平方数


根据数论推论,[1,n]中完全平方数的个数为 根号n

因为取整为了修正所以加了0.5

总之答案输出根号n就行了

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注