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:

    1. Input: 19
    2. Output: true
    3. Explanation: 
    4. 12 + 92 = 82
    5. 82 + 22 = 68
    6. 62 + 82 = 100
    7. 12 + 02 + 02 = 1

    题意

    判断一个数字是否为”Happy Number”：将一个数字各位取出并求其平方之和，得到的和作为新的数字继续重复操作，如果最后能够得到数字1则说明原数字为”Happy Number”；如果最后陷入循环但得不到1则说明原数字不是”Happy Number”。

    思路

    难点在于对非”Happy Number”循环的判断。

    最简单的方法是直接用HashSet记录每一个出现过的数字，当某一个数字再次出现且不为1时，说明陷入循环，为非”Happy Number”。

    根据之前的刷题经验，这类判断循环的问题可以使用快慢指针来解决：当快指针追上慢指针且快指针不为1时，说明陷入循环，为非”Happy Number”。

    找规律。试了一下非”Happy Number”的循环中总包含了一个”4”，提交代码后发现的确是这样，但不会严格的证明。

    代码实现 - hash

    1. class Solution {
    2.     public boolean isHappy(int n) {
    3.         Set<Integer> hash = new HashSet<>();
    5.         while (n != 1) {
    6.             hash.add(n);
    7.             int m = 0;
    8.             while (n != 0) {
    9.                 m += (n % 10) * (n % 10);
    10.                 n /= 10;
    11.             }
    12.             if (hash.contains(m)) {
    13.                 return false;
    14.             }
    15.             n = m;
    16.         }
    18.         return true;
    19.     }
    20. }

    代码实现 - Two Pointers

    1. class Solution {
    2.     public boolean isHappy(int n) {
    3.         int slow = n, fast = n;
    5.         while (fast != 1) {
    6.             slow = nextInt(slow);
    7.             fast = nextInt(nextInt(fast));
    8.             if (fast == slow && fast != 1) {
    9.                 return false;
    10.             }
    11.         }
    13.         return true;
    14.     }
    16.     private int nextInt(int n) {
    17.         int sum = 0;
    18.         while (n != 0) {
    19.             sum += (n % 10) * (n % 10);
    20.             n /= 10;
    21.         }
    22.         return sum;
    23.     }
    24. }

    代码实现 - 找规律

    1. class Solution {
    2.     public boolean isHappy(int n) {
    3.         while (n != 1 && n != 4) {
    4.             int m = 0;
    5.             while (n != 0) {
    6.                 m += (n % 10) * (n % 10);
    7.                 n /= 10;
    8.             }
    9.             n = m;
    10.         }
    11.         return n == 1;
    12.     }
    13. }