Leetcode_202.快乐数_三种方法解决（普通方法解决，哈希表解决，循环链表的性质解决_快慢指针）

第一种方法：暴力解法

最暴力的思路就是直接使用循环往下一直计算，这样特别浪费时间，由于题目中说到可以无限循环，所以我们这里让其循环1e5次。
这道题的核心还是getNext()这个函数，要求返回当前数每个数字的平方和，主要就是将一个数字拆开，还是挺好想到的

暴力ac代码：

class Solution {
public:// 计算数字各位平方和int getNext(int y) {int result = 0;while (y) {int digit = y % 10;      // 获取最后一位数字result += digit * digit; // 平方后累加y /= 10;                 // 去掉最后一位}return result;}bool isHappy(int n) {// 设置最大迭代次数，避免无限循环int count= 1e5;while (count--) {n = getNext(n);if (n == 1) {return true;}}return false;}
};

第二种方法：哈希表

利用c++的STL容器
当n不等于1的时候，表示这个数字还得继续变换，故而循环条件设置为 n!=1
那么导致无限循环的原因是什么呢？
是因为在数字变换的过程中，一定又变换回来了一次
例如：2

1. 2 ²=4;
2. 4²=16 ;
3. 1²+6²=37;
4. 3²+7²=58;
5. 5²+8²=89;
6. 8²+9²=145;
7. 1²+4²+5²=42
8. 4²+2²=20;
9. 2²+0²=4;

由此可见，如果不是快乐数的话，那么它的变换是一定为环的。
那当我们设计循环的时候，可以查询哈希表，如果这次变换的值之前在哈希表中出现过，那么就证明会陷入循环，直接返回false表示不是快乐数，如果没有出现过，那就加入哈希表。
判断完之后，更新n的值
如果可以走出循环那么就证明 n== 1，表示是快乐数

哈希表ac代码:

class Solution {
public:int getNext(int y) {int result = 0;while (y) {int digit = y % 10;result += digit * digit;y /= 10;}return result;}bool isHappy(int n) {unordered_set<int> seen; // 记录已经出现过的数字while (n != 1) {// 如果当前数字已经出现过，说明进入循环，不是快乐数if (seen.find(n) != seen.end()) {return false;}seen.insert(n); // 记录当前数字n = getNext(n); // 计算下一个数字}return true; // 最终得到1，是快乐数}
};

第三种方法：根据循环链表的性质(快慢指针)

当链表成环，慢指针总会遇见快指针。
根据这个性质，我们可以得到这个题的第三种解法
这个写法主要讲一下while循环
当本次循环快指针不为 1 时，代表还没有找到快乐数，所以要继续循环变换寻找，一旦快指针等于 1 ,就代表找到了，此时退出循环，直接返回true，当快指针不为1 时，快指针变换两次，慢指针变换一次，变换完毕之后进行判断，如果 快指针等于慢指针 并且 快指针不等于 1 ，就证明快慢指针相遇了，数字 n 的变换过程存在一个环，所以一定不是快乐数，直接返回false;

class Solution {
public:// 计算数字各位平方和int getNext(int y) {int result = 0;while (y) {int digit = y % 10;      // 获取最后一位数字result += digit * digit; // 平方后累加y /= 10;                 // 去掉最后一位}return result;}bool isHappy(int n) {int fast=n,slow=n;while(fast!=1){fast=getNext(getNext(fast));//快指针走两步slow=getNext(slow);//慢指针走一步if(fast==slow && fast!=1){return false;}}//退出循环代表快指针走到了1的位置return true;}
};