【算法——双指针】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;}
};

结果：