[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] 中的完全平方数有
n
\sqrt{n}
n 个。
- 如 n=16， n \sqrt{n} 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);
}