题目

力扣题目

判断一个正整数 n 是否为快乐数。每一轮将当前数字替换为它各位数字的平方和；如果最终变为 1，则它是快乐数。如果过程进入循环且始终无法到达 1，则不是快乐数。

示例 1：

Text
输入：n = 19
输出：true

19 → 1² + 9² = 82
82 → 8² + 2² = 68
68 → 6² + 8² = 100
100 → 1² + 0² + 0² = 1

示例 2：

Text
输入：n = 2
输出：false

提示：

  • 1 <= n <= 2^31 - 1

考察内容

  • 拆分整数的每一位
  • 计算各位数字的平方和
  • 使用哈希集合检测重复状态
  • 有限状态序列与循环
  • 快慢指针判环的替代思路

解题思路

计算下一个数字

反复对 num 取模和整除：

  • digit = num % 10 取得最后一位；
  • 将 digit * digit 累加到结果；
  • num /= 10 删除最后一位。

哈希集合检测循环

计算过程只有两种结局：

  1. 最终到达 1，说明是快乐数；
  2. 某个数字再次出现，之后的变化过程也会完全重复，说明进入循环，不可能再到达 1。

因此使用哈希集合 seen 保存已经出现过的数字。每轮先尝试将当前数字加入集合：

  • 插入成功：当前状态第一次出现，继续计算；
  • 插入失败：当前状态重复，已经形成环，返回 false。

以 19 为例：

19→82→68→100→119 \rightarrow 82 \rightarrow 68 \rightarrow 100 \rightarrow 1

以 2 为例，过程最终会再次回到 4：

2→4→16→37→58→89→145→42→20→42 \rightarrow 4 \rightarrow 16 \rightarrow 37 \rightarrow 58 \rightarrow 89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4

⤢ 打开

为什么过程一定会结束或成环

即使 n 很大，各位平方和也会迅速缩小。例如一个 10 位整数的各位平方和最多为 10×92=81010 \times 9^2 = 810。此后状态只会在有限范围内变化，所以最终一定到达 1 或重复某个状态。

  • 时间复杂度：通常记为 O(log⁡n)O(\log n)，一次转换需要处理数字的位数，后续状态数量有限
  • 空间复杂度：O(log⁡n)O(\log n)，用于保存出现过的状态；在整数范围内也可视为常数

快慢指针

也可以把“计算各位平方和”看成链表的 next 函数，使用快慢指针判断是否存在环。若快指针到达 1 则是快乐数；若快慢指针相遇且值不是 1，则进入了非快乐环。该写法可将额外空间降为 O(1)O(1)。

代码演示

C++
bool isHappy(int n) {
    auto nextNumber = [](int num) {
        int sum = 0;
        while (num > 0) {
            int digit = num % 10;
            sum += digit * digit;
            num /= 10;
        }
        return sum;
    };

    std::unordered_set<int> seen;

    while (n != 1 && seen.insert(n).second) {
        n = nextNumber(n);
    }

    return n == 1;
}

易错点

  • 没有检测循环：只写 while (n != 1) 会在非快乐数上无限循环。
  • 把各位数字直接相加：题目要求累加每一位的平方。
  • 拆位后忘记更新数字：每轮需要执行 num /= 10，否则内部循环无法结束。
  • 在集合中记录了无关值：应记录完整的状态数字，而不是单独的某一位。
  • 误解 insert(n).second：返回 true 表示首次插入；返回 false 表示数字已经存在，检测到循环。
  • 担心平方和溢出：在 32 位正整数范围内，各位平方和很小，使用 int 足够。

总结

快乐数本质上是一个确定状态转移问题。每个数字只有唯一的下一个状态，因此重复状态意味着之后必然无限循环。使用哈希集合记录访问历史，就能清晰地区分“到达 1”和“进入环”两种结局。

相关题目

    1. 环形链表
    1. 环形链表 II
    1. 各位相加
    1. 寻找重复数