LeetCode 319 - 灯泡开关

[Northxw]

  题目描述： 初始时有 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 小弟愚钝，恳请解惑。

[qwertyegg]

对于一个整数 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))

[Northxw]

@qwertyegg emmm... 这算是翻译了一遍重要部分吗？

[petelin]

这题最后有一个地方很有意思 比 n 小的所有完美平方数的个数就是 n 的平方

[petelin]

感谢一楼 很简洁 其实就是 任何一个数 都能被拆开成 n 对数相乘 这个题正好一对是一开一关结果为关
但是为什么最后还有开着的？因为有完全平方数比如 2×2 只开了一次对应的关不会操作 所以只有完全平方数是开着的

[yippees]

大概查了下
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 的平方根的取整。

//我也只是大约想到约数 完全平方数··

[Northxw]

@petelin 谢谢啦
@yippees 谢谢啦

[widewing]

等等。。这难道不是求小于 n 的质数个数吗？

[Northxw]

@widewing 不是的

[smdbh]

从暴力双循环慢慢优化，就有了 1 楼的答案