LeetCode 202 快乐数：快慢指针解法详解
在数学的奇妙花园里，有一种特殊的数字被赋予了"快乐"的称号。快乐数（Happy Number）就像一位在数字迷宫中寻找出口的旅人，它遵循着特定的变换规则，一步步走向最终的归宿——1。
快乐数的定义：对于一个正整数，如果将其各位数字的平方和不断进行替换，最终能够得到 1，那么这个数就被称为快乐数。反之，如果陷入一个不包含 1 的循环，那么这个数就是不快乐的。
让我们以 19 为例，展开这段数字的奇妙旅程：
19 → 1² + 9² = 82
82 → 8² + 2² = 68
68 → 6² + 8² = 100
100 → 1² + 0² + 0² = 1
瞧！经过 4 步变换，19 最终到达了幸福的终点——1，因此它是一个快乐数。
解题思路：从数字到链表的思维转换
链表思维的巧妙应用
虽然表面上我们处理的是数字，但如果我们把每个数字看作链表中的一个节点，把数字变换规则看作指向下一个节点的指针，那么快乐数问题就转化为了链表判环问题！
19 → 82 → 68 → 100 → 1 → null
快慢指针：龟兔赛跑的智慧
在链表判环问题中，快慢指针算法是一种经典且高效的解决方案。我们可以让两个指针以不同的速度遍历这个"数字链表"：
- 慢指针（p）：每次计算一次数字变换
- 快指针（q）：每次计算两次数字变换
如果存在环（即数字不快乐），快慢指针终将相遇；如果数字快乐，快指针会率先到达 1。
算法实现：C++代码解析
关键函数：数字变换
// 计算数字 n 的下一个变换结果
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 = getNext(slow); // 慢指针走一步
fast = getNext(getNext(fast)); // 快指针走两步
}
return fast == 1; // 判断快指针是否到达 1
}
数学深度：数字会无限增大吗？
一个自然的疑问是：在变换过程中，数字会不会变得越来越大，最终无限增长？让我们通过数学分析来解答这个问题。
对于一个 m 位数 n，其各位数字平方和的最大值为 81m（当所有位都是 9 时）。而：
- 当 m=3 时，最大和为 243（3×81），远小于 999
- 当 m=4 时，最大和为 324，远小于 9999
事实上，对于任何大于 3 位的数字，经过一次变换后数字都会变小。因此，数字不会无限增大，最终要么收敛到 1，要么进入一个有限的循环。
快乐数的性质与统计
快乐数有一些有趣的性质：
- 所有不快乐数最终都会进入循环：4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
- 1 到 100 之间的快乐数有：
| 快乐数 | 变换步骤 |
|---|---|
| 1 | 0 |
| 7 | 5 |
| 10 | 1 |
| 13 | 2 |
| 19 | 4 |
| … | … |
复杂度分析与优化
时间复杂度：O(log n)，因为每次变换都会显著减少数字的大小（对于大数而言）。
空间复杂度：O(1)，因为我们只使用了常数个额外空间。
扩展思考
- 快乐数的密度：随着数字增大，快乐数的比例会如何变化？
- 快乐素数：既是素数又是快乐数的数字，如 7、13、19 等。
- 连续快乐数：是否存在连续的快乐数？（例如 31 和 32 都是快乐数）
快乐数问题不仅是一个有趣的编程练习，更是数学之美的一个缩影。它展示了如何将看似简单的数字变换转化为深刻的算法问题，并通过巧妙的思维转换找到高效的解决方案。