快乐数的定义
快乐数（Happy Number）是一个有趣的数学概念。对于一个正整数，如果将其各位数字的平方和不断进行替换，最终能够得到 1，那么这个数就被称为快乐数。反之，如果陷入一个不包含 1 的循环，那么这个数就是不快乐的。
以 19 为例：
19 → 1² + 9² = 82
82 → 8² + 2² = 68
68 → 6² + 8² = 100
100 → 1² + 0² + 0² = 1
经过 4 步变换，19 到达了终点 1，因此它是快乐数。
解题思路：链表思维转换
虽然处理的是数字，但我们可以把每个数字看作链表中的一个节点，变换规则看作指向下一个节点的指针。这样，快乐数问题就转化为了经典的链表判环问题。
如果不快乐，数字序列会进入循环；如果快乐，序列最终指向 1 并结束。
快慢指针策略
在链表判环中，快慢指针（Floyd's Cycle Detection）是高效且节省空间的方案。
- 慢指针（slow）：每次走一步（一次变换）。
- 快指针（fast）：每次走两步（两次变换）。
如果存在环，快慢指针终将相遇；如果数字快乐，快指针会率先到达 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
}
这里有个细节要注意：快指针初始位置设为 getNext(n)，是为了让它在第一次循环前就已经领先一步，避免初始状态 slow == fast 直接退出循环。
数学深度：数字会无限增大吗？
一个自然的疑问是：在变换过程中，数字会不会变得越来越大，最终无限增长？
对于一个 m 位数 n，其各位数字平方和的最大值为 81m（当所有位都是 9 时）。
- 当 m=3 时，最大和为 243（3×81），远小于 999。
- 当 m=4 时，最大和为 324，远小于 9999。
事实上，对于任何大于 3 位的数字，经过一次变换后数字都会变小。因此，数字不会无限增大，最终要么收敛到 1，要么进入一个有限的循环。这保证了算法必然终止。
复杂度分析与优化
- 时间复杂度：O(log n)。因为每次变换都会显著减少数字的大小（对于大数而言），且循环次数有限。
- 空间复杂度：O(1)。我们只使用了常数个额外变量，没有使用哈希表存储历史路径。
扩展思考
- 快乐数的密度：随着数字增大，快乐数的比例会如何变化？
- 快乐素数：既是素数又是快乐数的数字，如 7、13、19 等。
- 连续快乐数：是否存在连续的快乐数？（例如 31 和 32 都是快乐数）
快乐数问题不仅是一个有趣的编程练习，更是数学之美的一个缩影。它展示了如何将看似简单的数字变换转化为深刻的算法问题，并通过巧妙的思维转换找到高效的解决方案。