【算法——双指针】LeetCode 202 快乐数

题目描述：

思路：快慢指针

看到循环，我就想起了快慢指针的方法，从题目我们可以看出，我们需要模拟一个过程：不断用当前的数去生成下一个数，生成的规则就是将当前数的各位的平方累加；得到的结果要么就是1，那么初始的这个数为快乐数；要么就是一个无限循环。

关键在于我们并不能让程序无限循环下去，而是要去判断什么时候将陷入无限循环。如果新生成的数已经出现过了，那么必然将陷入循环，在这几个数的生成过程中的循环，如示例2：

进入循环后我们可以使用 “快慢指针” 思想，找出循环：“慢指针” 每次走一步，“快指针” 每次走两步，当二者相等时，即为一个循环周期。最后，判断是不是因为 1 引起的循环，是的话就是快乐数，否则不是快乐数。

代码：

class Solution {
    int NextN(int n)    //返回n这个数每一位上的平方和(即这个数的下一位)
    {
        int sum = 0;
        while(n != 0)
        {
            int t = n % 10;
            sum += t * t;
            n /= 10;
        }
        return sum;
    }
public:
    bool isHappy(int n) {
        int slow = n;
        int fast = NextN(n);
        while(slow != fast)
        {
            slow = NextN(slow);
            fast = NextN(NextN(fast));
        }
        return slow == 1;
    }
};