LeetCode题解：快乐数

题目描述

编写一个算法来判断一个数n是不是快乐数。
“快乐数”定义为：

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

如果n是快乐数就返回true，否则就返回false。

示例

• 示例1
  输入：n = 19
  输出：true
  解释：
  1^2 + 9^2 = 82
  8^2 + 2^2 = 68
  6^2 + 8^2 = 100
  1^2 + 0^2 + 0^2 = 1
• 示例2
  输入：n = 2
  输出：false

思路方法

只需要抓住一点：按快乐数的运算方式，最后得到的数要么是1，要么就在一定范围内无限循环（得不到1）。

哈希法

class Solution {
    public int getNext(int n){
        int totalNum = 0;
        while(n!=0){
            int temp=n%10;
            n/=10;
            totalNum+= temp*temp;
        }
        return totalNum;
    }
    public boolean isHappy(int n) {
        Set<Integer> hash = new HashSet<Integer>();
        while(n>1&&!hash.contains(n)){
            hash.add(n);
            n = getNext(n);
        }
        return n==1;
    }
}

复杂度分析

• 时间复杂度：O(logn)
• 空间复杂度：O(logn)

双指针法

class Solution {
    public int getNext(int n){
        int totalNum = 0;
        while(n!=0){
            int temp=n%10;
            n/=10;
            totalNum+= temp*temp;
        }
        return totalNum;
    }
    public boolean isHappy(int n) {
        int slow = n;
        int fast = getNext(n);
        while(fast!=1&&fast!=slow){
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        return fast==1;
    }
}

复杂度分析

• 时间复杂度：O(logn)
• 空间复杂度：O(1)