⭐️前面的话⭐️

本篇文章介绍来自319. 灯泡开关题解，难度为 中等，标签： 数学 数论 脑筋急转弯 想不到，展示语言为Java。

📒博客主页：未见花闻的博客主页
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
📌本文由未见花闻原创！
📆首发时间：🌴2022年11月30日🌴
✉️坚持和努力一定能换来诗与远方！
💭推荐书籍：📚《算法》，📚《算法导论》
💬参考在线编程网站：🌐牛客网🌐力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
🍭作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

⭐️319. 灯泡开关⭐️

🔐题目详情

319. 灯泡开关

难度中等336

初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。

第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。

找出并返回 n 轮后有多少个亮着的灯泡。

示例 1：

输入：n = 3
输出：1 
解释：
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 

你应该返回 1，因为只有一个灯泡还亮着。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：1

提示：

• 0 <= n <= 109

💡解题思路

基本思路： 数学
解题思路：
其实我们可以假设一开始n个灯泡都是关闭的，每第i次，就会将i倍数的编号的灯泡全部转换状态，即：
i=1时，所有的正整数都是1的倍数，因此所有的灯转换状态，从【关闭】状态到【打开】状态。
i=2时，为2的灯泡都会转换状态，同理i=3时，3的倍数的灯泡也会转换状态，以此类推，当第i次转换时，会将编号为i的倍数的灯泡转换状态。

以上假设完全符合题目的要求，n次操作后，仍然保持着【打开】状态的灯泡转换次数一定是【奇数次】，编号为i的灯泡转换次数，即i约数的个数。

问题转化为【[1,n]中有多少个约数为奇数的数】，由于约数是成对存在的，想要约数是奇数个，则一定得包含完全平方数，因为完全平方数的两个约数是相同的，而其他非完全平方数类的约数一定是成对存在的，如4，它的约数有1 4 2，1与4是成对出现的，2是4的开平方数，只会占据约数个数的一个席位，所以问题【[1,n]中有多少个约数为奇数的数】转换为【[1,n]中有多少个完全平方数】，区间[1,n]中完全平方数的个数为 $\sqrt{n}$，因此该算法题的答案为 $\sqrt{n}$。

🔑源代码

class Solution {
    public int bulbSwitch(int n) {
        return (int) Math.sqrt(n);
    }
}

🌱总结

一道数学推理题，想不到哎，记录下来。