Happy Number

题目链接：https://leetcode.com/problems/happy-number/

这道题看上去很简单，如果用hashtable的话，不少童鞋应该都能做出来。只要想明白一件事儿，循环结束的条件：要么当前的数字为1，要么当前的数字曾经出现过。（至于为什么一定会出现循环，额，数学家们已有讨论，可以参考这个链接里的内容和其他链接 http://mathworld.wolfram.com/HappyNumber.html。 不过简单的说，就是按这种规律一直运算，结果总会出现0, 1, 4, 16, 20, 37, 42, 58, 89, 145 这十个数中的一个）好了，这样子逻辑和明了，代码如下。

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> visited;
        int cur = n;
        while(!(cur == 1 || visited.find(cur) != visited.end())) {
            visited.insert(cur);
            int temp = 0;
            while(cur) {
                temp += (cur % 10) * (cur % 10);
                cur = cur / 10;
            }
            cur = temp;
        }
        return cur == 1;
    }
};

但其实这道题还有一种不需要hashtable的方法，就是使用Floyd Cycle detection algorithm。相信很多人在做linkedlist cycle detection的时候都用过这个方法，仔细一想，这个方法确实可以用在这道题上哦。这个方法是这样的，设置两个指针，slow和fast，然后每次slow走一步，fast走两步，（在这道题里就是slow做一次求平方和的运算，fast做两次），直到fast与slow相等或者fast为1为止。对于这个算法的简单证明大家可参考wiki：http://en.wikipedia.org/wiki/Cycle_detection或者直接找原paper。对于这个算法在linkedlist中的解释，可以参考这个博文：http://www.cnblogs.com/hiddenfox/p/3408931.html

class Solution {
public:
    bool isHappy(int n) {
        int slow = n;
        int fast = sqrtSum(n);
        while(fast != 1 && slow != fast) {
            fast = sqrtSum(fast);
            if(fast != 1 && slow != fast) {
                fast = sqrtSum(fast);
                slow = sqrtSum(slow);
            }
        }
        return fast == 1;
    }
    
    int sqrtSum(int n) {
        int sum = 0;
        while(n) {
            sum += (n % 10) * (n % 10);
            n = n / 10;
        }
        return sum;
    }
};

由这道题我们可以想到在进行与循环有关的问题是，Floyd的这个算法应该率先考虑一下。