编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

示例 2：

输入：n = 2
输出：false

提示：

• 1 <= n <= 2^31 - 1

---

拿到一个全新的概念：快乐数，先来找个规律。

从举例计算中可以发现，快乐数通过有限步骤最终可以得到 1 ，和题目描述相同。

而痛苦数有一个规律，在计算的过程中，他们不是在循环里（如图2、3、4行），就是在去往循环的路上（如图5、6行）。

所以不要让任何人或事困住你，那将变得不幸，跳出循环，你就是快乐的。

到这里这道题就有两个解决方向：

• 暴力法，我们能完全枚举出痛苦数循环里的所有数，因此在计算过程中判断是否得到了痛苦循环中的数即可。
• 找环。----> 问题被同化成：链表中是否存在环。

方法一：暴力法

我们可以找到循环：

4→16→37→58→89→145→42→20→4

有且仅有这样一个循环，可以验证所有痛苦数都会最终进入这个循环。

所以将这组数保存下来，计算过程中对每个结果进行验证，如果结果在这些数中就返回false。否则不会进入死循环。

class Solution {
public:bool isHappy(int n) {unordered_set<int> pain = {4,16,37,58,89,145,42,20,4};while(n != 1){if(pain.contains(n)){return false;}n = cal(n); }return true;}int cal(int n){int result = 0;while(n > 0){int temp = n % 10;n /= 10;result += temp * temp;}return result;}
};

进一步的，在这种思路下，还能找到进一步的规律，所有数都会在计算过程中的到个位数。

个位数中，1是快乐数（7也是，但7在计算中也能变成1）。而在上面的唯一循环中，有个位数4。

所以可以进一步修改代码：

class Solution {
public:bool isHappy(int n) {while (true) { int new = 0; while (n > 0) {int temp = n % 10;new += temp * temp; n /= 10; }if (new == 1) return true; if (new == 4) return false; n = new; }}
};

方法二：快慢指针

使用两个指针分别步长是 1 和 2，也就是计算下一个数，和接下来的第二个数。步长为 2 的为快指针。

如果 n 是快乐数，即没有循环，那么快指针最终会比慢指针先到达数字 1。

如果 n 是痛苦数，那么最终快指针和慢指针将在循环内的同一个数字上相遇。

class Solution {
public:bool isHappy(int n) {int slow = n;int fast = cal(n);while(fast != 1 && fast != slow){fast = cal(cal(fast));slow = cal(slow);}return fast == 1;}int cal(int n){int result = 0;while(n > 0){int temp = n % 10;n /= 10;result += temp * temp;}return result;}
};