解題說明
Happy Number
題目描述：給定一個正整數 n，反覆對其每個位數的平方和進行計算。若最終結果收斂到 1，則 n 為快樂數；否則將陷入無限循環，永遠無法到達 1。
解題思路：對各位數平方和反覆迭代，存在兩種情況：要麼收斂到 1（快樂數），要麼進入一個循環。關鍵觀察是，所有非快樂數最終都會進入含有數字 4 的循環。偵測循環有兩種策略：
- 雜湊集合法：每次計算出新的平方和後，若已出現在集合中則代表進入循環，回傳 false；若等於 1 則回傳 true。
- Floyd 龜兔賽跑法：把數列視為鏈結串列，用快慢指標偵測循環。慢指標每次走一步，快指標每次走兩步。若快慢指標相遇且值為 1，是快樂數；相遇但值不為 1，則進入循環。
本解法使用雜湊集合，直觀且易於理解。
C++ 解法
複雜度分析
時間複雜度：O(log n) 每步（計算位數平方和）× 步數。對於不快樂數，循環中最大值有上界（三位數以上必然縮小），因此步數有限，整體為 O(log n)。
空間複雜度：O(log n) — 雜湊集合儲存循環中遇到的數字，數量有限。
虛擬碼
1. Define helper digitSquareSum(n): a. sum = 0 b. While n > 0: extract digit d = n%10, sum += d*d, n /= 10 c. Return sum 2. Initialize empty hash set 'seen' 3. While n != 1: a. If n is in seen, return false (cycle detected) b. Insert n into seen c. n = digitSquareSum(n) 4. Return true
其他解法
Floyd 龜兔賽跑法 O(log n)：慢指標每步走一次 digitSquareSum，快指標每步走兩次。若快慢指標相遇時值為 1 則回傳 true，否則 false。不需要額外空間（O(1)），適合追求空間最優的情境。
硬編碼循環數字集合 O(log n)：已知所有不快樂數最終都會經過 {4, 16, 37, 58, 89, 145, 42, 20}，直接檢查 n 是否等於這些數字之一即可提前終止，概念簡單但依賴預先知識。
延伸思考
- 若改為計算位數的立方和，哪些數字是「快樂數」？循環結構有何不同？
- 如何用 Floyd 龜兔賽跑法改寫此題以達到 O(1) 空間？
- 給定一個範圍 [1, n]，如何高效找出所有快樂數而不重複計算？