1.题目链接
202. 快乐数 - 力扣（LeetCode）
https://leetcode.cn/problems/happy-number/submissions/609206400/
2.题目描述
编写⼀个算法来判断⼀个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于⼀个正整数，每⼀次将该数替换为它每个位置上的数字的平⽅和。
- 然后重复这个过程直到这个数变为 1，也可能是⽆限循环但始终变不到 1 。
- 如果这个过程 结果为 1 ，那么这个数就是快乐数。
- 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
⽰例 1：
- 输⼊： n = 19
- 输出： true
解释：
- 19 -> 1 * 1 + 9 * 9 = 82
- 82 -> 8 * 8 + 2 * 2 = 68
- 68 -> 6 * 6 + 8 * 8 = 100
- 100 -> 1 * 1 + 0 * 0 + 0 * 0 = 1
⽰例 2：
- 输⼊： n = 2
- 输出： false
解释：（这⾥省去计算过程，只列出转换后的数）
- 2 -> 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> 16
- 往后就不必再计算了，因为出现了重复的数字，最后结果肯定不会是 1
3.算法思路
该算法用于判断一个数是否为“快乐数”（即通过反复计算各位平方和最终能得到 1 的数）。其核心思想是 快慢指针法，通过高效检测循环避免无限迭代，具体步骤如下：
1. 计算平方和的辅助函数
-
功能：
SunOfSquares(int n)计算整数n每一位的平方和。 -
实现：
-
通过循环取
n的末位数字（n % 10），累加其平方值。 -
移除末位（
n /= 10），直到n变为 0。
-
-
示例：
n = 19→ 1² + 9² = 1 + 81 = 82。
2. 快慢指针检测循环
-
初始化：
-
slow初始化为n（每次走一步）。 -
fast初始化为SunOfSquares(n)（每次走两步）。
-
-
循环条件：
-
slow != fast时持续移动指针： -
slow移动一步：计算一次平方和。 -
fast移动两步：连续计算两次平方和。
-
-
终止条件：当
slow和fast相遇时，说明存在循环或已到达 1。
3. 判断结果
-
若相遇时
slow == 1，说明最终收敛到 1，是快乐数，返回true。 -
若相遇时
slow != 1，说明进入非 1 的循环，返回false。
算法关键点
-
快慢指针的优势：
无需额外存储空间（如哈希表），空间复杂度为 O(1)。快指针的速度是慢指针的两倍，确保在存在循环时快速相遇。 -
数学依据：
根据弗洛伊德循环检测算法，快慢指针必然在环内相遇。若结果为 1，则后续所有平方和均为 1，形成“自环”。 -
边界处理：
当输入为 1 时，直接跳过循环并返回true，保证正确性。
示例分析
-
输入：
n = 19-
过程：
19 → 82 → 68 → 100 → 1 -
快慢指针在 1 处相遇，返回
true。
-
-
输入：
n = 2-
过程：
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4（进入循环） -
快慢指针在 4 处相遇，返回
false。
-
复杂度
-
时间复杂度：O(n)，其中
n为到达循环或 1 的步数。快指针加速了循环检测。 -
空间复杂度：O(1)，仅使用固定空间存储指针。
4.代码实现
class Solution
{
public:// 定义函数 SumOfSquares 求 n 每一位数的平方和int SunOfSquares(int n){int sum = 0;while(n){int temp = n % 10;sum += temp * temp;n = n / 10;}return sum;}bool isHappy(int n) {int slow = n, fast = SunOfSquares(n);while(slow != fast){slow = SunOfSquares(slow);fast = SunOfSquares(SunOfSquares(fast));}return slow == 1;}
};
