Happy Number

这里最简单的想法就是按照题目的逻辑重复模拟此过程，同时利用set查重，如果有重复值可以直接判错了

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        checker = set()
        while n not in checker and n != 1:
            checker.add(n)
            tmp = 0
            while n:
                n, rem = divmod(n, 10)
                tmp += (rem ** 2)
            n = tmp

        return n == 1

另外这里我们可以观察到，happy number的实质是重复的进行这种运算最后会到达1而不是在某些中间值里面陷入死循环，明显的可以看到这和linked list cycle的特性非常一样，这里我们可以使用Floyd cycle detection算法了（判环算法的总称），Python没有do while形式的循环，这里先用c++写

class Solution {
public:
    int squareSum(int n) {
        int result = 0;
        while (n > 0) {
            int tmp = n % 10;
            result += (tmp * tmp);
            n /= 10;
        }
        return result;
    }

    bool isHappy(int n) {
        int slow = n;
        int fast = n;

        do {
            slow = squareSum(slow);
            fast = squareSum(fast);
            fast = squareSum(fast);
        } while (slow != fast);

        if (slow == 1 || fast == 1) {
            return true;
        }

        return false;
    }
};

Python版

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        slow, fast = self.squareSum(n), self.squareSum(self.squareSum(n))
        while slow != fast:
            slow = self.squareSum(slow)
            fast = self.squareSum(self.squareSum(fast))

        return True if slow == 1 or fast == 1 else False

    def squareSum(self, n):
        result = 0
        while n:
            n, rem = divmod(n, 10)
            result += (rem ** 2)
        return result