Leetcode 每日一题2 Happy Number

题意

题目链接：Happy Number

给一个数字，判断它是不是Happy Number。假如一个数是Happy Number，则可以通过不断取各数位的平方和得到1。而假如不是Happy Number，则会陷入循环，不会得到1。

思路

这道题的关键在于怎么知道发生了循环，并在发生循环的时候及时结束。弗洛伊德判圈法(Floyd Cycle detection algorithm)是可以在O(1)的空间复杂度和O(n)的时间复杂度内，判断是否发生循环的一种算法，其中n是循环的次数。其思想是维护两个指针，令它们一开始都指向最开始的位置，然后进行do while循环，让其中一个指针一次走两步，另一个一次走一步，直到两者相等，就可以判定存在圈。

这道题一定存在循环，Happy Number在找到圈的时候，指向的数为1，而非Happy Number指向的数非1，得解。

代码

class Solution {
public:
    bool isHappy(int n) {
        int slow, fast;
        slow = fast = n;
        do {
            slow = getSum(slow);
            fast = getSum(fast);
            fast = getSum(fast);
        } while (slow != fast);
        return slow == 1;
    }
    int getSum(int d) {
        int sum = 0;
        while (d) {
            int mod = d % 10;
            d /= 10;
            sum += mod * mod;
        }
        return sum;
    }
};