双指针——快乐数
一.题目描述
202. 快乐数 - 力扣（LeetCode）
二.题目解析
我们要判断一个数是不是快乐数要通过它的三个性质来进行判断。这个数会一直变化，由它的各个位的平方和重新构成这个数。如果这个数在变化的过程中变成了1，那么就是快乐数；如果陷入了循环，一直变不到1，就说明不是快乐数。
所以，对于一个数n来说有两种情况：1、在进行若干次变换后变成了1；2、在进行若干次变换之后进入了循环。
但其实，我们可以将第一种也归为是进入循环的一种，只不过每一个位置都是1.
三.算法原理
我们看到上面的情况图有没有联想到之前学习链表的一道题——带环链表。判断一个链表是否带环，我们利用了快慢双指针。这里我们也可以使用快慢指针来实现：
这里其实是在模拟带环链表的性质。我们让slow每次变换一次，fast变换两次即可。
扩展：
这道题之所以简单是因为题目已经告诉我们一定会进行循环，但是如果没有这句话呢？有没有可能n一直变换下去，不会进入循环？
答案是不会的！
四.代码实现
因为我们需要频繁求一个数的每个位的平方和，所以我们将其写成一个函数。
int getSquare(int n)
{
int ans = 0;
while (n)
{
int index = n % 10;
ans += index * index;
n /= 10;
}
return ans;
}
bool isHappy(int n)
{
int slow = n;
int fast = getSquare(n);
while (fast != slow)
{
slow = getSquare(slow);
fast = getSquare(getSquare(fast));
}
return slow == 1;
}