一、题目介绍
我们需要判断一个正整数 n 是否为「快乐数」。
定义如下：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
- 如果结果为 1，则是快乐数；否则返回 false。
示例： 输入：n = 19 输出：true 解释：1² + 9² = 82 → 8² + 2² = 68 → 6² + 8² = 100 → 1² + 0² + 0² = 1
输入：n = 2 输出：false
提示：1 <= n <= 2³¹ - 1
二、快慢指针原理
这道题的核心在于检测是否存在循环。如果我们把每次计算平方和的过程看作链表的一个节点，那么最终结果要么收敛到 1（无环），要么进入一个死循环（有环）。
我们可以使用经典的 Floyd 判圈算法（快慢指针）来解决这个问题：
- 初始化：设置两个指针，slow 指向初始值 n，fast 指向第一次计算后的结果。
- 移动规则：在每一步中，slow 指针走一步（计算一次平方和），fast 指针走两步（连续计算两次平方和）。
- 相遇判断：由于存在循环，快指针最终一定会追上慢指针。此时若两者相遇的位置是 1，说明是快乐数；若相遇位置不是 1，说明陷入了非 1 的循环，不是快乐数。
这种方法不需要额外的哈希表来记录访问过的数字，空间复杂度仅为 O(1)。
三、代码实现
下面是完整的 Java 实现。为了逻辑清晰，我将计算平方和的逻辑封装成了一个辅助方法。
public class Solution {
// 计算各位数字的平方和
public int bitSum(int n) {
int sum = 0;
while (n != 0) {
int tmp = n % 10; // 取出最后一位
sum += tmp * tmp; // 累加平方
n /= 10; // 去掉最后一位
}
return sum;
}
public boolean isHappy(int n) {
int n;
bitSum(n);
(slow != fast) {
slow = bitSum(slow);
fast = bitSum(bitSum(fast));
}
fast == ;
}
}
