Leetcode 319.灯泡开关
灯泡开关
初始时有 n 个灯泡关闭。第 1 轮,你打开所有的灯泡。第 2 轮,每两个灯泡你关闭一次。第 3 轮,每三个灯泡切换一次开关(如果关闭则开启,如果开启则关闭)。第 i 轮,每 i 个灯泡切换一次开关。对于第 n 轮,你只切换最后一个灯泡的开关。找出 n 轮后有多少个亮着的灯泡。
示例:
输入: 3
输出: 1
解释:
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭].
你应该返回 1,因为只有一个灯泡还亮着。
A bulb ends up on iff it is switched an odd number of times.
Bulb i is switched in round d iff d divides i. So bulb i ends up on iff it has an odd number of >divisors.
Divisors come in pairs, like i=12 has divisors 1 and 12, 2 and 6, and 3 and 4. Except if i is a >square, like 36 has divisors 1 and 36, 2 and 18, 3 and 12, 4 and 9, and double divisor 6. So bulb >i ends up on iff and only if i is a square.
So just count the square numbers.
大概解释一下,当一个灯泡被执行偶数次switch操作时它是关着的,当被执行奇数次switch操作时它是开着的,那么这题就是要找出哪些编号的灯泡会被执行奇数次操作。
现在假如我们执行第i
次操作,即从编号i开始对编号每次+i进行switch操作,对于这些灯来说,
如果其编号j(j=1,2,3,⋯,n)能够整除i,则编号j的灯需要执switch操作。
具备这样性质的i是成对出现的,比如:
j=12时,编号为12的灯,在第1次,第12次;第2次,第6次;第3次,第4次一定会被执行Switch操作,这样的话,编号为12的等肯定为灭。
但是当完全平方数36就不一样了,因为他有一个特殊的因数6,这样当i=6时,只能被执行一次Switch操作,这样推出,完全平方数一定是亮着的,所以本题的关键在于找完全平方数的个数。
class Solution {
public int bulbSwitch(int n) {
return (int) Math.sqrt(n);
}
}
最新文章
- PostgreSQL介绍以及如何开发框架中使用PostgreSQL数据库
- sax/dom/jdom/dom4j的区别
- C++智能指针简单剖析
- 智者当借力而行, 借助Autodesk应用程序商店实现名利双收
- 重新想象 Windows 8 Store Apps (58) - 微软账号
- 学习Shell脚本编程(第4期)_在Shell程序中的使用变量
- Linux Communication Mechanism Summarize
- [bzoj5015][Snoi2017]礼物
- Deep Learning - 2 反向传播
- codeforces 955F Cowmpany Cowmpensation 树上DP+多项式插值
- nodejs 文件拷贝
- WebsphereMQ搭建集群
- properties编程示例
- Java反编译工具CFR,Procyon简介
- [RxJS] Build your own RxJS
- Breadth-first Search-690. Employee Importance
- gen_projective_mosaic(Halcon例子)
- leetcode 14 最长公共前缀
- 3.3.1 Validations
- BZOJ1509 &; 洛谷4408:[NOI2003]逃学的小孩——题解