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