快乐数

好的，我们来讲一个新的、且尚未讨论过的哈希算法题目：“快乐数”。这是一个非常经典且有趣的问题，它巧妙地利用了哈希表来检测循环，是学习“快慢指针”或“哈希集合”应用的好例子。

1. 题目描述

题目：
编写一个算法来判断一个数 n 是不是快乐数。

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

示例 1：

• 输入：n = 19
• 输出：true
• 解释：
  1² + 9² = 82
  8² + 2² = 68
  6² + 8² = 100
  1² + 0² + 0² = 1
  最终得到 1，所以是快乐数。

示例 2：

• 输入：n = 2
• 输出：false
• 解释：
  2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> ...
  可以看到，最后在 “4” 这里进入了循环 (4->16->37->58->89->145->42->20->4)，永远也得不到1。所以不是快乐数。

2. 问题分析与核心难点

理解这个问题的关键在于题面中一个隐藏的关键词：“无限循环”。这意味着，对于一个非快乐数，我们计算平方和的过程会进入一个重复的循环。如果我们不采取措施识别这个循环，程序就会陷入死循环。

因此，这个题目的核心难点就变成了：如何判断一个序列中是否出现了重复的数字（循环）？

这正是哈希集合大显身手的地方。哈希集合可以在平均 O(1) 时间复杂度内判断一个元素是否已经存在。

3. 解题思路的循序渐进讲解

我们分几步来构建解决方案。

第一步：明确核心子操作——计算数字的平方和

我们首先需要一个辅助函数 getNext(n)，它的功能是：给定一个数 n，计算其每个数字的平方和。

如何实现？ 有两种常见方法：

1. 数学取模法：不断对数字取模（%10）得到最后一位数字，计算其平方，然后整除（//10）去掉最后一位，直到数字变为 0。
2. 字符串转换法：将数字转为字符串，然后遍历每个字符，再转回数字计算平方。这种方法更直观但效率稍低。

我们采用更高效的取模法：

def get_next(n):
    total_sum = 0
    while n > 0:
        digit = n % 10   # 获取最后一位数字
        n = n // 10      # 去掉最后一位数字
        total_sum += digit * digit
    return total_sum

验证：对于 n=19。

• 第一次循环：digit=9, n=1, total_sum=81
• 第二次循环：digit=1, n=0, total_sum=81+1=82。返回 82。

第二步：模拟计算过程并检测循环

这是最核心的一步。我们的算法框架可以描述为：

1. 初始化一个空的哈希集合 seen，用于记录已经出现过的数字。
2. 不断计算当前数字 n 的下一个数字 next_n。
3. 在每次计算后，检查：
   • 如果 next_n == 1：说明我们找到了终点，是快乐数，返回 True。
   • 如果 next_n 已经存在于 seen 集合中：说明我们进入了一个循环，永远也到不了1，不是快乐数，返回 False。
4. 如果以上都不满足，说明我们遇到了一个“新”的数字。将这个新数字 next_n 加入到 seen 集合中，并将 n 更新为 next_n，继续循环。

第三步：整合成完整算法

将以上两步整合起来，用代码清晰地表达逻辑。

def isHappy(n):
    def get_next(number):
        total_sum = 0
        while number > 0:
            number, digit = divmod(number, 10) # 同时得到商和余数，更简洁
            total_sum += digit ** 2
        return total_sum

    seen = set()
    while n != 1 and n not in seen: # 循环条件：没到1，且没出现过
        seen.add(n)          # 记录当前数字
        n = get_next(n)      # 计算下一个数字

    return n == 1            # 退出循环时，看n是否等于1

让我们手动模拟一下算法处理 n=19 的过程：

再模拟一下 n=2 的过程：
（过程会稍长，但关键点是当n变为4时，发现4已经在seen集合{2, 4, 16, 37, 58, 89, 145, 42, 20}中，循环终止，返回False）

4. 算法复杂度分析

• 时间复杂度：O(log n)。这里的分析稍微复杂一些。
  1. 计算下一个数字 get_next(n) 的时间复杂度是 O(log n)，因为一个数 n 的位数大约是 log₁₀(n)。
  2. 在最坏情况下，我们需要检测循环。对于任意给定的 n，其通过 get_next 函数生成的数字序列是有限的，并且被一个数学上的“上界”所约束（例如，对于3位数，最大平方和是 9² * 3 = 243）。因此，序列中的不同数字个数实际上存在一个上限（远小于n本身）。所以，总的时间复杂度可以视为 O(k * log n)，其中 k 是一个常数（通常不大）。最终简化为 O(log n)。
• 空间复杂度：O(k)。k 是序列中不同数字的个数，用于存储在哈希集合 seen 中。与时间复杂度分析类似，k 也存在一个上界。

5. 一个有趣且更优的替代方案：快慢指针法

虽然哈希集合的解法已经非常好了，但这个问题还有一个“空间复杂度为 O(1)”的巧妙解法——使用“快慢指针”来检测循环。这与检测链表是否有环的思想一模一样。

思路：

• 定义两个“指针”：slow 和 fast，初始都指向输入的数字 n。
• slow 每次走一步（计算一次 get_next）。
• fast 每次走两步（计算两次 get_next）。
• 循环进行，直到满足以下任一条件：
  1. fast == 1：说明它是快乐数，返回 True。
  2. slow == fast（且不等于1）：说明它们在循环中相遇，即存在环，不是快乐数，返回 False。

代码实现：

def isHappy(n):
    def get_next(number):
        total_sum = 0
        while number > 0:
            number, digit = divmod(number, 10)
            total_sum += digit ** 2
        return total_sum

    slow = n
    fast = get_next(n) # 快指针先走一步

    while fast != 1 and slow != fast:
        slow = get_next(slow)       # 慢指针走一步
        fast = get_next(get_next(fast)) # 快指针走两步

    return fast == 1

这个算法省去了哈希集合的开销，将空间复杂度降低到了 O(1)，是这个问题的一个更优解。

6. 总结

“快乐数”问题完美展示了哈希表在检测重复元素、判断循环存在性方面的强大作用。它的解题路径非常清晰：

1. 明确核心操作：分解数字并计算平方和。
2. 识别问题本质：判断一个序列是否出现重复，即检测循环。
3. 应用数据结构：使用哈希集合存储历史数字，以 O(1) 时间判断是否重复。
4. 思考优化：可以进一步使用快慢指针法，将空间复杂度优化到 O(1)。

通过这个问题，你不仅能掌握一个具体的算法，更能深刻理解“检测循环”这一抽象问题的两种通用解决方案（哈希集合和快慢指针）及其适用场景。