哈希算法题目：快乐数 题目描述 “快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程，直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。 给你一个整数 n ，判断它是否是快乐数。如果是，返回 true ；否则，返回 false 。 示例： 输入：n = 19 计算过程： 1² + 9² = 1 + 81 = 82 8² + 2² = 64 + 4 = 68 6² + 8² = 36 + 64 = 100 1² + 0² + 0² = 1 + 0 + 0 = 1 结果为 true 。 输入：n = 2 计算过程会进入循环：2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ... 结果为 false 。 解题思路 本题的核心在于判断计算过程是否会“无限循环”。如果一个数不是快乐数，其平方和序列必然会出现重复的数字（即进入循环），而不会无限发散（可以证明平方和不会无限增大）。因此，我们只需要在计算过程中记录已经出现过的数字，一旦发现重复，就说明进入了循环，返回 false ；如果计算得到 1，返回 true 。 记录已出现数字并快速判断重复，这正是哈希集合的典型应用场景。 解题步骤详解 步骤 1：设计辅助函数 getNext(n) 这个函数的目的是计算数字 n 各位数字的平方和。 初始化 sum = 0 。 当 n > 0 时循环： 取 n 的个位数： digit = n % 10 。 将 digit 的平方加到 sum 上： sum += digit * digit 。 将 n 除以 10（向下取整），去掉已经处理过的个位： n = n / 10 。 返回 sum 。 示例：n = 19 digit = 9 → sum = 0 + 81 = 81, n = 1 digit = 1 → sum = 81 + 1 = 82, n = 0 返回 82。 步骤 2：主函数 isHappy(n) 的实现 创建一个空的哈希集合 seen ，用于存储已经出现过的数字。 设置当前数字 current = n 。 进入循环（使用 while True 或 while current != 1 ）： 如果 current == 1 ，直接返回 true 。 如果 current 已经在集合 seen 中，说明进入了循环，返回 false 。 否则，将 current 加入集合 seen 。 调用 getNext(current) 得到下一个数字，并赋值给 current 。 循环结束后（理论上不会自然结束，因为总会在 1 或循环处返回）。 步骤 3：具体例子演示 以 n = 2 为例： seen = {}，current = 2。 2 不在 seen 中，加入 seen：{2}。计算 next：2 → 4。 current = 4，不在 seen 中，加入：{2, 4}。next：4 → 16。 current = 16，加入：{2, 4, 16}。next：16 → 1+36=37。 current = 37，加入：{2, 4, 16, 37}。next：37 → 9+49=58。 … 依次加入 58, 89, 145, 42, 20。 当 current = 4 时，发现 4 已经在 seen 中（{2, 4, 16, 37, 58, 89, 145, 42, 20}），说明进入循环，返回 false 。 步骤 4：复杂度分析 时间复杂度：O(log n) 的链长。因为 getNext 函数每次计算复杂度为 O(log n)（n 的位数），而序列长度不会太大（实验证明，无论 n 多大，序列长度不会超过几百）。 空间复杂度：O(log n) 的链长，哈希集合存储已出现的数字。 关键点总结 无限循环的判定 ：哈希集合高效检测重复出现。 数学保证 ：平方和序列不会无限增大（对于 32 位整数，最大平方和是 9² * 10 ≈ 810，远小于原数范围），因此必然进入循环或到达 1。 边界情况 ：输入为 1 时直接返回 true。 这种方法清晰、高效，是解决“快乐数”问题的标准方法。