題目描述

編寫算法判斷一個數是否為「快樂數」。過程：對任意正整數，反覆替換為各位數字平方和，直到結果為 1（快樂數），或陷入不含 1 的循環（非快樂數）。

示例 19： 1²+9²=82 → 8²+2²=68 → 6²+8²=100 → 1²+0²+0²=1 → 快樂數

核心洞察

非快樂數最終會陷入循環（如 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4）。使用 HashSet 記錄出現過的數，檢測循環。

代碼實現

#include <iostream>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool isHappy(int n) {
        if (n <= 0) return false;
        if (n == 1) return true;
        unordered_set<int> seen;
        while (true) {
            int sum = 0;
            while (n > 0) {
                int d = n % 10;
                sum += d * d;
                n /= 10;
            }
            if (sum == 1) return true;
            if (seen.count(sum)) return false; // 循環檢測
            seen.insert(sum);
            n = sum;
        }
    }
};

進階：Floyd 循環檢測（O(1) 空間）

快慢指針：slow = f(slow)，fast = f(f(fast))。若相遇且不為 1，則有環。無需額外存儲。

int next(int n) {
    int sum = 0;
    while (n) { int d = n%10; sum += d*d; n/=10; }
    return sum;
}
bool isHappy(int n) {
    int slow = n, fast = n;
    do {
        slow = next(slow);
        fast = next(next(fast));
    } while (slow != fast);
    return slow == 1;
}

數學性質補充

• 所有非快樂數最終進入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 循環
• 三位數以上數字平方和嚴格遞減，最終進入三位數範圍，狀態空間有限
• 快樂數密度約 1/7

測試用例