双指针——快乐数

一.题目描述

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;
}