[319]. 灯泡开关

[319]. 灯泡开关

• • 题目
  • 算法设计：完全平方数

题目

传送门：https://leetcode.cn/problems/bulb-switcher/

 

算法设计：完全平方数

问题是有多少灯是亮的。

那怎么样灯才会亮呢？

• 点偶数次相当于没点，开了又关。只有点奇数才会亮，开了。

比如，第 6 栈灯，第1、2、3、6次都点了，其实没亮，开了关了开了关了。

之所以第 6 栈灯会被点 4 次是因为：6 = 1×6 = 2×3。

也就是说，亮 = 点奇数次。

那什么情况会存在奇数呢？

• 比如 16 = 1×16 = 2×8 = 4×4。

• 4 重复了，实际上第 4 轮只会按一次。

也就是说，亮灯 = 点奇数次 = 完全平方数。

问有多少灯亮，就是问 [1-n] 中有多少完全平方数？

这里是有一个数学结论的，[1-n] 中的完全平方数有 $\sqrt{n}$ 个。

• 如 n=16，$\sqrt{n}$ = 4。

最后会有4栈灯亮，分别是：

1×1=1
2×2=4
3×3=9
4×4=16

16栈灯时，第 1、4、9、16 栈灯会亮。

n灯 亮灯
1  1
2  1
3  1
4  2
5  2
6  2
7  2
8  2
9  3
10  3
11  3
12  3
13  3
14  3
15  3
16  4
17  4
18  4
19  4
20  4
21  4
22  4
23  4
24  4
25  5

完整代码：

int bulbSwitch(int n) {
    int cnt = 0;
    // 统计区间 [1, n] 上完全平方数的个数
    for (int i = 1; i * i <= n; ++i) 
        ++cnt;
    return cnt;
}

或者：

int bulbSwitch(int n) {
	return sqrt(n);
}