LeetCode(Math)Happy Number

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:

Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

思路：关键在于怎么避免死循环，首先怎么才能进入死循环呢，其实通过计算方式可以看出，如果当前计算的数经过题目给定的算法计算后在未来的某一步再次得到了当前的值，则会陷入死循环，重复从这个数开始计算到这个数，比如如果输入为2的话：
$$
2^2=4
$$

$$
4^2=16
$$

$$
1^2+6^2=37
$$

$$
3^2+7^2=58
$$

$$
5^2 + 8^2 = 89
$$

$$
…
$$

$$
2^2+0^2=2
$$

回到2以后又开始了下一轮重复的计算，永远不能跳出，如何避免这种情况出现呢，容易想到利用set的不可重复放置相同元素的特性，将该条件作为循环是否终止的条件即可，代码如下：

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