Leetcode 202题 快乐数：数字世界中的奇妙旅程
Leetcode 202题 快乐数：数字世界中的奇妙旅程
视频地址
因为想更好的为大佬服务，制作了同步视频，这是Bilibili的视频地址
在数学的奇妙花园里，有一种特殊的数字被赋予了"快乐"的称号。快乐数（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
图1：快乐数的链表表示法。快乐数最终会指向1，然后结束；不快乐的数则会进入一个循环
快慢指针：龟兔赛跑的智慧
在链表判环问题中，快慢指针算法是一种经典且高效的解决方案。我们可以让两个指针以不同的速度遍历这个"数字链表"：
- 慢指针（p）：每次计算一次数字变换
- 快指针（q）：每次计算两次数字变换
如果存在环（即数字不快乐），快慢指针终将相遇；如果数字快乐，快指针会率先到达1。
算法实现：C++代码解析
关键函数：数字变换
// 计算数字n的下一个变换结果intgetNext(int n){int sum =0;while(n >0){int digit = n %10;// 获取最后一位数字 sum += digit * digit; n /=10;// 去掉最后一位数字}return sum;}快乐数判断主逻辑
boolisHappy(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 |
| … | … |
表1：部分快乐数及其到达1所需的步骤数
复杂度分析与优化
时间复杂度：O(log n)，因为每次变换都会显著减少数字的大小（对于大数而言）。
空间复杂度：O(1)，因为我们只使用了常数个额外空间。
扩展思考
- 快乐数的密度：随着数字增大，快乐数的比例会如何变化？
- 快乐素数：既是素数又是快乐数的数字，如7、13、19等。
- 连续快乐数：是否存在连续的快乐数？（例如31和32都是快乐数）
快乐数问题不仅是一个有趣的编程练习，更是数学之美的一个缩影。它展示了如何将看似简单的数字变换转化为深刻的算法问题，并通过巧妙的思维转换找到高效的解决方案。
