编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1示例 2：
输入：n = 2
输出：false提示：
1 <= n <= 2^31 - 1
解题思路：快慢指针
一开始可能会想，这道题还能和双指针扯上关系？没想到还真是，只需要我们将其模型抽象出来即可！
根据题目的定义，无非就是两种情况，要么最后得到是 1，要么最后就是无限循环下去，无限循环下去，其实我们就可以理解为是一个环形，不断的在重复着之前的数字，那对于最后得到的是 1 的情况，其实也是可以抽象为环形的，因为 1 怎么分解最后还是得到 1，相当于 1 一直在循环，如下图所示：
也就是说，走到环里面了，如果此时能知道环里面元素是 1，那么说明是返回 true 的，如果不是 1 的话，说明返回 false。
那问题来了，我们如何得到哪里是环❓❓❓
这时候就借用到了快慢指针来解决了，大家肯定都做过一道链表的判断环题目，用的就是快慢指针，通过快慢指针在环中的不断循环，加上其步伐的快慢，最后两个指针判断是否相等，相等说明就是相遇了，就达到是否在环内的目的！
所以我们只需要用快慢指针，最后肯定快指针先到环内循环，而慢指针则后到环内，在环内循环后两者最后肯定会相遇，判断相遇时候的元素是否为 1 即可判断返回值！
那问题又来了，那是因为在链表题中对于每个节点都有一个指针，而这里不一样啊，快慢指针到底指向什么❓❓❓
我们前面说过，双指针还是快慢指针，它们都不一定是语言级别上的指针，更多意义上表示的是一个指向，根据题目来，因为每一次都要拿这个数的每个位置上的数求平方和，那么也就说明，一次平方和，其实就是下一个位置，那我们就让慢指针指向一次平方和的结果，让快指针指向两次平方和的结果，不就达到了类似链表那样子的快慢了吗，对不对！
这样子问题就解决了！
这里再补充一点知识，有没有可能这道题的结果，不会构成环，而是一直不断增大❓❓❓
答案是必须会构成环！这里其实也很好推导，用到一个鸽巢原理（抽屉原理）：其实就是说，现在有 n 个巢，有 n+1 只鸽子，那么就能推出此时至少有一个巢，里面的鸽子数量要大于 1。
为什么呢，因为如果我们如果平均分的话，每个巢就先都有一只鸽子，此时还剩下一只鸽子，所以随便怎么放的话都会至少有一个巢要大于一只鸽子的数量！
说这个有什么用呢，当然有用！根据题目给的数据范围，也就是 2^31 - 1，其大小差不多为 2147483647，也就是 int 类型的范围，此时我们为了便于计算，干脆将其放大到 9999999999，也就是十位数中的最大值！
此时根据题目的平方和计算，可以得到 9999999999 每一位的平分也就是 9 的平方就是 81，一共有十位数，所以就是 810，也就是说，计算平方和之后的范围就在 [1, 810] 之间了，也说明 2147483647 肯定也在 [1, 810] 之间。
那么此时这个区间相当于是巢，一共有 810 个巢，假设此时一个数字通过 810 次计算平方和之后得到了 810 个在 [0, 810] 区间内不重复的数字，此时只要再多算一次，也就是第 811 次，就会出现环形结构！
也就是说，不可能出现无环、一直循环下去的情况，最多计算超过 810 次了之后，也是必定会出现的环的！
接下来的代码也不难了，无非就是求一个平方和罢了，代码如下所示：
class Solution {
public:
int cal(int n) // 获取每个位置上数字的平方和
{
int ret = 0;
while(n)
{
ret += pow(n % 10, 2);
n /= 10;
}
return ret;
}
bool isHappy(int n)
{
// 定义快慢指针
int slow = n, fast = cal(n);
while(slow != fast)
{
slow = cal(slow);
fast = cal(cal(fast));
}
return (slow == 1 ? true : false);
}
};