今天是堅持每日一題打卡的第二十天

---

題目鏈接：https://leetcode-cn.com/problems/bulb-switcher/

---

題解匯總：https://zhanglong.blog.csdn.net/article/details/121071779

---

題目描述

初始時有 n 個燈泡處于關閉狀態。第一輪，你將會打開所有燈泡。接下來的第二輪，你將會每兩個燈泡關閉一個。

第三輪，你每三個燈泡就切換一個燈泡的開關（即，打開變關閉，關閉變打開）。第 i 輪，你每 i 個燈泡就切換一個燈泡的開關。直到第 n 輪，你只需要切換最后一個燈泡的開關。

找出并返回 n 輪后有多少個亮著的燈泡。

示例 1：
輸入：n = 3
輸出：1
解釋：
初始時, 燈泡狀態 [關閉, 關閉, 關閉].
第一輪后, 燈泡狀態 [開啟, 開啟, 開啟].
第二輪后, 燈泡狀態 [開啟, 關閉, 開啟].
第三輪后, 燈泡狀態 [開啟, 關閉, 關閉].

你應該返回 1，因為只有一個燈泡還亮著。

示例 2：
輸入：n = 0
輸出：0

示例 3：
輸入：n = 1
輸出：1

提示：
0 <= n <= 109

---

分析

題意：若有n盞燈， 第一輪將燈全部打開，第二輪將每兩個燈泡關閉一個，在第三輪，每三個燈泡就切換一下燈泡的開關（注意，前三輪每輪的操作都不同）。 持續到第n輪。第三輪到第n輪的操作相同。

舉例：假設有六盞燈，第一輪全部打開， 第二輪將第2，4，6盞燈關閉，第三輪將第三盞燈關閉，第六盞燈打開…

思路：
第六盞燈的操作次數：分別在第1，2，3，6次操作。 $6=1?6=2?3$ 我們發現，這恰好是6的全部因子。

類推到所有位置， 如第5盞燈的操作次數：分別在第1，5次操作， $5=1?5$

我們發現，無論是5還是6，都進行了偶數次操作， 也就是說最后的結果一定是關著的。

因此易得：如果進行了奇數次操作，最后的結果一定是開的。

進一步，我們來看4：

第四盞燈的操作次數：分別在1，2，4次操作， $4=1?4=2?2$

易得：可以開平方的數，擁有奇數次操作，最后是開著的。

因此，只需要對n進行開平方，我們就得到了最后的結果。

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

總結

以上是生活随笔為你收集整理的题意解读+详细题解-Leecode 319. 灯泡开关——Leecode每日一题系列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。