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
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
解題思路：
根據(jù)題意，最后結(jié)果為 1 是 happy number，返回 True，否則必定出現(xiàn)環(huán)，不是 happy number 返回 False。
在寫代碼的時(shí)候，happy number 的終止條件容易得到（循環(huán)過(guò)程中平方和等于1即可）。但是，不是 happy number 的終止條件不容易找到。
但是，發(fā)現(xiàn)一個(gè)規(guī)律：如果出現(xiàn)環(huán)，則這個(gè)環(huán)中必定出現(xiàn) 4 這個(gè)數(shù)字。比如5，循環(huán)結(jié)果依次是：
25，29，85，89，145，42，20，4，16，37，58，89，145，42，20，4......
其他不是 happy number 的也有這樣的規(guī)律。因此，循環(huán)終止的條件就可以找到了。
Python實(shí)現(xiàn)：
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
補(bǔ)充：
如果觀察不到這個(gè)規(guī)律，我可能使用快慢指針解決是否有環(huán)的問(wèn)題。慢指針 slow 每次只計(jì)算一次平方和，快指針 fast 每次計(jì)算兩次平方和。如果快指針追上慢指針（fast = slow），且慢指針不為1，則代表有環(huán)，不是 happy number，否則為 happy number。
快慢指針的思路來(lái)源于判斷鏈表是否有環(huán)的問(wèn)題：Q141 Linked List Cycle。
關(guān)于快慢指針：
快慢指針可以解決這樣的問(wèn)題：
- 判斷鏈表是否有環(huán)（設(shè)置兩個(gè)指針，慢指針每次走一步，快指針每次走兩步，如果有環(huán)，兩指針總會(huì)相遇）；
- 求鏈表中點(diǎn)（設(shè)置兩個(gè)指針，慢指針每次走一步，快指針每次走兩步，當(dāng)快指針走到鏈表尾，慢指針剛好到鏈表中點(diǎn)）；
- 求鏈表倒數(shù)第n個(gè)數(shù)（設(shè)置兩個(gè)指針，快指針先走n步，然后慢指針和快指針一起走，當(dāng)快指針到達(dá)鏈表尾，慢指針剛好為倒數(shù)第n個(gè)數(shù)）；
- 如果鏈表有環(huán)，求環(huán)的入口（設(shè)置兩個(gè)指針，一個(gè)指針指向相遇點(diǎn)，一個(gè)指針指向鏈表頭。每次各走一步，再次相遇的點(diǎn)就是環(huán)入口）。
