LeetCode 319 Bulb Switcher — 從模擬到數學規律的思維演進

題目重述

n 盞燈泡初始全滅。第 i 輪切換所有編號為 i 的倍數的燈泡（開→關、關→開）。共進行 n 輪，求最終亮著的燈泡數。

四階段思維歷程

階段 1：誤解題意

以為「every second bulb」僅指第 2 盞，寫出 return 1，測試 n=4 應為 2 才發現理解錯誤——實際是「每隔一盞」（2,4,6…）。

階段 2：暴力模擬

建立 bool[] 直接模擬，O(n²)，n=999999 直接 TLE。

階段 3：位運算優化存儲

嘗試用 long long 位圖壓縮空間，但位運算邏輯複雜，未完成。

階段 4：打印規律發現數學本質

列印 n=20,30 的亮滅矩陣，發現亮燈泡編號恰為 完全平方數：1, 4, 9, 16, 25…。
原因：第 k 盞燈泡被切換次數等於其約數個數。完全平方數約數個數為奇數，其餘為偶數。故答案為 ⌊√n⌋。

最終 O(1) 解法

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

「履帶車」直觀模型（文中原創）

作者將亮燈位置視為「履帶車」：間距為 1, 2, 1, 4, 1, 6, 1, 8…，其中偶數項 2,4,6,8… 為「輪子」。雖可寫 O(√n) 迴圈，但 sqrt 更簡潔。

總結

1. 暴力→優化→找規律→數學證明，是解題常見路徑。
2. 約數奇偶性決定最終狀態，完全平方數為關鍵。
3. LeetCode 同類題：Perfect Squares、Count Primes 等均需數學洞察。