Q202 Happy Number

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

解题思路：

根据题意，最后结果为 1 是 happy number，返回 True，否则必定出现环，不是 happy number 返回 False。

在写代码的时候，happy number 的终止条件容易得到（循环过程中平方和等于1即可）。但是，不是 happy number 的终止条件不容易找到。

但是，发现一个规律：如果出现环，则这个环中必定出现 4 这个数字。比如5，循环结果依次是：

25，29，85，89，145，42，20，4，16，37，58，89，145，42，20，4......

其他不是 happy number 的也有这样的规律。因此，循环终止的条件就可以找到了。

Python实现：

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        while True:
            n = sum([int(ch)**2 for ch in str(n)])
            if n == 1: return True
            if n == 4: return False

a = 19
b = 8
c = Solution()
print(c.isHappy(a))  # True
print(c.isHappy(b))  # False

补充：

如果观察不到这个规律，我可能使用快慢指针解决是否有环的问题。慢指针 slow 每次只计算一次平方和，快指针 fast 每次计算两次平方和。如果快指针追上慢指针（fast = slow），且慢指针不为1，则代表有环，不是 happy number，否则为 happy number。

快慢指针的思路来源于判断链表是否有环的问题：Q141 Linked List Cycle。

关于快慢指针：

快慢指针可以解决这样的问题：

1. 判断链表是否有环（设置两个指针，慢指针每次走一步，快指针每次走两步，如果有环，两指针总会相遇）；
2. 求链表中点（设置两个指针，慢指针每次走一步，快指针每次走两步，当快指针走到链表尾，慢指针刚好到链表中点）；
3. 求链表倒数第n个数（设置两个指针，快指针先走n步，然后慢指针和快指针一起走，当快指针到达链表尾，慢指针刚好为倒数第n个数）；
4. 如果链表有环，求环的入口（设置两个指针，一个指针指向相遇点，一个指针指向链表头。每次各走一步，再次相遇的点就是环入口）。