Last Updated on 2023-04-27 by Clay
題目
There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.
On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.
Return the number of bulbs that are on after n rounds.
Example 1:
Input: n = 3 Output: 1 Explanation: At first, the three bulbs are [off, off, off]. After the first round, the three bulbs are [on, on, on]. After the second round, the three bulbs are [on, off, on]. After the third round, the three bulbs are [on, off, off]. So you should return 1 because there is only one bulb is on.
Example 2:
Input: n = 0 Output: 0
Example 3:
Input: n = 1 Output: 1
Constraints:
0 <= n <= 109
題目給定一個正整數 n，代表我們會有 n 個燈泡，並且需要進行 n 輪的開關切換。開關切換的原理是，在第 i 輪時，我們要把每 i 個燈泡切換開關。
這樣說起來很抽象，下面直接表示。假設我們要跑 4 輪，我們會有 4 個燈泡，預設都是關閉的。
- 初始態：X X X X
- 第一輪：O O O O （每 1 個燈泡都需要切換開關）
- 第二輪：O X O X （每 2 個燈泡都需要切換開關）
- 第三輪：O X X X （每 3 個燈泡都需要切換開關）
- 第四輪：O X X O （每 4 個燈泡都需要切換開關）
我們最後要回傳的，就是在最後一輪結束後，有多少燈泡是亮著的。
解題思路
求 n 範圍內的平方數
我是用列舉來觀察出這個規律的，跟許多直接思考出這個規律的大神差太多了。簡單來說，如果你列舉了好幾個不同的 n 輸入，最後應該會觀察出一個規律：到最後會亮著的，都是平方數的燈泡亮著！
仔細一想的話其實也很單純，那就是第 i 個數字會被切換開關，代表它會被自己的因數除掉。一般會被因數整除的，通常都是成對出現的因數。
假設 15，15 可以被除以 (1, 15)、(3, 5)，所以 15 這個數字會被切換開關 4 次，也就恢復成了沒亮著的狀態。
但是若考慮到 16 的話，16 可以被除以 (1, 16)、(2, 8), (4, 4)，數列列出來就是 [1, 2, 4, 8, 16] —— 我們會發現，它總共被切換開關的次數是 5 次！也就是說，第 16 個燈泡到最後會是亮著的。
所以我們可以把這個題目，認定是『找到共有幾個小於等於 n 的平方數』。
求 n 範圍內的平方數 複雜度
| Time Complexity | O(log(n)) |
| Space Complexity | O(1) |
由於我們只需要找平方數，所以時間複雜度應該是 log(n)。
C++ 範例程式碼
class Solution {
public:
int bulbSwitch(int n) {
// Init
int result = 0;
int i = 1;
// Count result
while (i * i <= n) {
++result;
++i;
}
return result;
}
};Python 範例程式碼
class Solution:
def bulbSwitch(self, n: int) -> int:
# Init
result = 0
i = 1
# Count result
while i * i <= n:
result += 1
i += 1
return result
優化解
另外，可能還會很容易想到另外一個更快速的優化解法：如果我們只是要找在 n 中的平方根，那不是將 n 開根號就好了？
比方說 16，開根號是 4 —— 代表平方數就是 1^2=1, 2^2=4, 3^2=9, 4^2=16，到 5 就已經遠遠超過 16 啦。
對 17 來說也一樣，根本就不會計算到 5，因為 5 的平方 25 是一個大於 17 的數值，所以 17 也一樣只有 4 個平方數。
按照這個想法，我們只要將我們的輸入開根號，並取正整數的部分（忽略小數）就是我們最後會亮的燈泡數了。
兩節點走訪 複雜度
| Time Complexity | O(1) |
| Space Complexity | O(1) |
在許多程式語言的設計中，sqrt() 是一個內建的函式，使用浮點數的演算法，時間複雜度應是 O(1)。我查的資料是如此告訴我的，如果有謬誤之處還請不吝告訴我。
C++ 範例程式碼
class Solution {
public:
int bulbSwitch(int n) {
return int(sqrt(n));
}
};Python 範例程式碼
class Solution:
def bulbSwitch(self, n: int) -> int:
return int(sqrt(n))