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.

首先需要明确的一点，如果在等于1的时候不跳出，明显会陷入一个死循环（在为1时一直求）。而对于一个不可能等于1的数，我们来看一下它为何会陷入死循环，直觉可以猜到，对于一个死循环，一定是形成了一个环，导致无限的在这个环内踏步。
例如对于20，有20->4->16->37->58->89->145->42->20，可以看到我们又回到了二十，这样就陷入了循环。
再例如对于56,56->61->37->58->89->145->42->20，由上面的描述，在二十的入口形成了环。

所以问题就转换为了寻找环的入口，如果环的入口是1，那么这就是我们想要的happy number ，如果环的入口不是1，那么就不是我们想要的number。

可以使用快慢指针，也可以使用Set记录第一个重复的数就是入口。

使用快慢指针寻找环的入口

class Solution {
    public boolean isHappy(int n) {
        int slow = next_number(n);
        int fast = next_number(next_number(n));
        while(fast!=slow)
        {
            slow=next_number(slow);
            fast= next_number(next_number(fast));
        }
        if(slow==1)return true;
        else return false;
    }
    private int next_number(int n)
    {
        int result = 0 ;
        while(n>0)
        {
            int remain = n%10;
            result+=remain*remain;
            n=n/10;
        }
        return result ;
    }
}

使用Set寻找环的入口

class Solution {
    public boolean isHappy(int n) {
       HashSet<Integer> set = new HashSet<>();
       while(true)
       {
           if(n==1)return true;
           if(!set.contains(n))
           {
               set.add(n);
               int result = 0;
               while(n>0)
               {
                   int remain = n%10;
                   result+=remain*remain;
                   n=n/10;
               }
               n=result;
           }
           else
             return false;
       }
    }
    
}