编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Solution

参考 @LeetCode官方

会有以下三种可能：

1. 最终会得到 11。
2. 最终会进入循环。
3. 值会越来越大，最后接近无穷大。

在代码中不需要处理第三种情况，是因为它永远不会发生。（列表，每一位数的最大数字的下一位数是多少）

• 利用 set 存储已经出现过的值

// @lc code=start
class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> record;
        while(n != 1){
            int sum = 0;
            while(n){
                sum += pow(n%10, 2);
                n /= 10;
            }
            if(record.find(sum)==record.end())
                record.insert(sum);
            else 
                return false;
            n = sum;
        }
        return true;
    }
};
// @lc code=end

• 双指针法
• 如果 n 是一个快乐数，即没有循环，那么快跑者最终会比慢跑者先到达数字 1。
• 如果 n 不是一个快乐的数字，那么最终快跑者和慢跑者将在同一个数字上相遇。

class Solution {
public:
    bool isHappy(int n) {

        if(n == 1) return true;

        int slow = op(n); 
      	if(slow == 1) return true;
        int fast =op(slow); 
      if(fast == 1) return true;
        while(slow != fast){
            slow = op(slow);
            fast = op(fast); if(fast == 1) return true;
            fast = op(fast); if(fast == 1) return true;
        }
        return false;
    }

private:
    int op(int n){
        int res = 0;
        while(n){
                res += pow(n%10, 2);
                n /= 10;
            }
        return res;
    }
};

java

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> sum = new HashSet<>();
        while (n != 1) {
            if (sum.contains(n)) {
                return false;
            }
            sum.add(n);
            n = getNextNum(n);
        }
        return true;
    }

    private int getNextNum(int n) {
        int num = 0;
        while (n != 0) {
            int tmp = n % 10;
            num += tmp * tmp;
            n /= 10;
        }
        return num;
    }
}