题目描述

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

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

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

样例

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

算法1

哈希表

判断快乐数的过程中只有两种情况

• 1、无限循环 但始终变不到 1
• 2、直接变到 1

从起点开始，一直往下走，用哈希表记录每一次变过的点

• 1、若哈希表本身就已经有该点，则表示已经走到了一个死循环，则 return false
• 2、若一直走下去，哈希表中都不存在该点，并顺利走向1，则 return true

时间复杂度 $O(1)$

Java 代码

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

算法2

双指针

可以将判断快乐数过程中的所有点看成一个单链表，可能存在环，即该问题就变成了单链表是否存在环的问题

• 1、fast 指针从原点每次走2步， slow 指针从原点每次走1步
• 2、两个指针从起点开始走，只要有环，最终两个指针都会相遇，或者没有环，最后走到1，也会不停的在1位置循环，也会相遇，因此两个指针最后一定会相遇
  • (1)、当相遇的点的值是1，则表示不存在环
  • (2)、当相遇的点的值不是1，则表示存在环

时间复杂度 $O(1)$

Java 代码

class Solution {
    static int get(int n)
    {
        int res = 0;
        while(n != 0)
        {
            res += (n % 10) * (n % 10);
            n /= 10;
        }
        return res;
    }
    public boolean isHappy(int n) {
        if(n == 1) return true;
        int fast = get(n), slow = n;
        while(fast != slow)
        {
            fast = get(get(fast));
            slow = get(slow);
        }
        return fast == 1;
    }
}