题目描述
编写一个算法来判断一个正整数 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
提示： 1 <= n <= 2³¹ - 1
思路分析
这道题的核心在于检测序列中是否存在环。如果我们不断计算各位数字的平方和，得到的新数列要么最终收敛到 1（快乐数），要么进入一个不包含 1 的循环（非快乐数）。
既然存在'循环'的可能性，我们自然联想到链表中的环检测问题。这里不需要显式地构建链表，而是将数值变换看作节点间的跳转关系。
快慢指针（Floyd 判圈算法） 是解决此类问题的经典方案：
- 慢指针每次走一步：计算一次平方和。
- 快指针每次走两步：连续计算两次平方和。
- 如果存在环，快指针最终一定会追上慢指针。
- 当两者相遇时，检查当前值是否为 1。如果是，说明进入了以 1 为终点的循环（即 1->1）；如果不是，说明陷入了死循环。
这种方法的优势在于空间复杂度仅为 O(1)，无需使用哈希表记录历史访问过的数字，非常适合处理大范围的整数输入。
代码实现
下面是 Java 语言的完整实现。为了保持逻辑清晰，我将计算平方和的逻辑封装成了一个辅助方法。
public class Solution {
// 计算各位数字的平方和
private 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 slow = n;
int fast = bitSum(n);
// 快慢指针移动，直到相遇
while (slow != fast) {
slow = bitSum(slow);
fast = bitSum(bitSum(fast));
}
// 相遇点如果是 1，则是快乐数
return fast == 1;
}
}
关键点说明：
- 初始化差异：注意
fast初始化为bitSum(n)而不是n。这是为了确保在第一次循环前，快指针已经领先一步，避免在n=1的特殊情况下直接跳过循环判断（虽然逻辑上slow==fast也能处理，但分开初始化更符合 Floyd 算法的常规直觉）。 - 边界情况：当
n=1时，slow=1,fast=1，循环不执行，直接返回true，符合定义。 - 性能：由于数字平方和增长有限，对于任意正整数，其变换后的值很快就会落入一个较小的范围内，因此循环次数不会太多，时间复杂度可视为 O(log n) 级别。
