題目在問什麼

給一個正整數 n，不斷把它替換成「各位數字平方和」。

如果最後會走到 1，它就是 happy number；如果會卡進不包含 1 的循環，就不是。

例子

Input: n = 19
Output: true

因為：

1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

解題思路

這題關鍵不是怎麼算平方和，而是怎麼判斷自己是否已經進入循環。

最直接的做法是用 HashSet<int> 記錄每一輪算出來的結果：

  • 如果某次結果變成 1，就回傳 true
  • 如果某次結果之前已經出現過，代表進入循環，回傳 false

如何拆出每一位數

每輪計算平方和時，可以反覆做：

  • n % 10 取得個位數
  • n /= 10 去掉個位數

把每一位的平方累加起來，就是下一輪的新數字。

代碼

public class Solution
{
    public bool IsHappy(int n)
    {
        if (n == 1) { return true; }

        HashSet<int> hash = new HashSet<int>();

        while (n != 1)
        {
            int curr = 0;

            while (n > 0)
            {
                int remainder = n % 10;
                curr = remainder * remainder + curr;
                n /= 10;
            }

            if (hash.Contains(curr)) { return false; }

            hash.Add(curr);
            n = curr;
        }

        return true;
    }
}

複雜度

這題實際上狀態數量不會太大，因此可以視為很小的循環空間。

  • 時間複雜度：O(log n) 到收斂，每輪要拆各位數
  • 空間複雜度：O(log n) 或可視作有限狀態集合

這題先記住的重點

  • 這題真正要處理的是「循環檢測」
  • HashSet 是最直觀的做法
  • 拆數字位數時，% 10 和 / 10 是標準手法