202. 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

1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

一个定义新运算的问题，所谓“幸运数”的定义很简单，一个数各位的平方和组成一个新数字，对新数字计算平方和，如果为1，则是幸运数，否则继续运算。

题目要求我们对幸运数进行判断，那么如何判断呢？我们可以将要判断的数字的各位进行分离，然后计算平方和，再进行组合之后，判断其值是否为1.

但这个思路要实现起来比较麻烦，而且属于暴力破解，能不能总结出一个关于幸运数的一般规律呢？

我们可以在纸上模拟幸运数判断的过程，如果一个数在题目定义的计算过程中，某两次的结果是相同的且不是1，那么就说明出现了周期现象，也就是说这个数无论经过多少轮运算，都不会得到1这个结果，所以就不会是幸运数。

但还有一个问题需要解决，如果一个数不是幸运数，那么会不会出现周期无穷大的情况呢？如果出现了这种情况，那么上述算法就会出现错误，在讨论区我找到了这个问题的证明，原文证明非常详细，在此就不再赘述了，链接如下:

算法证明

证明得到的结论是，如果一个数不是幸运数，那么一定会有一个常数T，使得某两个间隔为T的运算结果相等。

所以我们的思路是:用一个unordered_set存储每一次的运算结果，如果该结果不在set中，则将其插入;若存在，则判断其是否为1，为1则是幸运数，否则不是。 代码如下:

/*solution1 use unordered_set,7ms*/
class Solution {
private:
    int divideThenSum(int n){
        int tmp=n,sum=0;
        while(n){
            tmp=n%10;
            sum+=tmp*tmp;
            n=n/10;
        }
        return sum;
    }

public:
    bool isHappy(int n) {
        unordered_set<int> hash;
        int res=n;
        while(true){
            res=divideThenSum(res);
            if(hash.count(res)==0)
                hash.insert(res);
            else
                return res==1;
        }
    }
};

AC之后又进行了更深一步的思考，既然是周期现象，那么也可以尝试一下Floyd Cycle Algorithm，即我们在判断链表是否有环时使用的算法(快慢指针法),代码如下:

/*solution 2,use Floyd cycle algorithm,4ms*/
class Solution {
private:
    int divideThenSum(int n){
        int tmp=n,sum=0;
        while(n){
            tmp=n%10;
            sum+=tmp*tmp;
            n=n/10;
        }
        return sum;
    }

public:
    bool isHappy(int n) {
        int slow=n,fast=n;
        do{
            slow=divideThenSum(slow);
            fast=divideThenSum(divideThenSum(fast));
        }while(slow!=fast);
        return slow==1;
    }
};