这是一个创建于 2078 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目描述： 初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。示例:
输入: 3
输出: 1
解释:
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭].
你应该返回 1，因为只有一个灯泡还亮着。
我的疑惑
谷歌百度一大堆解题思路，只有两个让我比较心仪的答案。一个时 CSDN 某博主在 2015 年写的，跳跃太大，我一时半会理解不了； 一个是力扣英文区本题评论区的精选评价，奈何谷歌翻译也会出现牛头不对马尾的语法，搞的我不知道该怎么去理解。
虽然在整体上对本题已经有了自己的认识，但是总感觉心里有疑惑点，好像差点什么，我自认为自己还没有搞懂这道题。 希望大家能帮我解答疑惑，分析的时候麻烦尽量详细点。
最后
我贴出力扣英文区该题的链接： https://leetcode.com/problems/bulb-switcher/discuss/77112/Share-my-o(1 小弟愚钝，恳请解惑。
 |
1
qwertyegg 2019-03-28 20:15:33 +08:00  1
对于一个整数 i,如果不是 perfect square(4, 9, 16...)，那么他的因子一定是成对(偶数个)出现的，比如 6 的因子是 1,2,3,6
而 perfect square 的因子是奇数个，比如 16 的因子是 1, 2, 4, 8, 16 实际上就是数[1, n]之间有多少个 perfect square number，数量是 floor(log(n)) |
 |
3
petelin 2019-03-28 20:19:29 +08:00 via iPhone
这题最后有一个地方很有意思 比 n 小的所有完美平方数的个数就是 n 的平方
|
|
4
petelin 2019-03-28 20:24:44 +08:00 via iPhone
感谢一楼 很简洁 其实就是 任何一个数 都能被拆开成 n 对数相乘 这个题正好一对是一开一关结果为关
但是为什么最后还有开着的？因为有完全平方数比如 2×2 只开了一次对应的关不会操作 所以只有完全平方数是开着的 |
 |
5
yippees 2019-03-28 20:37:29 +08:00
大概查了下
https://blog.csdn.net/camellhf/article/details/52819154 首先观察题目给的例子，结合题意，很自然就能想到，一个开关 i 被拨动的次数就是 i 的约数的个数，比如第 8 个开关，它被拨动了 4 次，分别在轮数=1,2,4,8 时，而 1，2，4，8 就是 8 的约数。 所以题目就变成了求 1-n 中每个数 i 的约数个数，统计约数个数是奇数的数目，因为如果约数个数是奇数，则开关是开的。 那么下一步就是求 i(i≤n)的约数个数，想到这里，要发现一点，约数是成对存在的，即 2 是 8 的约数，那么 8÷2=4 也是 8 的约数，其中有一种特殊情况，就是 i 为完全平方数，比如 9 跟它的约数 3，因此， 如果 i 是完全平方数，那么 i 的约数个数肯定是奇数，如果 i 不是完全平方数，由于约数成对出现，所以约数个数肯定是偶数。 想出了这一点，这道题就变成了更简单的题目：计算 1-n 中完全平方数的数目，到这里就不用我继续讲了吧。 ——————华丽的分割线————————– 以上是我 10 分钟前的想法，然而在这洗澡的 10 分钟里，我突然想到了小于等于 n 的平方数的数目就是直接对 n 的平方根取整数，所以最佳的答案只需一行，直接返回对 n 的平方根的取整。 //我也只是大约想到约数 完全平方数·· |
 |
7
widewing 2019-03-29 07:36:17 +08:00 via Android
等等。。这难道不是求小于 n 的质数个数吗？
|
 |
9
smdbh 2019-03-29 17:45:38 +08:00
从暴力双循环慢慢优化，就有了 1 楼的答案
|
Select Language