快乐数

题目描述
编写一个算法来判断一个数 n 是不是快乐数。
快乐数的定义如下：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 重复这个过程，直到这个数变为 1，也可能是无限循环但始终变不到 1。
• 如果可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true；不是则返回 false。

示例 1
输入：n = 19
输出：true
解释：
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

示例 2
输入：n = 2
输出：false
解释：计算会进入循环：2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → … 永远到不了 1。

解题过程

步骤 1：理解问题关键
题目核心是模拟“数字平方和”的计算过程，并判断结果是否会收敛到 1，还是会进入一个无限的循环。
无限循环意味着在计算过程中，某个数字会重复出现，之后就会一直重复这个序列。
因此，我们需要一种方法来检测重复。这正是哈希集合（HashSet）的典型应用场景。

步骤 2：计算数字的平方和
设计一个辅助函数 getSum(int n)，输入整数 n，输出 n 的每一位数字的平方和。
做法是：

1. 初始化结果 sum = 0。
2. 当 n > 0 时，重复：
   • 取 n 的个位数：digit = n % 10
   • 将 digit * digit 加到 sum
   • n 去掉个位数：n = n / 10
3. 返回 sum。

例如，n = 19：

• digit=9, sum=0+81=81, n=1
• digit=1, sum=81+1=82, n=0 → 返回 82。

步骤 3：检测循环
我们模拟计算过程：

1. 初始化一个哈希集合 seen，用于存储已经出现过的数字。
2. 当 n 不等于 1 且 n 不在 seen 中时：
   • 将 n 加入 seen
   • 计算 n 的平方和，赋值给 n
3. 循环结束后，判断 n 是否等于 1：
   • 等于 1 → 是快乐数
   • 不等于 1 → 说明 n 是重复出现的数字（即在 seen 中已存在），进入了循环，不是快乐数。

为什么用哈希集合？
因为哈希集合可以在平均 O(1) 时间内判断一个数字是否已经存在，从而快速检测循环。

步骤 4：详细推演示例 n = 19
seen = {}
n=19 → 不在 seen 中，加入 seen={19}，计算平方和 82
n=82 → 不在 seen 中，加入 seen={19,82}，计算平方和 68
n=68 → 不在 seen 中，加入 seen={19,82,68}，计算平方和 100
n=100 → 不在 seen 中，加入 seen={19,82,68,100}，计算平方和 1
n=1 → 等于 1，结束，返回 true。

步骤 5：详细推演示例 n = 2
seen = {}
n=2 → 加入 seen={2}，平方和 4
n=4 → 加入 seen={2,4}，平方和 16
n=16 → 加入 seen={2,4,16}，平方和 37
n=37 → 加入 seen={2,4,16,37}，平方和 58
n=58 → 加入 seen={2,4,16,37,58}，平方和 89
n=89 → 加入 seen={2,4,16,37,58,89}，平方和 145
n=145 → 加入 seen={2,4,16,37,58,89,145}，平方和 42
n=42 → 加入 seen={2,4,16,37,58,89,145,42}，平方和 20
n=20 → 加入 seen={2,4,16,37,58,89,145,42,20}，平方和 4
n=4 → 此时 4 已经在 seen 中（循环出现），停止循环，n=4≠1，返回 false。

步骤 6：时间复杂度与空间复杂度分析

• 时间复杂度：O(m * d)，其中 m 是直到检测到循环或达到 1 的步数，d 是每次计算平方和的位数（实际上每次计算是 O(log n) 的时间，n 会迅速减小）。更严谨的分析可参考“快乐数”的数学性质，但可以认为是 O(log n) 级别的。
• 空间复杂度：O(m)，哈希集合存储已出现的数字，m 是步数。

步骤 7：边界情况

• n 可能很大，但平方和计算会让数字迅速变小（因为数字位数有限）。
• n = 1 直接是快乐数。
• 注意 n 可能为 0？题目说正整数，所以 n ≥ 1。

步骤 8：代码实现（伪代码）

function isHappy(n):
    seen = empty HashSet
    
    while n != 1 and n not in seen:
        seen.add(n)
        n = getSum(n)
    
    return n == 1

function getSum(num):
    sum = 0
    while num > 0:
        digit = num % 10
        sum += digit * digit
        num = num / 10
    return sum

总结
此题巧妙地结合了模拟计算与哈希查重。哈希表在这里的作用是记录历史状态，从而在状态重复时立即判断进入循环，终止计算。这是解决“可能循环”类问题的常见技巧。