每日一练：【优先算法】双指针之快乐数（medium）

1. 题目链接：202. 快乐数

2. 题目描述及分析

对于一个正整数我们替换为它每个位置上数字的平方和，不断重复这个过程就如上图所示。

这里需要补充的是根据鸽巢定理，n个巢穴，n + 1个鸽子，，将鸽子都安排进巢穴，那么不管怎么安排，至少有一个有一个巢穴里面鸽数大于1，我们这里取一个超过int范围的9999999999，我们按照上诉操作进行一次，数值变为810，那么如果我们继续对810变形，我们就会发现在这个过程中出现的数在[1,810]这个范围，这就意味着如果我们对9999999999变形超过810次，那么就一定会出现与[1,810]中数值重复的数。

以此类推，这就意味着一个数，我们对其进行尽可量的变化，最终要么这个数变为1，要么这个数无线循环变化下去。

3. 算法原理

这题笔者采用的是快慢指针的做法，不过在正式完成这题之前，我们需要先了解一些前置知识。

首先存在两个指针fast、slow，fast一次走两步，slow一次走一步，那么，如果fast、slow遍历一个带环链表，fast、slow是否会相遇呢？结论是如果如果链表成环，fast与slow一定会成环，并且相遇的位置就是环的节点

我们可以看到L=(x-1)*C+C-N,因此，当head走完L的路程，mee会走完（X-1）圈回到fast、slow相遇的位置，再走C-N走到开始入环的第一个节点与head相遇。

至此我们所需要的前置知识完成（当然，对此有的读者会疑惑为什么fast速度一定要是slow的两倍，其他速度行不行，，限于那不是本文章的写作目的，笔者不详细展开讨论，对此有兴趣的读者，可以移步看这篇文章【初阶数据结构】链表经典OJ（8道））

回过头来我们发现这道题的计算过程就可以视作一个带环的链表（变为1的过程，可以视作1这个节点独自成环，1变化后还是1），因此，根据我们的前置知识，我们采用快慢指针来完成这道题目，fast一次走两步，slow一次走一步（指针这里只是一种抽象概率，大家不要被迷惑，我们这里可以通过fast一次计算两次，slow一次计算一次模拟。）

4.算法代码

class Solution {
public:
    int Sum(int num)//用来进行一次变化的函数
    {
        int s = 0;
        while(num)
        {
            s += pow(num % 10,2);
            num /= 10;
        }
        return s;
    }
    bool isHappy(int n) {
        int slow = Sum(n),fast = Sum(Sum(n));
        while(slow != fast)
        {
            slow = Sum(slow);//slow一次走一步
            fast = Sum(Sum(fast));//fast指针一次走两步
        }

        return slow == 1;
    }
};