哈希算法题目：快乐数
字数 2599 2025-10-26 19:15:23

哈希算法题目：快乐数

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

「快乐数」定义为：

  1. 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  2. 然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
  3. 如果可以变为 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
解释：（会进入循环 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 ...）

解题过程

步骤1：理解问题核心与难点
这个问题的核心操作是“求每个位置上的数字的平方和”，并不断重复。难点在于，如何判断一个数“不是”快乐数。题目提示了“无限循环但始终变不到1”的情况。因此，关键点在于检测这个“循环”。一旦我们在计算过程中遇到了之前出现过的数字，就意味着我们已经进入了一个循环，而这个循环里显然不包含1（否则过程就终止了），那么就可以断定这个数不是快乐数。

步骤2：设计关键操作 - 求数字的平方和
我们需要一个辅助函数 getNext(n) 来计算数字 n 的每一位数字的平方和。
具体步骤如下：

  1. 初始化一个变量 totalSum 为 0，用于累加平方和。
  2. 当 n 大于 0 时，循环执行：
    a. 通过 n % 10 操作获取 n 的个位数（digit）。
    b. 将这个个位数的平方（digit * digit）加到 totalSum 上。
    c. 通过 n = n / 10（整数除法）将 n 去掉个位数。
  3. 循环结束后，返回 totalSum。

以 n=19 为例：

  • 第一次循环：digit = 9 (19 % 10), totalSum = 0 + 81 = 81, n = 1 (19 / 10)。
  • 第二次循环：digit = 1 (1 % 10), totalSum = 81 + 1 = 82, n = 0 (1 / 10)。
  • 返回 82。

步骤3：选择检测循环的方法 - 哈希集合
我们需要一种高效的方法来记录计算过程中出现过的所有数字，并快速判断下一个数字是否已经存在于记录中。哈希集合（HashSet）是完美选择，因为它提供了 O(1) 时间复杂度的插入和查询操作。

算法逻辑如下：

  1. 创建一个哈希集合（命名为 seen），用于存储已经出现过的数字。
  2. 将输入的数字 n 作为当前数字。
  3. 进入一个循环，循环的条件是 n 不等于 1，并且 n 不在集合 seen 中。
    a. 将当前的 n 加入到集合 seen 中，标记为已出现。
    b. 调用 getNext(n) 函数，将结果赋值给 n，进行下一轮计算。
  4. 循环结束后，我们检查 n 是否等于 1。
    • 如果等于 1，说明是快乐数，返回 true。
    • 如果不等于 1，说明是因为 n 已经存在于 seen 中而退出循环的，即进入了循环，不是快乐数，返回 false。

步骤4：完整流程演示（以 n=2 为例）

  1. 初始化：seen 集合为空，n = 2。
  2. 第一轮：n=2 不在 seen 中且不等于1。
    • 将 2 加入 seen -> seen = {2}。
    • 计算 next：2² = 4 -> n = 4。
  3. 第二轮：n=4 不在 seen 中且不等于1。
    • 将 4 加入 seen -> seen = {2, 4}。
    • 计算 next：4² = 16 -> n = 16。
  4. 第三轮：n=16 不在 seen 中且不等于1。
    • 将 16 加入 seen -> seen = {2, 4, 16}。
    • 计算 next：1² + 6² = 1 + 36 = 37 -> n = 37。
  5. 第四轮：n=37 不在 seen 中且不等于1。
    • 将 37 加入 seen -> seen = {2, 4, 16, 37}。
    • 计算 next：3² + 7² = 9 + 49 = 58 -> n = 58。
  6. 第五轮：n=58 不在 seen 中且不等于1。
    • 将 58 加入 seen -> seen = {2, 4, 16, 37, 58}。
    • 计算 next：5² + 8² = 25 + 64 = 89 -> n = 89。
  7. 第六轮：n=89 不在 seen 中且不等于1。
    • 将 89 加入 seen -> seen = {2, 4, 16, 37, 58, 89}。
    • 计算 next：8² + 9² = 64 + 81 = 145 -> n = 145。
  8. 第七轮：n=145 不在 seen 中且不等于1。
    • 将 145 加入 seen -> seen = {2, 4, 16, 37, 58, 89, 145}。
    • 计算 next：1² + 4² + 5² = 1 + 16 + 25 = 42 -> n = 42。
  9. 第八轮：n=42 不在 seen 中且不等于1。
    • 将 42 加入 seen -> seen = {2, 4, 16, 37, 58, 89, 145, 42}。
    • 计算 next：4² + 2² = 16 + 4 = 20 -> n = 20。
  10. 第九轮：n=20 不在 seen 中且不等于1。
    • 将 20 加入 seen -> seen = {2, 4, 16, 37, 58, 89, 145, 42, 20}。
    • 计算 next：2² + 0² = 4 + 0 = 4 -> n = 4。
  11. 第十轮：此时 n=4。我们发现 4 已经在集合 seen 中了（第二轮加入的）。
    • 循环条件 n != 1 && n not in seen 不成立（因为4在seen中）。
    • 退出循环。
  12. 判断 n=4，不等于1，所以返回 false。数字2不是快乐数。

通过这个循序渐进的讲解，你应该能清晰地理解如何利用哈希集合来检测循环，从而解决“快乐数”问题。

哈希算法题目：快乐数 题目描述 编写一个算法来判断一个数 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 解释：（会进入循环 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 ...） 解题过程 步骤1：理解问题核心与难点 这个问题的核心操作是“求每个位置上的数字的平方和”，并不断重复。难点在于，如何判断一个数“不是”快乐数。题目提示了“无限循环但始终变不到1”的情况。因此，关键点在于检测这个“循环”。一旦我们在计算过程中遇到了之前出现过的数字，就意味着我们已经进入了一个循环，而这个循环里显然不包含1（否则过程就终止了），那么就可以断定这个数不是快乐数。 步骤2：设计关键操作 - 求数字的平方和 我们需要一个辅助函数 getNext(n) 来计算数字 n 的每一位数字的平方和。 具体步骤如下： 初始化一个变量 totalSum 为 0，用于累加平方和。 当 n 大于 0 时，循环执行： a. 通过 n % 10 操作获取 n 的个位数（digit）。 b. 将这个个位数的平方（digit * digit）加到 totalSum 上。 c. 通过 n = n / 10 （整数除法）将 n 去掉个位数。 循环结束后，返回 totalSum 。 以 n=19 为例： 第一次循环：digit = 9 (19 % 10), totalSum = 0 + 81 = 81, n = 1 (19 / 10)。 第二次循环：digit = 1 (1 % 10), totalSum = 81 + 1 = 82, n = 0 (1 / 10)。 返回 82。 步骤3：选择检测循环的方法 - 哈希集合 我们需要一种高效的方法来记录计算过程中出现过的所有数字，并快速判断下一个数字是否已经存在于记录中。哈希集合（HashSet）是完美选择，因为它提供了 O(1) 时间复杂度的插入和查询操作。 算法逻辑如下： 创建一个哈希集合（命名为 seen ），用于存储已经出现过的数字。 将输入的数字 n 作为当前数字。 进入一个循环，循环的条件是 n 不等于 1，并且 n 不在集合 seen 中。 a. 将当前的 n 加入到集合 seen 中，标记为已出现。 b. 调用 getNext(n) 函数，将结果赋值给 n，进行下一轮计算。 循环结束后，我们检查 n 是否等于 1。 如果等于 1，说明是快乐数，返回 true。 如果不等于 1，说明是因为 n 已经存在于 seen 中而退出循环的，即进入了循环，不是快乐数，返回 false。 步骤4：完整流程演示（以 n=2 为例） 初始化： seen 集合为空， n = 2 。 第一轮：n=2 不在 seen 中且不等于1。 将 2 加入 seen -> seen = {2} 。 计算 next：2² = 4 -> n = 4 。 第二轮：n=4 不在 seen 中且不等于1。 将 4 加入 seen -> seen = {2, 4} 。 计算 next：4² = 16 -> n = 16 。 第三轮：n=16 不在 seen 中且不等于1。 将 16 加入 seen -> seen = {2, 4, 16} 。 计算 next：1² + 6² = 1 + 36 = 37 -> n = 37 。 第四轮：n=37 不在 seen 中且不等于1。 将 37 加入 seen -> seen = {2, 4, 16, 37} 。 计算 next：3² + 7² = 9 + 49 = 58 -> n = 58 。 第五轮：n=58 不在 seen 中且不等于1。 将 58 加入 seen -> seen = {2, 4, 16, 37, 58} 。 计算 next：5² + 8² = 25 + 64 = 89 -> n = 89 。 第六轮：n=89 不在 seen 中且不等于1。 将 89 加入 seen -> seen = {2, 4, 16, 37, 58, 89} 。 计算 next：8² + 9² = 64 + 81 = 145 -> n = 145 。 第七轮：n=145 不在 seen 中且不等于1。 将 145 加入 seen -> seen = {2, 4, 16, 37, 58, 89, 145} 。 计算 next：1² + 4² + 5² = 1 + 16 + 25 = 42 -> n = 42 。 第八轮：n=42 不在 seen 中且不等于1。 将 42 加入 seen -> seen = {2, 4, 16, 37, 58, 89, 145, 42} 。 计算 next：4² + 2² = 16 + 4 = 20 -> n = 20 。 第九轮：n=20 不在 seen 中且不等于1。 将 20 加入 seen -> seen = {2, 4, 16, 37, 58, 89, 145, 42, 20} 。 计算 next：2² + 0² = 4 + 0 = 4 -> n = 4 。 第十轮：此时 n=4。我们发现 4 已经在集合 seen 中了（第二轮加入的）。 循环条件 n != 1 && n not in seen 不成立（因为4在seen中）。 退出循环。 判断 n=4，不等于1，所以返回 false。数字2不是快乐数。 通过这个循序渐进的讲解，你应该能清晰地理解如何利用哈希集合来检测循环，从而解决“快乐数”问题。