LeetCode 202. 快乐数
在算法的世界里，有些数字拥有特殊的'命运'。快乐数（Happy Number）的定义很简单：对于一个正整数，将其各位数字的平方和不断进行替换，如果最终能得到 1，它就是快乐数；如果陷入一个不包含 1 的循环，就是不快乐的。
以 19 为例，它的旅程是这样的：
19 → 1² + 9² = 82
82 → 8² + 2² = 68
68 → 6² + 8² = 100
100 → 1² + 0² + 0² = 1
经过 4 步变换，它到达了终点。而如果不快乐，数字就会像迷宫一样绕圈走不出来。
核心思路：从数字到链表
虽然处理的是数字，但我们可以换个角度思考。如果把每个数字看作链表中的一个节点，把变换规则看作指向下一个节点的指针，那么判断一个数是否快乐，本质上就是检测链表中是否存在环。
- 快乐数：路径最终通向 1（相当于链表尾）。
- 不快乐数：路径进入死循环（相当于链表成环）。
既然转化为了链表判环问题，我们自然想到了经典的快慢指针算法（Floyd Cycle Detection Algorithm）。
让两个指针同时出发：
- 慢指针：每次走一步（计算一次平方和）。
- 快指针：每次走两步（计算两次平方和）。
如果存在环，快指针终将追上慢指针；如果不存在环（即快乐数），快指针会先到达 1。
C++ 代码实现
下面直接看核心逻辑的实现。这里不需要额外的哈希表来记录历史数字，空间效率非常高。
// 辅助函数：计算下一个数字
int getNext(int n) {
int sum = 0;
while (n > 0) {
int digit = n % 10; // 取出最后一位
sum += digit * digit; // 累加平方
n /= 10; // 去掉最后一位
}
return sum;
}
// 主函数：判断是否为快乐数
bool isHappy(int n) {
int slow = n;
int fast = getNext(n); // 快指针先走一步
// 当快指针未到 1 且快慢指针未相遇时继续
while (fast != 1 && slow != fast) {
slow = (slow);
fast = ((fast));
}
fast == ;
}
